• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The present invention relates to a method for generating an electronic signature of a document associated with a condensate obtained by a given hash function including the implementation by data processing means (11b) of a server (1b) steps of: (a) receiving said condensate and zero-knowledge proof of knowledge that said condensate is the result of applying said hash function to said document; (b) Verification that said evidence with no disclosure of knowledge is valid; (c) generating an electronic signature of the document from said condensate.
    公开号:FR3059802A1
    申请号:FR1662089
    申请日:2016-12-07
    公开日:2018-06-08
    发明作者:Paul Keuffer Julien；Herve Chabanne；Emmanuel Prouff；Olivier Clemot
    申请人:Safran Identity and Security SAS；
    IPC主号:
    专利说明:

    GENERAL TECHNICAL AREA
    The present invention relates to the field of authentication, and in particular to a method of electronic signature of a confidential document.
    STATE OF THE ART
    The electronic signature of an electronic document makes it possible to guarantee the integrity of the document, to authenticate the author, and this definitively (non-repudiation), by analogy with the handwritten signature of a paper document.
    It is common for a document issuer to outsource the generation of the electronic signature to a service provider, called the Signature Solution Provider (FSS). Indeed, the electronic signature process must, to be officially valid, be certified by a competent authority, which is the case of the FSS (the implementation of this cryptographic primitive necessary for the signature indeed requires specific skills, with a secure secret key storage difficult to carry out in practice). To this end, the client (the sender of the document) uploads the document to an FSS server for the latter to sign.
    In practice, the electronic signature is not carried out on the complete document but on a condensate of it (also called "cryptographic imprint" or "hashed" of the document, from English "hash"), obtained by applying a cryptographic hash function to the document. The condensate has a fixed size and the signature primitive is applied to an element which is constructed from this condensate. In addition, the condensate does not reveal anything about the document: you cannot find the original document from this condensate, at least as long as the hash function used is considered safe. We can however recalculate the condensate from the message to verify that it is correct.
    If the document to be signed contains sensitive information, the client may not want to disclose it to their electronic signature provider. Since only the condensate is necessary to generate the signature of a document, it could be envisaged that the client could only transmit a condensate of the message to the FSS.
    But this is unthinkable today: since we cannot find the original document from its condensate, the FSS should produce a signature of a document that it has not seen. However, the fact of producing a signature commits it from a legal point of view, hence the current refusal of any FSS to generate an electronic signature if it does not have access to the document (a dishonest customer could provide the condensate of a document which is not his to attribute paternity to it).
    In summary, today the sender of a confidential document who wants a signature to be generated for this document can only:
    - Either provide the document in clear to an FSS and trust it;
    - Either generate the signature alone but it is necessary to have specific skills, to be certified by an authority and to provide the computing power yourself.
    It is noted that there are known electronic signature mechanisms known as blind, making it possible to sign a document which has been masked (the mask can be removed after the generation of the signature), so that the signatory cannot take cognizance of its content. This mechanism is widely used in electronic voting or virtual currency protocols, but is useless for solving this problem: the masked document could certainly be transmitted to the FSS without violating confidentiality, but the latter would still not accept generate the signature for lack of being able to verify that the condensate corresponds to this masked document. In addition, the signature obtained after unmasking is not a standard signature within the meaning of ISO standards or NIST.
    It would therefore be desirable to have a solution allowing document issuers to continue to delegate the generation of signatures to FSSs with the same level of security and reliability while eliminating the need to transmit the document in clear, and this quickly and efficiently.
    PRESENTATION OF THE INVENTION
    According to a first aspect, the present invention relates to a method for generating an electronic signature of a document associated with a condensate obtained by a given hash function comprising the implementation by data processing means of a server d 'stages of:
    (a) Receipt of said condensate and proof of zero disclosure of knowledge that said condensate is indeed the result of the application of said hash function given to said document;
    (b) Verification that said null knowledge proof is valid;
    (c) generation of an electronic signature of the document from said condensate.
    According to other advantageous and non-limiting characteristics:
    • step (c) includes the application to condensate of a function configured by a private key of a document issuer;
    • the zero-disclosure proof of knowledge is a cryptographic object of type zkSNARK;
    • said given hash function is a cryptographic hash function iterating a compression function according to the Merkle-Damgârd principle;
    • said given hash function is chosen from the functions of the SHA-1 and SHA-2 families;
    • said zero disclosure knowledge proof that said condensate is the result of the application of said hash function given to said document is zero knowledge proof evidence that the equipment 10a has a pre- image such that said condensate is indeed the result of the application of an iteration of the compression function to said pre-image;
    The method comprises a prior step (aO) of generation, by data processing means of equipment having said document, of said proof with zero disclosure of knowledge of the fact that said condensate is indeed the result of the application of said hash function given to said document;
    • step (aO) further comprises the prior generation of said condensate by application of said hash function given to said document;
    • step (c) includes the transmission of the electronic signature generated to said equipment data processing means;
    • the method comprises a subsequent step (d) of association by the data processing means of the equipment with the electronic signature to the document so as to form the signed document;
    • the step (aO) comprises the prior reception by the processing means of the equipment of a nonce, and the generation of a condensate of a concatenation of the document and the nonce supplemented by a block of stuffing;
    • step (a) includes receiving the nonce completed with a block of stuffing, and said condensate of a concatenation of the document and the nonce completed by the block of stuffing;
    • said zero disclosure proof of knowledge that the equipment has a pre-image such that said condensate is indeed the result of the application of at least one iteration of the compression function to said pre-image, is a proof with no disclosure of knowledge that the condensate of the document and the condensate of the concatenation of the document and of the nuncio completed by the stuffing block are linked by a given relation;
    Said relationship given between the condensate of the document and the condensate of the concatenation of the document and of the nonce completed by the stuffing block is chosen from a plurality of predetermined relationships, step (b) comprising the determination of said relationship as a function of the value received from the nonce completed by the stuffing block, and the verification of the proof accordingly;
    • step (aO) comprises the determination of the block of stuffing supplementing the nonce and the choice of said given relationship between the condensate of the document and the condensate of the concatenation of the document and the nonce completed by the blocking pad, as a function of lengths of said document and / or nonce.
    According to a second and a third aspect, the invention provides a computer program product comprising code instructions for the execution of a method according to the first aspect of generating an electronic signature of a document associated with a condensate. ; and a means of storage readable by a computer equipment on which a computer program product comprises code instructions for the execution of a method according to the first aspect of generation of an electronic signature of a document associated with a condensate .
    PRESENTATION OF THE FIGURES
    Other characteristics and advantages of the present invention will appear on reading the following description of a preferred embodiment. This description will be given with reference to the appended drawings in which:
    - Figure 1 is a diagram of an architecture for the implementation of the methods according to the invention;
    - Figure 2 illustrates the Merkle-Damgârd principle.
    DETAILED DESCRIPTION
    Architecture
    With reference to FIG. 1, there is proposed a method for generating an electronic signature of a document implemented within an architecture as shown. The document is associated with a condensate obtained by a given hash function.
    As explained, a hash function takes as input a message of arbitrary size (the original document) and produces a condensate of fixed size associated with this message. Here, said given hash function is advantageously a so-called cryptographic function, that is to say with additional properties: the condensate is statistically well distributed in the set of arrival values, it is impossible in reasonable time to find two messages which have the same condensate (resistance to collisions) and one cannot from the condensate find a message which made it possible to obtain this value (resistance to the calculation of pre-image).
    Hash functions constructed using the MerkleDamgârd principle (which will be discussed later), that is, iterating a so-called compression function, are examples of cryptographic hash functions which are advantageously chosen for the present process. We will take the example of the functions of the SHA family (“Secure Hash Algorithm”), standardized by the NIST (“National Institute of Standards and Technology”), in particular the SHA-1 or SHA-2 subfamilies (notably SHA -256)
    The present method is indeed a “generation of electronic document signature” method, and not a “document signature”. This means that it only allows to obtain the electronic signature of the document and not yet the "signed document", i.e. the association of the original document and the signature, generally in any container.
    By “electronic signature” of a document is meant the conventional definition of this term, namely a cryptographic primitive making it possible to identify the signatory and guaranteeing that the document has not been altered since the moment when the signature was produced and is indeed the original document (in the remainder of this description, the document from which the condensate is actually derived will be designated as "original"). This cryptographic object generally consists of an encrypted document condensate thanks to an asymmetric encryption function: the signatory uses a private key, and everyone can verify the signature using a public key (by comparing the condensate contained in the signature and a recalculated condensate).
    More specifically, signature standards such as the PKCS # 1 v2.2 standard impose the signing of a fixed-size "summary" of the document, this summary being obtained from the condensate and padding to obtain a predetermined size. Note that the data that completes the digest of the document does not depend on the document itself.
    In general, it will be considered in the remainder of this description that the electronic signature is constructed from the condensate using a function known to those skilled in the art, and in a preferred embodiment that the electronic signature is constructed by modifying Hardly reversible condensate, by applying a function set by the signatory's private key (this type of function is called trap door). It should also be noted that, depending on the signature algorithms used, the condensate can be supplemented with stuffing and masking (to make the signature non-deterministic). Those skilled in the art will be able to generate the signature from the condensate using the techniques of their choice.
    The present method is essentially implemented via a server 10b of an FSS, equipped with data processing means 11b (one or more processors). The server 10b can further comprise data storage means 12 (a memory) for the storage of the various cryptographic objects involved.
    The server 10b can be connected in particular via a network 2 such as the Internet to an equipment 10a supplying said document for which to generate the signature (but only transmitting its condensate as will be seen). The equipment 10a is thus typically a work station of a document issuing body, i.e. the signatory (client of the FSS).
    The equipment 10a can itself be connected to other third-party servers 10c to which it can transmit the signed document once the server 10b has sent it the generated electronic signature.
    Signature generation method
    The present electronic signature generation method is implemented by the data processing means 11b of the server 10b from an imprint of said document for which the signature is desired.
    More specifically, the server 10b will receive (from the equipment 10a) the condensate of the original document, but not the document itself which can remain confidential.
    And yet, the present process makes it possible to make signature operations on a condensate while having a strong guarantee that this condensate is indeed linked to a document validly owned by the client, in other words allows to sign a confidential original document without having direct access to this document.
    For this, we use a cryptographic protocol generating a "proof" that the condensate which is at the origin of the signature is indeed linked to a document, this proof revealing nothing other than the fact that the original document is well possessed by the producer of the evidence.
    The Pinocchio protocol presented in the publication "Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova, Pinocchio: Nearly Practical Verifiable Computation, in Proceedings of the IEEE Symposium on Security and Privacy, IEEE, May 21, 2013" was one of the first verifiable calculation protocols allowing the performer to calculate the application of any function in a verifiable manner and the client to verify the associated proof in a calculation time less than that necessary to perform the calculation itself.
    In a first step (a), the data processing means 11b of the server 10b of the FSS (not having the original document, and playing the role of "verifier") receive said condensate and a proof with zero disclosure of knowledge of the fact that said condensate is indeed the result of the application of said hash function given to said original document.
    Preferably, this step is preceded by a prior step (aO) of generation, by the data processing means 11a of the client's equipment 10a (having said original document, and playing the role of "prover"), of said proof with zero disclosure of knowledge of the fact that said condensate is indeed the result of the application of said hash function given to said document
    More specifically, said zero-disclosure proof guarantees the following statement: "given the condensate of an original document received, the equipment 10a has a document whose condensate corresponds to that supplied".
    This step (aO) preferably further comprises the prior generation of said condensate by application of said hash function given to said document (as typically explained by families SHA-1 or SHA-2, in particular SHA-256).
    Thus, one can link the condensate to the original document but one cannot obtain information on the contents of the original document. The cryptographic protocol gives proof that is quick to verify (less than half a second) and that cannot be falsified: it is almost impossible (probability less than 1/2 80 , even less than 1/2 128 depending on the parameters chosen for carry out the proof, the latter then being slower to carry out) to have proof of the above statement accepted if the process has not proceeded in accordance with what is specified.
    In carrying out the proof, the prover uses the possibility of producing proofs with zero disclosure of knowledge to hide the original document. Thus the evidence gives no information on the document itself, except that the condensate supplied is linked to this document.
    In all cases, in a step (b) the data processing means 11b of the server 10b verify that said proof with zero disclosure of knowledge is valid, and if this is the case they generate the electronic signature of the document from said condensate in step (c). As explained, the generation of the signature of step (c) typically consists in the application to the condensate of a function parameterized by a private key of a sender of the document, if necessary supplemented with other elements (stuffing and masking).
    The verification of such proof in step (b) is not interactive (the verifier, ie the FSS does not need to contact the prover, ie the client) and is simply done in constant time by verifying that the proof is valid, which ίο shows (with a very small probability) to the server 10b that the claimed property is true, ie that the client has a valid document having as condensate the condensate received. He therefore became convinced that the condensate sent to him was lawful despite the absence of the original document.
    Thus, once the proof is verified, the condensate alone is considered sufficient for a signature to be generated without risk of usurpation.
    Thanks to the evidence (which we will come back to in more detail later), confidentiality can be complete (since the generation of evidence does not require communication between the client and the FSS) without FSS taking any risk since the evidence guarantees that the customer has the original message.
    The proof is short (see very short - of the order of 300 bytes - in preferred embodiments which will be described later), transmitting it with the condensate of the document poses no bandwidth problem. In addition, the verification of this proof is rapid (in constant time, a few tens of thousandths of a second), which does not increase the computational load at the level of the data processing means of the FSS server 10b. The generation of proof is heavier in terms of calculation time, but since step (aO) is implemented on the equipment side 10a, this additional calculation time is the responsibility of the customer, who takes into account somehow to cover the additional cost related to the need to keep the document confidential.
    Thus the present process is optimal for both the client and the signature provider.
    Additionally, step (c) may comprise the transmission of the electronic signature generated to said data processing means 11a of the equipment 10a (in response to step (a) which constitutes a signature request), so as to being able to implement a subsequent step (d) of association by the data processing means 11a of the equipment 10a of the electronic signature to the document so as to form the signed document. The equipment 10a can then legally avail itself of this electronic signature from other entities (servers 10c).
    Evidence generation
    Preferably, said proof with zero disclosure of knowledge is a cryptographic object of the zkSNARK type.
    zkSNARK means "zero-knowledge Succinct Non Interactive ARgument of Knowledge", i.e. Non-interactive knowledge argument with zero knowledge disclosure. It is a cryptographic primitive built around the notion of evidence. Researchers in theoretical computer science and in cryptography have long been interested in the concept of evidence. There are theoretical results allowing to produce a very short and secure proof of an algorithm but the time to carry out this proof is out of reach and will remain despite the increase in the computing power of computers. One of the reasons is the power given to the prover, the prover. In the theoretical proof results, the prover has infinite computing power and the proofs remain secure despite this.
    The notion of evidence was then released, the protocol seeking to protect itself only from a prover that would have significant but limited computing power. The result of the protocol is no longer evidence but an argument. It is from this notion of argument that practical verifiable calculation systems were built. An additional requirement in a system producing an argument is that this argument is non-interactive: the verifier and the prover do not need to interact to produce the argument.
    Since 2010, realizations of zkSNARKs have been presented: these are arguments whose size is short (some elements of an elliptical curve), which do not require interactivity and which moreover allow the prover to perform proof with zero disclosure of knowledge ie the proof contains no non-trivial information on the entries provided by the prover.
    There are several protocols which concretely carry out zkSNARKs, and a person skilled in the art can use them indifferently in the present process:
    - The Pinocchio protocol already mentioned;
    - The Gepetto Protocol, presented in the publication “Craig Costello, Cedric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, and Samee Zahur, Geppetto: Versatile Verifiable Computation, in Proceedings of the IEEE Symposium on Security and Privacy, IEEE, 18 May 2015 ", which is an improvement from Pinocchio
    - The protocol presented in the following publication "Eli BenSasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza. SNARKs for C: Verifying Program Executions Succinctly and in Zéro Knowledge. In Proceedings of the 33rd Annual International Cryptology Conference, CRYPTO Ί3, pages 90108, 2013 ”, implemented open-source in the form of a library called libsnark, optimizing the protocol producing a zkSNARK in Pinocchio by improving expressiveness that is, the type of programs or algorithm that can be checked.
    To take the example of the Pinocchio protocol, this protocol has several parts:
    1. A classical program is translated in the form of an arithmetic circuit, that is to say a set of relations between the inputs and outputs of the program translated only using additions and multiplications d elements of a finite body. It should be noted that all programs can in theory be translated in this form but that only part of these programs admits efficient translation in circuit form.
    2. The arithmetic circuit obtained is effectively represented using three families of polynomials, to which is added an additional polynomial, called the target polynomial. These families of polynomials form "Quadratic
    Arithmetic Programs ”(QAPs). They encode the relationships between the inputs and outputs of each multiplicative gate of the circuit, the relationships of the additive gates being integrated in the first multiplicative gate which follows in the calculation.
    These OAPs are linked to the verifiable calculation by the following point: a calculation y = C (x) is correct for an input x if and only if all the relations describing the corresponding arithmetic circuit are satisfied by fixing as input value x and as output value y.
    OAPs allow you to compress all the constraints to be checked in a single relationship to be checked: a polynomial constructed from the value x and from the three families of the CAP must divide the target polynomial.
    3. A cryptographic protocol then takes as input a CAP associated with a program, generates evaluation and verification keys which use elliptic curves to hide the polynomial relationships. The polynomial proving that the calculation was performed correctly is then calculated directly using the relationships hidden in the elliptic curve. The divisibility relation is only translated using a constant number of elements of the elliptic curve, that is to say that the proof is of constant size. The verification of this proof is extremely fast.
    The protocol also makes it possible to obtain that the calculation inputs provided by the prover are private: it allows to hide the values of the prover in the realization of the proof by multiplying them by a multiple of the target polynomial, which does not modify the causes the "proof" polynomial to be divisible by the target polynomial.
    This “proof” polynomial, when it is hidden in an elliptical curve constitutes a zkSNARK.
    The Pinocchio protocol allows the person carrying out the proof to hide some of the entries in the calculation which he proves. In this case, it is a question of carrying out the following calculation:
    Input: length of document M, initialization vector IV
    Private entry: the document M for which we want to calculate the condensate h (M),
    Output: h (M) and proof π that the prover knows a document M which is hashed in h (M).
    Note that there are known protocols intended for the generation of proof of proper operation of a hash function, which the skilled person can directly use even if they are not optimal. The difficulty is to obtain a reasonable calculation time to carry out the proof and sizes of evaluation and verification keys which are not too large.
    - the Zerocash protocol (IEEE Security & Privacy 2014) of BenSasson et al., proposes the definition of an arithmetic circuit to verify the compression function of SHA-256 which comprises around 30,000 multiplicative gates. This gives a proof completion time of about 5 seconds (per compression level, checking the entire hash function which includes many iterations of the compression function will be significantly longer), which remains high and largely improvable;
    - the ZKBoo protocol, presented in the publication "ZKBoo: faster zero-knowledge for boolean circuits" by Giacomelli, Madsen and Orlandi (Usenix Security 2016) "allows better performance (proof in 50 ms, verification in 70 ms) by iteration of the compression function, but the size of the proof is substantial (800 KB) all the more since it seems to have been measured only on an application of the compression function.
    Preferred embodiment
    As explained, the Pinocchio process and its known derivatives have the major drawback of requiring significant computing power on the side of the performer (the data processing means 11a of the client's equipment 10a). The cost of producing proof of a calculation by this protocol is several orders of magnitude higher than that of the calculation itself.
    In practice, it can be seen that the SHA-256 function (and more precisely its compression function) comprises numerous bit-by-bit operations which are ill-suited to the representation of the calculations used in the Pinocchio protocol. A first solution to speed up the generation of proof is to change the hash function, for example by using hash functions based on the sum of subsets (also known as arithmetic, because the arithmetic circuit representing the function has fewer multiplicative gates. Examples are described in the publication "O. Goldreich, S. Goldwasser, and S. Halevi. Collision-free hashing from lattice problems. Technical report, 1996 ”.
    These functions have been used in zkSNARKs and described in the publication “E. Ben-Sasson, A. Chiesa, E. Tromer and M. Virza. Scalable Zero-Knowledge via Cycles of Elliptic Curves. CRYPTO 2014 ”.
    However, the functions of the SHA family remain the most used (because standardized), and above all, they make it possible to obtain a condensate which will be used to produce the standard signature, once the protocol is finished, this is why it is desirable to have an algorithm that allows them to be used despite their poor adaptation to the representation of the calculations used in the Pinocchio protocol.
    In a preferred embodiment, the present method thus overcomes these difficulties by allowing, as we will see, to generate a small constant digital proof (of the order of 300 bytes, ie several thousand times less than for known protocols) in a few thousandths of a second, and without revealing anything on the original document, using properties of the cryptographic hash functions iterating a compression function according to the Merkle-Damgârd principle.
    Referring to Figure 2, we note that to be able to process documents of arbitrary size, the Merkle-Damgârd principle used by the preferred hash functions such as SHA-1 or SHA-2 consists in defining the function h " of compression ”mentioned before taking as input a message mi and a chaining variable of fixed size (with t 0 = IV the initialization vector) and the result of which is a message t t of size smaller than the initial message. This function h is called compression function because it takes an input of M bit and produces at its output a sequence of N bit with N strictly less than M. In the case of SHA-256 for example the input has a size of 512 bit (ie the message is processed block by block of size 512 bit) and the compression function produces a value of size 256 bit.
    Then the compression function is applied recursively to each block of the message until all the possible blocks have been used up and ultimately obtains t n = // (m) = / i (/ i (... / i (/ V, m 1 ), m 2 ), ..., m n ). This principle thus extends the calculation of a condensate to any message of any size (less than 2 64 -1 for SHA-256).
    Note that to protect against certain attacks, the last message block m n is completed by a padding block PB (in English padding block), so that the entry of the last occurrence of h is m n II PB. In the case of SHA-256, this block is of variable size but at least equal to 65 bit. It includes a field announcing the size of the message in bits and a means of knowing when this block is finished.
    One solution to greatly limit the generation time of the proof and its size when the hash function applies the Merkle-Damgârd principle is then to use a proof of knowledge of a preimage of the compression function (in others terms the internal state after already several iterations of the function h, in practice one of the values t ^ ie [l; n- lj], more specifically the last value ΐ η _ ± ) rather than necessarily the original document, this evidence also showing possession of the document, provided that the hash function does have the cryptographic properties expected of it, such as resistance to pre-image computation or a statistically well distributed distribution among all possible values . More precisely, instead of proving that he knows the prover can content himself with proving that he knows the value t n _ !, because it makes it possible to verify (with the last message block m n ) that the result obtained by applying a single iteration of the compression function h is equal to the value of the condensate transmitted to the verifier.
    Indeed, it can be shown that the affirmations “given the condensate of an original document received, the equipment 10a has a document whose condensate corresponds to that supplied” and “given the condensate of an original document received , the equipment 10a has a pre-image of the compression function of said hash function, the result of which (application of an iteration of the compression function to said pre-image) corresponds to the condensate supplied "are substantially equivalent (the two propositions have the same computational difficulty).
    For this, a challenge-response mechanism is cleverly used. More precisely, by studying in more detail the construction of hash functions based on the Merkle-Damgârd scheme, one can obtain a means of carrying out the proof which requires less computation. For a nonce τ (ie an arbitrary number, that is to say a random, for single use, from the English “number used once”, which plays the role of challenge), by expressing the value of H (m ) and H (m II τ) using the compression function, we see that there are quantities common to both expressions. It then suffices to prove that the quantities H (m) and H (m II τ) are linked to prove that the client is aware of a pre-image of the hash function and therefore of the original document.
    In most of the practical verifiable calculation protocols that exist, the programs to be verified must not use a data-dependent control structure. This is problematic in our situation because the program that calculates the message condensate must apply the compression function as many times as there are blocks in the document.
    In the proof to be produced, it is necessary to apply a small number of times the compression function, between two and four times according to the size of the last block of the message. But we are still in a case where the program producing the proof includes instructions which are not fixed before knowing the document.
    To get around this, the idea is to modify the length of the nonce τ using padding (we obtain τ ραά , which is as we will see included in the response to the challenge) and to produce three proof systems which correspond to the three possible cases listed in Table 1 below.
    <ïts it- 1 ('ii' »ii v 2 <it '· n 3 i. h7i ί -U 7 447 <l <512 ! 512 îu, i ; i }>!; ,, PB ,; Λιίι /., ΡΗρ., Ρίβ ’ ί ,,. ΡΕ, : = 00,, Λ11Miîhw ,, r „„ · ,. · ,!). 1f'- Μ-Λι [j τ ïpffirf s = T | W) / ί ’/ ίΐ;., Γ ,,,, ίΐ ./’ Λ; ; jh, ΡΒ,;. τ ΡΒ > Γ. ,,,.; Ph 2 .
    T. BI L h R e 1 al <n entre // i w el Hun i <e, nn la idilk 'ik ‘wi
    These three cases, based on the example of SHA-256, are linked to the requirement that the padding block is of variable size but at least equal to 65 bit: if the final block m n has a length greater than 447 bit (ie 512-65) but greater than 512 bit, then the padding block PB should be between 1 and 64 bit which is not possible. It is then divided into PB ± and PB 2 (ie PB = PB l II PB 2 ), PB 1 completing m n and PB 2 being a complete block of 512 bit compressed in an additional occurrence of h.
    Thus, to return to the nonce τ, for example in the simple case where the document has a length which is a multiple of 512 bit (the last block therefore has a length of 512 bit), the expressions in Table 1 indicate that the client must prove that he knows a value a (which corresponds to t n ) such that: H (m) = Ιτζα, ΡΒ ^ and H (m II τ) = h (a, T II PB 2 ~), with PB ± with a length of 512 bit and PB 2 the length to complete τ with 512 bit (which is possible if τ is short, for example 64 bit). The client then produces a zero disclosure proof of knowledge by hiding the value t n from the signatory.
    Step (aO) thus advantageously comprises the prior reception by the processing means 11a of the equipment 10a of a nonce τ (the challenge, preferably of a predetermined length such as 64 bit), and the generation of a condensate from a concatenation of the document and the nonce supplemented by a block of stuffing τ ραά , which will be called “auxiliary condensate” for convenience in this description (the condensate of the original document will be called the “main condensate”) . The idea is thus to modify the length of the nonce τ using padding and to produce three proof systems which correspond to the three possible cases listed in Table 1.
    More precisely :
    - In case 1, is generated by the data processing means 11a of the equipment 10a a proof with zero disclosure of knowledge of the fact that
    Ξχ G {0, l} 256 , Ξα, b G {0, l} 512 , H (m) = h (x, a) RH (m II r pad ) = h (x, b)
    - In case 2, is generated by the data processing means 11a of the equipment 10a a proof with zero disclosure of knowledge of the fact that
    Ξχ G {0, l} 256 , 3 a, h, c G {0, l} 512 , H (m) = h (x, a) / H (m II τ ραά ) = h (h (x, b), c)
    - In case 3, is generated by the data processing means 11a of the equipment 10a a proof with zero disclosure of knowledge of the fact that
    Ξχ G {0, l} 256 , 3 a, h, c G {0, l} 512 , H (m) = h (h (x, a), II r pad ) = h (h (x, a) , vs)
    Even if this table is designed for SHA-256, those skilled in the art will be able to adapt it for other hash functions constructed with the Merkle-Damgârd principle and determine the adequate proofs to generate.
    Step (a) then comprises the reception (by the processing means 11b of the server 10b) of said auxiliary condensate H (m II τ ραά ) (with the proof and the main condensate and the said nonce completed by a block of stuffing τ . ραά in other words the client transmits τ ραά and the signatory chooses one of three proof systems based on τ ραά if τ ραά is 64 bit long it is in case number 3, otherwise its the bit more to the left begins with 0 in case number 1 and with 1 in case number 2. The data processing means 11b of the server 10b then know which proposition to check in step (b).
    Summary of the preferred embodiment
    In this particularly preferred embodiment, the method for generating an electronic signature of a document m associated with a condensate H (m) obtained by a cryptographic hash function H iterating a compression function h according to the Merkle principle. Damgârd, includes the following stages:
    (aO) By the processing means 11a of the equipment 10a:
    - Reception of a nonce (the challenge τ) generated and sent by the server 10b;
    - Generation of the nonce supplemented by a stuffing block (the response τ ραά ), said stuffing block being advantageously determined as a function of lengths of the nonce τ and especially of said document m (preferably according to three diagrams depending on the length of the document);
    - generation of said condensate (main condensate H (m)) by application of said hash function given H to said document m;
    - generation of a condensate of a concatenation m II τ ραά of the document and of the nonce supplemented by the block of blocking (auxiliary condensate H (m II τ ραά )) by application of the same given hash function (to which document is concatenated the nonce completed by the stuffing block);
    generation of proof with zero disclosure of knowledge of the fact that said (main) condensate is indeed the result of the application of said hash function given to said document; said proof being more precisely proof with zero disclosure of knowledge of the fact that the equipment 10a has a pre-image x such that said condensate H (m) is indeed the result of the application of at least one iteration ( in particular one or two) of the compression function h at said pre-image x; said proof being more precisely proof with zero disclosure of knowledge of the fact that the condensate (main) the condensate (auxiliary) of the concatenation of the document and the nuncio completed by the blocking of blocking H (m II τ ραά ) are linked by a given relation (relating to the iterations of the compression function h); said relationship given between the condensate H (m) of the document and the condensate H (m II T pad ) of the concatenation of the document and of the nonce supplemented by the stuffing block being preferably determined as a function of the length of said document H (m) . In the example of SHA-256, according to this length there are three cases according to which the relation is: Ξα, b, c G {0, l} 512 such that o is H (riï) = h (x, a) / H (m II τ ραά ) = h (x, b) o let H (riï) = h (x, a) / H (m II τ ραά ) = h (h (x, b), vs) ;
    o let H (riï) = h (h (x, a), b) / H (m II τ ραά ) = h (h (x, a), c); where x is as explained the pre-image (of a length 256 bit) of which we prove the knowledge;
    - return to server 10b of the condensate (main) H (m), of the condensate (auxiliary) H (m II τ ραά ) of the concatenation of the document and of the nonce completed by the block of blocking, of the nonce supplemented by the block of blocking τ ραά , and of the proof;
    (a) reception of these elements by the processing means 11b of the server 10b;
    (b) determination by the processing means 11b of the server 10b of said relation that proves the proof as a function of the value received from the nonce completed by the stuffing block τ ραά , and the verification that said proof with zero disclosure of knowledge is valid accordingly (knowing the relationship);
    (c) generation of an electronic signature of the document from said (main) condensate H (m), if the proof has indeed been verified and validated, and if necessary return to the equipment 10a of the signature so that that she produce the signed document, ie the original document with its signature attached.
    Computer program product
    According to a second and a third aspect, the invention relates to a computer program product comprising code instructions for execution (in particular on the data processing means 11a, 11b of the equipment 10a and / or server 10b) of a method according to the first aspect of the invention for generating an electronic signature of a document associated with a condensate, as well as storage means readable by computer equipment (a memory of the equipment 10a or the second server 10b) on which we find this computer program product.
    权利要求:
    Claims (16)
    [1]
    1. Method for generating an electronic signature of a document associated with a condensate obtained by a given hash function comprising the implementation by data processing means (11b) of a server (1b) of steps from:
    (a) Receipt of said condensate and proof of zero disclosure of knowledge that said condensate is indeed the result of the application of said hash function given to said document;
    (b) Verification that said null knowledge proof is valid;
    (c) generation of an electronic signature of the document from said condensate.
    [2]
    2. Method according to claim 1, in which step (c) comprises the application to condensate of a function parameterized by a private key of a sender of the document.
    [3]
    3. Method according to one of claims 1 and 2, wherein the proof of zero knowledge disclosure is a cryptographic object of type zkSNARK.
    [4]
    4. Method according to one of claims 1 to 3, wherein said given hash function is a cryptographic hash function iterating a compression function according to the Merkle-Damgârd principle.
    [5]
    5. The method of claim 4, wherein said given hash function is chosen from the functions of the SHA-1 or SHA-2 families.
    [6]
    6. Method according to one of claims 4 and 5, wherein said proof with zero disclosure of knowledge of the fact that said condensate is indeed the result of the application of said hash function given to said document is proof with zero disclosure of knowledge of the fact that the equipment 10a has a pre-image such that said condensate is indeed the result of the application of an iteration of the compression function to said pre-image.
    [7]
    7. Method according to one of claims 1 and 6, comprising a preliminary step (aO) of generation, by data processing means (11a) of an equipment (10a) having said document, of said proof with zero disclosure knowledge of the fact that said condensate is indeed the result of the application of said hash function given to said document.
    [8]
    8. The method of claim 7, wherein step (aO) further comprises the prior generation of said condensate by application of said hash function given to said document.
    [9]
    9. Method according to one of claims 7 and 8, wherein step (c) comprises transmitting the electronic signature generated to said data processing means (11a) of the equipment (10a).
    [10]
    10. The method of claim 9, comprising a subsequent step (d) of association by the data processing means (11a) of the equipment (10a) of the electronic signature to the document so as to form the signed document.
    [11]
    11. Method according to one of claims 7 to 10, wherein step (aO) comprises the prior reception by the processing means (11a) of the equipment (10a) from a nonce, and the generation of a condensate of a concatenation of the document and the nonce supplemented by a block of stuffing.
    [12]
    12. The method of claim 11, wherein step (a) comprises receiving the nonce completed with a stuffing block, and said condensate from a concatenation of the document and the nonce completed by the stuffing block.
    [13]
    13. The method of claims 6 and 12 in combination, wherein said zero disclosure of knowledge that the equipment 10a has a pre-image such that said condensate is the result of the application of minus an iteration of the compression function at said pre-image, is proof with no disclosure of knowledge of the fact that the condensate of the document and the condensate of the concatenation of the document and of the nonce completed by the stuffing block are linked by a given relationship.
    [14]
    14. The method of claim 13, wherein said given relationship between the condensate of the document and the condensate of the concatenation of the document and of the nonce completed by the stuffing block is chosen from a plurality of predetermined relationships, step (b) comprising determining said relationship as a function of the value received from the nonce completed by the stuffing block, and verifying the proof accordingly.
    [15]
    15. The method of claim 14, wherein step (aO) comprises determining the stuffing block completing the nonce and choosing said given relationship between the condensate of the document and the condensate of the concatenation of the document and the completed nonce by the stuffing block, as a function of the lengths of said document and / or of the nonce.
    16. Product program computer including of instructions from code for the execution of a process according to one of claims 1 at 15 of generation of a signature electronic of a
    document associated with a condensate.
    [16]
    17. Storage means readable by computer equipment on which a computer program product comprises code instructions for the execution of a method according to one of claims 1 to 15 of
    5th generation of an electronic signature of a document associated with a condensate.
    3059
    类似技术:
    公开号 | 公开日 | 专利标题
    EP3334121A1|2018-06-13|Process of generating an electronic signature of a document associated to a digest
    EP2441207B1|2020-06-03|Cryptographic method for anonymous authentication and separate identification of a user
    FR3041195A1|2017-03-17|METHOD OF ACCESSING ONLINE SERVICE USING SECURE MICROCIRCUIT AND SECURITY TOKENS RESTRICTING THE USE OF THESE TOKENS TO THEIR LEGITIMATE HOLDER
    Lenstra et al.2015|A random zoo: sloth, unicorn, and trx
    WO2000048355A2|2000-08-17|Method for verifying the use of public keys generated by an on-board system
    EP2345202B1|2017-04-05|Digital signature method in two steps
    EP2656538B1|2015-07-29|Anonymous access to a service by means of aggregated certificates
    EP2707989A1|2014-03-19|Device and method for generating keys with enhanced security for fully homomorphic encryption algorithm
    EP2415199B1|2017-10-18|Method for performing a cryptographic task in an electronic component
    EP1166496A1|2002-01-02|Authentication and signature method for messages using reduced size of binary units of information content and corresponding systems
    Lepoint2014|Design and implementation of lattice-based cryptography
    Du et al.2020|Towards privacy-assured and lightweight on-chain auditing of decentralized storage
    EP1216537B1|2011-07-27|Method, system, device for proving authenticity of an entity or integrity of a message
    FR2834153A1|2003-06-27|Zero knowledge cryptographic system for electronic payment uses factorization and discrete logarithm
    EP0743775B1|1998-01-14|Method of zero-knowledge digital signatures, for creating a collision-resistant signature
    EP3614617A1|2020-02-26|Method and device for generating parameter| of an asymmetric cryptographic protocol from a blockchain, associated encryption and decryption method and device and computer program
    EP3767876A1|2021-01-20|Method for verifying a transaction in a blockchain type database
    EP3328026B1|2020-08-19|Methods of censoring an original document or verifying the authenticity of a final document
    Kaim2020|Privacy preserving post-quantum cryptography
    EP3843327A1|2021-06-30|Method for encoding a small-size cryptographic integrity pattern and associated devices
    Barbara2019|Proof of all: Verifiable computation in a nutshell
    Drosatos2013|Utilization and protection of personal data in ubiquitous computing environments
    FR3070517A1|2019-03-01|SYSTEM AND METHOD FOR AUTHENTICATION AND DIGITAL SIGNATURE
    WO2021110518A1|2021-06-10|Method for cogenerating a shared cryptographic material, devices, system and corresponding computer program
    FR3065552A1|2018-10-26|METHOD AND SYSTEM OF AUTHENTICATION AND NON-REPUDIATION
    同族专利:
    公开号 | 公开日
    EP3334121A1|2018-06-13|
    US20180159689A1|2018-06-07|
    US10785036B2|2020-09-22|
    FR3059802B1|2018-11-09|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    EP3010177A1|2014-10-13|2016-04-20|Morpho|Method for authenticating a client device with a server using a secret element|
    JP4306232B2|2002-11-25|2009-07-29|日本電気株式会社|Proof system and evaluation system|
    US20110246779A1|2008-12-11|2011-10-06|Isamu Teranishi|Zero-knowledge proof system, zero-knowledge proof device, zero-knowledge verification device, zero-knowledge proof method and program therefor|
    US20180096551A1|2016-10-04|2018-04-05|International Business Machines Corporation|Spheres of knowledge|EP3566384B1|2017-01-06|2021-02-17|Koninklijke Philips N.V.|Pinocchio / trinocchio on authenticated data|
    US11080433B2|2018-04-29|2021-08-03|Cryptowerk Corp.|Cryptographic data storage|
    US11080403B1|2018-12-19|2021-08-03|Hewlett-Packard Development Company, L.P.|Securely constructing a trusted virtual environment|
    SG11202013136SA|2020-02-03|2021-01-28|Alipay Hangzhou Information Technology Co Ltd|Blockchain-based trustable guarantees|
    法律状态:
    2017-11-20| PLFP| Fee payment|Year of fee payment: 2 |
    2018-06-08| PLSC| Publication of the preliminary search report|Effective date: 20180608 |
    2019-11-20| PLFP| Fee payment|Year of fee payment: 4 |
    2020-11-20| PLFP| Fee payment|Year of fee payment: 5 |
    2021-11-18| PLFP| Fee payment|Year of fee payment: 6 |
    2021-12-24| CD| Change of name or company name|Owner name: IDEMIA IDENTITY & SECURITY FRANCE, FR Effective date: 20211118 |
    2021-12-24| CA| Change of address|Effective date: 20211118 |
    优先权:
    申请号 | 申请日 | 专利标题
    FR1662089A|FR3059802B1|2016-12-07|2016-12-07|METHOD FOR GENERATING AN ELECTRONIC SIGNATURE OF A DOCUMENT ASSOCIATED WITH A CONDENSATE|
    FR1662089|2016-12-07|FR1662089A| FR3059802B1|2016-12-07|2016-12-07|METHOD FOR GENERATING AN ELECTRONIC SIGNATURE OF A DOCUMENT ASSOCIATED WITH A CONDENSATE|
    US15/833,822| US10785036B2|2016-12-07|2017-12-06|Method for generating an electronic signature of a document associated with a condensate|
    EP17205943.8A| EP3334121A1|2016-12-07|2017-12-07|Process of generating an electronic signature of a document associated to a digest|
    [返回顶部]