[go: up one dir, main page]

WO2015118160A1 - Procédés de signature pour distribuer des signatures partielles et/ou des signatures-seuils, procédés de validation correspondants et dispositifs électroniques correspondants - Google Patents

Procédés de signature pour distribuer des signatures partielles et/ou des signatures-seuils, procédés de validation correspondants et dispositifs électroniques correspondants Download PDF

Info

Publication number
WO2015118160A1
WO2015118160A1 PCT/EP2015/052681 EP2015052681W WO2015118160A1 WO 2015118160 A1 WO2015118160 A1 WO 2015118160A1 EP 2015052681 W EP2015052681 W EP 2015052681W WO 2015118160 A1 WO2015118160 A1 WO 2015118160A1
Authority
WO
WIPO (PCT)
Prior art keywords
partial
group
elements
sahai
groth
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/EP2015/052681
Other languages
English (en)
Inventor
Marc Joye
Benoit Libert
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Thomson Licensing SAS
Original Assignee
Thomson Licensing SAS
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Thomson Licensing SAS filed Critical Thomson Licensing SAS
Publication of WO2015118160A1 publication Critical patent/WO2015118160A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3247—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures
    • H04L9/3255—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures using group based signatures, e.g. ring or threshold signatures

Definitions

  • the disclosure relates to cryptography techniques, and more precisely to threshold signature techniques, where the signing capabilities are distributed over several devices.
  • threshold signature schemes that belong to the branch of threshold cryptography which was suggested in the article entitled “Threshold Cryptosystems” by Y. Desmedt et al., published in the conference proceedings of Crypto'89
  • the private key is shared among n servers in such a way that at least t out of these n servers have to contribute to each signature generation.
  • most existing threshold signature schemes either require interaction among the servers during the signing process or only provide security against static corruptions.
  • several practical non-interactive threshold signature schemes were proposed by Shoup (in the article entitled “Practical Threshold Signatures” , published in the conference proceedings of Eurocrypt 2000, LNCS series, pp.
  • the first adaptively secure threshold signatures were independently described in 1999 by Canetti et al. (described in the article entitled “Adaptive Security for Threshold Cryptosystems” , published in the conference proceedings of Crypto'99, LNCS 1666, pp. 98-115) and by Frankel et al. (described in the article entitled “Adaptively-Secure Distributed Public-Key Systems”, published in the conference proceedings of ESA'99, LNCS 1643, pp. 4-27. and in the article entitled “Adaptively-Secure Optimal-Resilience Proactive RSA", published in the conference proceedings of Asiacrypt'99, LNCS 1716, pp. 180-194).
  • threshold Schnorr signatures do not require the servers to jointly generate a randomized signature component in a first round before starting a second round.
  • SIP single inconsistent player
  • this server Since this server is chosen at random by the simulator among the n severs, it is only corrupted with probability 1 ⁇ 2 and, when this undesirable event, the simulator can simply rewind the adversary back to one of its previous states. After this backtracking operation, the simulator uses different random coins to simulate the view of the adversary, hoping that the inconsistent server will not be corrupted again.
  • each additive share d t is shared in a (t,n) fashion using a polynomial verifiable secret sharing and each share of d t is distributed to another server j.
  • composite order groups make the scheme of the previous mentioned article "Adaptively Secure Non-Interactive Threshold Cryptosystems" very expensive when it comes to verify signatures: as discussed by Freeman (in the article entitled “Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups", published in the conference proceedings of Eurocrypt'10, pp. 44-61, 2010.), computing a bilinear map in composite order groups is at least 50 times slower than evaluating the same bilinear map in prime order groups at the 80-bit security level (things can only get worse at higher security levels).
  • each signature is comprised of 1024 bits (or 4 times 256 bits as each signature contains 4 group elements).
  • each server should only send a single message to the combiner without having to interact with other servers at any time. For the time being, no solution combining all these properties exists.
  • references in the specification to "one embodiment”, “an embodiment”, “an example embodiment”, indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.
  • the present disclosure is directed to a signing method delivering a partial signature associated with a message, said partial signature being used in a threshold signing method, the signing method being executed on an electronic device.
  • the signing method is remarkable in that it comprises: - obtaining a partial secret key SK t being obtained from an output of a secret sharing scheme, said partial secret key SK t being equal to ⁇ ( ⁇ ), u K+1 (i) ⁇ , where elements Uj (i £ ⁇ ⁇ for all j £ ⁇ 1, ... , K + 1 ⁇ , with p being a prime number, and K being an integer greater or equal to one;
  • K elements tj with y ' £ ⁇ 1, K + 1 ⁇ and g being a generator of a group G, said group G being part of a bilinear group (G, G, G T ) with G being a group and G T being a target group; - determining from said message a vector so as to define a Groth-Sahai common reference string;
  • the signing method is remarkable in that said Groth-Sahai commitment associated with an element tj is obtained from determining
  • the signing method is remarkable in that said secret sharing scheme is a (t, n) Shamir secret sharing scheme.
  • the signing method is remarkable in that said secret sharing scheme is a non-interactive secret sharing scheme.
  • the signing method is remarkable in that said secret sharing scheme is based on Pedersen's protocol.
  • the signing method is remarkable in that said group G and said group G are permuted.
  • the signing method is remarkable in that said group G and said group G are a same group.
  • a threshold signing method delivering a threshold signature associated with a message, said signature being obtained from a combination of a set of t + 1 partial signatures provided by t + 1 devices among n devices comprising.
  • the threshold signing method is remarkable in that each partial signature being obtained through the execution of a signing method as mentioned previously, and in that said combination is defined in function of parameters defining a secret sharing scheme, said secret sharing scheme being a (t, n) threshold secret sharing scheme.
  • the threshold signing method is remarkable in that it comprises verifying said t + 1 partial signatures from a vector of verification keys, said verifying being done before performing said combination, each verification key VKi from said vector being associated with a corresponding partial secret key SK it and said verifying comprising determining if K pairing product equations hold.
  • the threshold signing method is remarkable in that said combination comprises: - determining Groth-Sahai commitments by multiplying Groth-Sahai commitments comprised in said partial signatures, using exponent's Lagrange interpolation, delivering determined Groth-Sahai commitments;
  • determining a non-interactive witness indistinguishable proof by multiplying non- interactive witness indistinguishable proofs comprised in said partial signatures, using Lagrange interpolation in the exponent, delivering determined non-interactive witness indistinguishable proof; and delivering said threshold signature comprising said determined Groth-Sahai commitments, and said determined non-interactive witness indistinguishable proof.
  • I n a preferred embodiment, it is proposed a signature verification method of a threshold signature associated with a message, said threshold signature being obtained from an execution of a previously mentioned threshold signing method.
  • the signature verification is remarkable in that it comprises verifying if K pairing equations hold.
  • the different steps of the method are implemented by a computer software program or programs, this software program comprising software instructions designed to be executed by a data processor of a relay module according to the disclosure and being designed to control the execution of the different steps of this method.
  • an aspect of the disclosure also concerns a program liable to be executed by a computer or by a data processor, this program comprising instructions to command the execution of the steps of a method as mentioned here above.
  • This program can use any programming language whatsoever and be in the form of a source code, object code or code that is intermediate between source code and object code, such as in a partially compiled form or in any other desirable form.
  • the disclosure also concerns an information medium readable by a data processor and comprising instructions of a program as mentioned here above.
  • the information medium can be any entity or device capable of storing the program.
  • the medium can comprise a storage means such as a ROM (which stands for "Read Only Memory”), for example a CD-ROM (which stands for “Compact Disc - Read Only Memory”) or a microelectronic circuit ROM or again a magnetic recording means, for example a floppy disk or a hard disk drive.
  • the information medium may be a transmissible carrier such as an electrical or optical signal that can be conveyed through an electrical or optical cable, by radio or by other means.
  • the program can be especially downloaded into an Internet-type network.
  • the information medium can be an integrated circuit into which the program is incorporated, the circuit being adapted to executing or being used in the execution of the method in question.
  • an embodiment of the disclosure is implemented by means of software and/or hardware components.
  • module can correspond in this document both to a software component and to a hardware component or to a set of hardware and software components.
  • a software component corresponds to one or more computer programs, one or more sub-programs of a program, or more generally to any element of a program or a software program capable of implementing a function or a set of functions according to what is described here below for the module concerned.
  • One such software component is executed by a data processor of a physical entity (terminal, server, etc.) and is capable of accessing the hardware resources of this physical entity (memories, recording media, communications buses, input/output electronic boards, user interfaces, etc.).
  • a hardware component corresponds to any element of a hardware unit or module (named a hardware module) capable of implementing a function or a set of functions according to what is described here below for the module concerned. It may be a programmable hardware component or a component with an integrated circuit for the execution of software, for example an integrated circuit, a smart card, a memory card, an electronic board for executing firmware etc.
  • the hardware component comprises a processor that is an integrated circuit such as a central processing unit, and/or a microprocessor, and/or an Application-specific integrated circuit (ASIC), and/or an Application-specific instruction-set processor (ASIP), and/or a graphics processing unit (GPU), and/or a physics processing unit (PPU), and/or a digital signal processor (DSP), and/or an image processor, and/or a coprocessor, and/or a floating-point unit, and/or a network processor, and/or an audio processor, and/or a multi-core processor.
  • a processor that is an integrated circuit such as a central processing unit, and/or a microprocessor, and/or an Application-specific integrated circuit (ASIC), and/or an Application- specific instruction-set processor (ASIP), and/or a graphics processing unit (GPU), and/or a physics processing unit (PPU), and/or a digital signal processor (DSP), and/or an image processor, and/or a coprocessor, and
  • the hardware component can also comprise a baseband processor (comprising for example memory units, and a firmware) and/or radio electronic circuits (that ca n comprise antennas) which receive or transmit radio signals.
  • the hardware component is compliant one or more standards such as ISO/IEC 18092 / ECMA-340, ISO/IEC 21481 / ECMA-352, GSMA, StoLPaN, ETSI / SCP (Smart Card Platform), GlobalPlatform (i.e. a secure element).
  • the hardware component is a Radio-frequency identification (RFI D) tag.
  • a hardware component comprises circuits that enable Bluetooth communications, and/or Wi-fi communications, and/or Zigbee communications, and/or USB communications and/or Firewire communications.
  • a step of obtaining an element/value in the present document can be viewed either as a step of reading such element/value in a memory unit of an electronic device or a step of receiving such element/value from another electronic device via communication means (such as for example a baseband processor, or a radio electronic circuit).
  • communication means such as for example a baseband processor, or a radio electronic circuit.
  • a hardware module configured to obtain a partial secret key SK t being obtained from an output of a secret sharing scheme, said partial secret key SK t being equal to ⁇ (0>— > U K+I (Q ⁇ > where elements Uj (i) E ⁇ ⁇ for all y E ⁇ 1, K + 1 ⁇ , with p a prime number, and K being an integer greater or equal to one;
  • K elements tj with j E ⁇ 1, ... , K + 1 ⁇ and g being a generator of a group G, said group G being part of a bilinear group (G, G, G r ) with G being a group and G r being a target group;
  • a hardware module configured to determine from said message a vector so as to define a Groth-Sahai common reference string; - a hardware module configured to determine Groth-Sahai commitments on said K + 1 elements tj with j E ⁇ 1, ... , K + 1 ⁇ from said Groth-Sahai common reference string, said Groth-Sahai commitments belonging to said group G;
  • a hardware module configured to determine a non-interactive witness indistinguishable proof comprising K(K + 1) elements, all the K(K + 1) elements belonging to said group G, said proof guarantying that said K + 1 elements tj verify K pairing equations;
  • an electronic device being able to deliver a threshold signature associated with a message, said signature being obtained from a combination of a set of t + 1 partial signatures provided by t + 1 devices among n devices.
  • the electronic device is remarkable in that it comprises a hardware module configured to combine said t + 1 partial signatures as a function of parameters defining a secret sharing scheme, said secret sharing scheme being a (t, n) threshold secret sharing scheme.
  • Figure 2 discloses a flowchart which depicts some steps performed during a generation of a partial signature associated with a message according to one embodiment of the present principles
  • Figure 3 discloses a flowchart which depicts some steps performed during a verification of a partial signature associated with a message according to one embodiment of the present principles
  • Figure 4 discloses a flowchart which depicts some steps performed during a combining process of several partial signatures associated with a message, in order to generate a signature associated with a message according to one embodiment of the present principles
  • Figure 5 discloses a flowchart which depicts some steps performed during a verification process of a signature associated with a message according to one embodiment of the present principles
  • Figure 6 discloses a flowchart which depicts some steps performed during a key distribution process according to one embodiment of the present principles
  • Figure 7 discloses a flowchart which depicts some steps performed during a generation of a partial signature associated with a message according to one embodiment of the present principles
  • Figure 8 discloses a flowchart which depicts some steps performed during a verification of a partial signature associated with a message according to one embodiment of the present principles
  • Figure 9 discloses a flowchart which depicts some steps performed during a combining process of several partial signatures associated with a message, in order to generate a signature associated with a message according to one embodiment of the present principles
  • Figure 10 discloses a flowchart which depicts some steps performed during a verification process of a signature associated with a message according to one embodiment of the present principles
  • Figure 11 discloses a flowchart which depicts some steps performed during a key distribution process according to one embodiment of the present principles
  • Figure 12 discloses a flowchart which depicts some steps performed during a generation of a partial signature associated with a message according to one embodiment of the present principles
  • Figure 13 discloses a flowchart which depicts some steps performed during a verification of a partial signature associated with a message according to one embodiment of the present principles
  • Figure 14 discloses a flowchart which depicts some steps performed during a combining process of several partial signatures associated with a message, in order to generate a signature associated with a message according to one embodiment of the present principles
  • Figure 15 discloses a flowchart which depicts some steps performed during a verification process of a signature associated with a message according to one embodiment of the present principles
  • Figure 16 presents an example of a device that can be used to perform one or several steps of methods disclosed in the present document.
  • Figure 1 discloses a flowchart which depicts some steps performed during a key distribution process according to one embodiment of the present principles.
  • public parameters par ams comprise asymmetric bilinear groups (G, G , G r ) of prime order p > 2 ⁇ with generators g E R G, g z , g r E R G as well as vectors
  • the key distribution process takes in input the following elements:
  • each player P £ (corresponding to an electronic device as the one depicted in Figure 16) performs the following steps described in Figure 1.
  • the electronic device (correspondin to a player P £ ) receives the shares (Aj(i),Bj(i)), and it verifies that lf tne latter equality does not hold, the player P £ broadcasts a complaint against player Pj.
  • any player receiving more than t complaints is immediately disqualified.
  • Each player P £ who received a complaint from another player Pj responds by returning the correct shares (A i (j ' ),B i (jy). If any of these new shares fails to satisfy the equation ⁇ player P £ is disqualified.
  • Q c ⁇ 1, ...,ri ⁇ be the set of non-disqualified players at the end of the step 103.
  • PK g ir
  • Figure 2 discloses a flowchart which depicts some steps performed during a generation of a partial signature associated with a message according to one embodiment of the present principles.
  • the electronic device i determines, from the bits
  • step referenced 302 it checks that the following pairing equation is verified by the elements comprised in the obtained partial signature:
  • step 301 e.g. the format of the obtained partial signature is not correct
  • step 302 e.g. the pairing equation is not verified
  • a value 0 is delivered by the electronic device. Otherwise, if no error occurs in step 301 and step 302, the electronic device outputs a value 1.
  • Figure 4 discloses a flowchart which depicts some steps performed during a combining process of several partial signatures associated with a message, in order to generate a signature associated with a message according to one embodiment of the present principles.
  • Figure 5 discloses a flowchart which depicts some steps performed during a verification process of a signature associated with a message according to one embodiment of the present principles.
  • an electronic device in a step referenced 501, parses ⁇ as (C z , C r , ⁇ , ⁇ 2 ) ⁇ G 4 x G 2 .
  • a step referenced 502 it returns/outputs an information (for example a value equal to 1) if the pair ( ⁇ 1 , ⁇ 2 ) satisfies the pairing equation:
  • ECClcfl ' 1 E (C z z ). E (C r r ). E(f, it 1 ). E( f M , it 2 ), That can also be written as follows
  • the adversary obtains (A(j), B (i)) and, not only (g ⁇ A ⁇ , g ⁇ B( - 1 ⁇ )- I n any case, each player only needs to store two elements of ⁇ ⁇ whereas solutions like the one described in the previously mentioned article "Simplified Threshold RSA with Adaptive and Proactive Security", incur the storage of 0 (n) elements at each player. It should be noted that, while it is assumed that players store ( ⁇ l (i), 5(0) a r, d erase all intermediate values (like the polynomials Ai [X] and Bi [X]) at the end of the key generation phase, these erasures are only motivated by efficiency considerations and they do not affect the security in any way.
  • Figure 6 discloses a flowchart which depicts some steps performed during a key distribution process according to one embodiment of the present principles.
  • Figure 6 to 10 describe another embodiment of the present principles that relies on the weaker Decision Linear (DLI N) assumption.
  • each player P £ performs the following steps described in Figure 6.
  • any player receiving more than t complaints is immediately disqualified.
  • Q c ⁇ 1, ... , n ⁇ be the set of non-disqualified players at the end of the step 603.
  • Figure 7 discloses a flowchart which depicts some steps performed during a generation of a partial signature associated with a message according to one embodiment of the present principles.
  • Figure 8 discloses a flowchart which depicts some steps performed during a verification of a partial signature associated with a message according to one embodiment of the present principles.
  • step 801 e.g. the format of the obtained partial signature is not correct
  • step 802 e.g. the pairing equations are not verified
  • a value 0 is delivered by the electronic device. Otherwise, if no error occurs in step 801 and step 802, the electronic device outputs a value 1.
  • Figure 9 discloses a flowchart which depicts some steps performed during a combining process of several partial signatures associated with a message, in order to generate a signature associated with a message according to one embodiment of the present principles.
  • Figure 10 discloses a flowchart which depicts some steps performed during a verification process of a signature associated with a message according to one embodiment of the present principles.
  • an electronic device in a step referenced 1001, parses ⁇ as (C z , C r , C UJ 7r llJ 7r 12 ,7r 13j ⁇ 21 ⁇ 22 ⁇ 23) ⁇
  • a step referenced 1002 it outputs (or returns) a value equal to 1 if the two following pairing equations are satisfied/verified by the electronic device (otherwise, if one or the two pairing equations are not verified, then a value 0 is delivered by the electronic device):
  • each element of G can have a 256-bit (respectively 512-bit) representation, so that each signature fits within 5376 bits.
  • each group element requires a 512-bit representation, so that the signature length increases to 7680 bits.
  • the second embodiment is thus somewhat less efficient than the first one (by a factor of 2.5 as far as the signature length is concerned). However, it relies on a weaker hardness assumption while retaining the main advantages of the first embodiment (i.e., constant-size private key shares, round optimal distributed key generation and non-interactivity of the signing process).
  • each signature is comprised of (K + Y) (2K + 1) group elements. More precisely, the commitments require (K + l) 2 elements of G and the proof elements take K(K + 1) elements of G.
  • Figures 11 to 15 describe another embodiment of the present principles that relies on the Decision Linear (DLIN) assumption. It is obtained by exchanging the roles of the groups G and G in the second previous embodiment. Namely, Groth-Sahai commitments take place in G whereas proof elements ⁇ belong to G.
  • DLIN Decision Linear
  • FIG. 11 discloses a flowchart which depicts some steps performed during a key distribution process according to one embodiment of the present principles.
  • the key distribution process takes in input the following elements:
  • each player P £ performs the following steps described in Figure 11.
  • the electronic device (corresponding to the player P) receives
  • the public key consists of
  • Figure 12 discloses a flowchart which depicts some steps performed during a generation of a partial signature associated with a message according to one embodiment of the present principles.
  • a step referenced 1204 it generates a non-interactive witness indistinguishable proof ⁇ (tj l i ,nj 2: i,nj 3 i ) ⁇ that the triple (z £ , £ , u £ ) £ G 3 satisfies the two following verification equations
  • Figure 13 discloses a flowchart which depicts some steps performed during a verification of a partial signature associated with a message according to one embodiment of the present principles.
  • M M[l] ...M[L] E ⁇ 0,1 ⁇ L
  • step 1301 e.g. the format of the obtained partial signature is not correct
  • step 1302 e.g. the pairing equations are not verified
  • a value 0 is delivered by the electronic device. Otherwise, if no error occurs in step 1301 and step 1302, the electronic device outputs a value 1.
  • Figure 14 discloses a flowchart which depicts some steps performed during a combining process of several partial signatures associated with a message, in order to generate a signature associated with a message according to one embodiment of the present principles.
  • a re-randomization process is applied to the obtained vector (C ⁇ , C ⁇ ', C ⁇ , ⁇ ' , ⁇ 1 ' 2 , ⁇ 3 , ⁇ 2 ' 1 , ⁇ 2 ' 2 , ⁇ 23 ).
  • the resulting re-randomized full signature ⁇ ⁇ , ⁇ , , ⁇ , ⁇ , ⁇ , ⁇ 13 , ⁇ 21 , ⁇ 22 , ⁇ 23 ) is then outputted.
  • Figure 15 discloses a flowchart which depicts some steps performed during a verification process of a signature associated with a message according to one embodiment of the present principles.
  • M M[l] ... M[L] E ⁇ 0,1 ⁇ L
  • a putative signature ⁇ an electronic device, in a step referenced 1501, parses ⁇ as follows (3 ⁇ 4, C f , C Qj n llt ⁇ 12 , ⁇ 13 , ⁇ 21 , ⁇ 22 , ⁇ 23 ) .
  • a step referenced 1502 it outputs (or returns) a value equal to 1 if the two following pairing equations are verified (otherwise, if one or the two pairing equations are not verified, then a value 0 is delivered by the electronic device):
  • E(gi, (le, le, ⁇ ) 1 E(g z , 3 ⁇ 4).
  • E ( ⁇ 13 , / ⁇ ) and E (3 ⁇ 4i, (le, 1& ⁇ ) ) _1 £( i z , 3 ⁇ 4.
  • E (n 23 , f M ⁇ ) where
  • a fourth embodiment can be obtained by similarly exchanging the roles of G and G in the first embodiment.
  • signatures comprising 2560-bits are obtained.
  • the first and second embodiments are thus the most efficient ones under the SXDH and DLIN assumptions, respectively, as far as the signature length is concerned.
  • the distributed key generation phase uses Pedersen's protocol (as described in the article entitled “Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing” , in the conference proceedings of Crypto'91, LNCS 576, pp. 129-140, or, more precisely, a variant with two generators).
  • each player verifiably shares a random secret using Pedersen's verifiable secret sharing - where verification is enabled by having all parties broadcast commitments to their secret polynomials - and the final secret key shares are obtained by summing up the shares of non-disqualified players.
  • Pedersen's protocol is its efficiency and its simplicity: when all parties follow the protocol, a single communication round is needed.
  • Pedersen's protocol does not guarantee the uniform distribution of public keys: as shown in the article entitled “Secure Distributed Key Generation for Discrete-Log Based Cryptosystems” , published in the conference proceedings of Eurocrypt'99, LNCS 1592, pp. 295- 310, 1999, even a static adversary can bias the distribution of public keys by corrupting only two players.
  • Pedersen's protocol can still be safely used in certain applications as explained in the article entitled “Secure Applications of Pedersen's Distributed Key Generation Protocol", published in the conference proceedings of CT-RSA'03, LNCS 2612, pp.
  • the scheme can be seen as a threshold version of (or a variant of) the signature scheme presented in the article entitled "Signatures resilient to continual leakage on memory and computgtion" by T. Malkin et al., and published in the conference proceedings of TCC'll, LNCS 6597, pp. 89-106.
  • the signer In order to sign an L -bit message E ⁇ 0,1 ⁇ L , the signer generates a kind of non-interactive proof of knowledge of (a, b), or, more precisely, a non-interactive proof of knowledge of(g a , g b ). To this end, he forms a Groth-Sahai common reference string (f, f M ) using the bits of the message M, according to a technique suggested by Malkin et al. in the previous mentioned article entitled "Signgtures resilient to continugl legkgge on memory gnd computgtion" .
  • Figure 16 presents an example of a device that can be used to perform one or several steps of methods disclosed in the present document.
  • Such device referenced 1600 comprises a computing unit (for example a CPU, for "Central Processing Unit"), referenced 1601, and one or more memory units (for example a RAM (for "Random Access Memory”) block in which intermediate results can be stored temporarily during the execution of instructions a computer program, or a ROM block in which, among other things, computer programs are stored, or an EEPROM (“Electrically-Erasable Programmable Read-Only Memory”) block, or a flash memory block) referenced 1602. Computer programs are made of instructions that can be executed by the computing unit.
  • Such device 1600 can also comprise a dedicated unit, referenced 1603, constituting an input-output interface to allow the device 1600 to communicate with other devices.
  • this dedicated unit 1603 can be connected with an antenna (in order to perform communication without contacts), or with serial ports (to carry communications "contact”).
  • the arrows in Figure 16 signify that the linked unit can exchange data through buses for example together.
  • some or all of the steps of the method previously described can be implemented in hardware in a programmable FPGA ("Field Programmable Gate Array”) component (which is an integrated circuit designed to be configured by a customer or a designer after manufacturing) or ASIC ("Application-Specific Integrated Circuit") component.
  • a programmable FPGA Field Programmable Gate Array
  • ASIC Application-Specific Integrated Circuit
  • threshold signatures were also used to implement distributed storage systems (like the system OceanStore described in the article entitled “OceanStore: An Architecture for Global-Scale Persistent Storage", by J. Kubiatowicz et a I., and published in the conference proceedings of ASPLOS 2000, pp. 190-201).
  • Non-interactive solutions can also serve as building blocks for metering systems (as detailed in the article entitled “Some Applications of Threshold Signature Schemes to Distributed Protocols” by V. Daza et al., and published on the Cryptology ePrint Archive: Report 2002/081) or e-commerce platforms (as the one described in the article entitled “Practical PIR for electronic commerce” by R. Henry et al., and published in the conference proceedings of ACM Conference on Computer and Communications Security (ACM-CCS) 2011, pp. 677-690. Therefore, the present disclosure can be applied in these contexts.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Storage Device Security (AREA)

Abstract

L'invention concerne, dans un mode de réalisation, un procédé de signature distribuant une signature partielle associée à un message, ladite signature partielle étant utilisée dans un procédé de signature à seuil, le procédé de signature étant exécuté sur un dispositif électronique. Le procédé de signature est caractérisé en ce qu'il comporte les étapes consistant à: - obtenir une clé secrète partielle SK i obtenue à partir de la sortie d'un schéma de partage de secrets, ladite clé secrète partielle SK i étant égale à {u1 (i), uK+1 (i)}, où les éléments uj (i) ∈ Zp quel que soit j ∈ {1,..., K + 1}, p étant un nombre premier et K étant un entier supérieur ou égal à un; - déterminer à partir de ladite clé partielle, K éléments tj = g -uj(i) , avec j ∈ {1,...,K + 1} and g étant un générateur d'un groupe G, ledit groupe G faisant partie d'un groupe bilinéaire (G, Ĝ, G T ) Ĝ étant un groupe et G T étant un groupe de destination ; - déterminer à partir dudit message un vecteur de façon à définir une chaîne de référence commune de Groth-Sahai; - déterminer des engagements de Groth-Sahai sur lesdits K + 1 éléments t j avec j ∈ {1,...,Κ + 1} à partir de ladite chaîne de référence commune de Groth-Sahai, lesdits engagements de Groth-Sahai appartenant audit groupe G; et - déterminer une preuve non interactive indiscernable par un témoin comportant K(K + 1) éléments, les K(K + 1) éléments appartenant tous audit groupe Ĝ, ladite preuve garantissant que lesdits K + 1 éléments tj vérifient K équations d'appariement; - distribuer ladite signature partielle associée audit message, ladite signature partielle comportant lesdits engagements de Groth-Sahai et ladite preuve non interactive indiscernable par un témoin.
PCT/EP2015/052681 2014-02-10 2015-02-10 Procédés de signature pour distribuer des signatures partielles et/ou des signatures-seuils, procédés de validation correspondants et dispositifs électroniques correspondants Ceased WO2015118160A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP14305175.3 2014-02-10
EP14305175 2014-02-10

Publications (1)

Publication Number Publication Date
WO2015118160A1 true WO2015118160A1 (fr) 2015-08-13

Family

ID=50721727

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2015/052681 Ceased WO2015118160A1 (fr) 2014-02-10 2015-02-10 Procédés de signature pour distribuer des signatures partielles et/ou des signatures-seuils, procédés de validation correspondants et dispositifs électroniques correspondants

Country Status (1)

Country Link
WO (1) WO2015118160A1 (fr)

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106452745A (zh) * 2016-09-27 2017-02-22 中国农业大学 一种秘密数据共享的验证方法及装置
WO2020012079A1 (fr) * 2018-07-11 2020-01-16 Ledger, Sas Gouvernance de sécurité du traitement d'une requête numérique
CN114730420A (zh) * 2019-08-01 2022-07-08 科恩巴斯公司 用于生成签名的系统和方法
CN114826603A (zh) * 2022-03-22 2022-07-29 上海交通大学 多人链下状态通道中信息安全保护实现方法及系统
US11411721B2 (en) * 2019-09-27 2022-08-09 Cypherium Blockchain Inc. Systems and methods for selecting and utilizing a committee of validator nodes in a distributed system
JP2022547876A (ja) * 2019-09-04 2022-11-16 ジーケーエイト リミテッド メッセージの署名のためのシステムおよび方法
JP2023519081A (ja) * 2020-01-15 2023-05-10 プラネットウェイ コーポレイション 拡張可能なサーバを用いるデジタル署名システム

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2006203754A (ja) * 2005-01-24 2006-08-03 Nippon Telegr & Teleph Corp <Ntt> 閾値つき電子署名の方法、その方法を用いた装置およびプログラム

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2006203754A (ja) * 2005-01-24 2006-08-03 Nippon Telegr & Teleph Corp <Ntt> 閾値つき電子署名の方法、その方法を用いた装置およびプログラム

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
"LECTURE NOTES IN COMPUTER SCIENCE", vol. 7194, 1 January 2012, SPRINGER BERLIN HEIDELBERG, Berlin, Heidelberg, ISBN: 978-3-54-045234-8, ISSN: 0302-9743, article BENOÎT LIBERT ET AL: "Non-interactive CCA-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions", pages: 75 - 93, XP055131489, DOI: 10.1007/978-3-642-28914-9_5 *
HARN L: "GROUP-ORIENTED (T, N) THRESHOLD DIGITAL SIGNATURE SCHEME AND DIGITAL MULTISIGNATURE", IEE PROCEEDINGS: COMPUTERS AND DIGITAL TECHNIQUES, IEE, GB, vol. 141, no. 5, PART E, 1 September 1994 (1994-09-01), pages 307 - 313, XP000477727, ISSN: 1350-2387, DOI: 10.1049/IP-CDT:19941293 *
SARAH MEIKLEJOHN ET AL: "Limitations on Transformations from Composite-Order to Prime-Order Groups: The Case of Round-Optimal Blind Signatures", INTERNATIONAL ASSOCIATION FOR CRYPTOLOGIC RESEARCH,, vol. 20100920:191008, 20 September 2010 (2010-09-20), pages 1 - 28, XP061004242 *

Cited By (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106452745A (zh) * 2016-09-27 2017-02-22 中国农业大学 一种秘密数据共享的验证方法及装置
US11757660B2 (en) 2018-07-11 2023-09-12 Ledger, Sas Security governance of the processing of a digital request
FR3085815A1 (fr) * 2018-07-11 2020-03-13 Ledger Gouvernance de securite du traitement d'une requete numerique
CN112970226A (zh) * 2018-07-11 2021-06-15 雷吉公司 数字请求的处理的安全管理
WO2020012079A1 (fr) * 2018-07-11 2020-01-16 Ledger, Sas Gouvernance de sécurité du traitement d'une requête numérique
CN114730420A (zh) * 2019-08-01 2022-07-08 科恩巴斯公司 用于生成签名的系统和方法
JP2022547876A (ja) * 2019-09-04 2022-11-16 ジーケーエイト リミテッド メッセージの署名のためのシステムおよび方法
JP7564868B2 (ja) 2019-09-04 2024-10-09 ギャラクシー デジタル トレーディング エルエルシー メッセージの署名のためのシステムおよび方法
US11411721B2 (en) * 2019-09-27 2022-08-09 Cypherium Blockchain Inc. Systems and methods for selecting and utilizing a committee of validator nodes in a distributed system
US12443569B2 (en) 2019-09-27 2025-10-14 Cypherium Blockchain Inc. Systems and methods for selecting and utilizing a committee of validator nodes in a distributed system
JP2023519081A (ja) * 2020-01-15 2023-05-10 プラネットウェイ コーポレイション 拡張可能なサーバを用いるデジタル署名システム
JP7602545B2 (ja) 2020-01-15 2024-12-18 プラネットウェイ コーポレイション 拡張可能なサーバを用いるデジタル署名システム
CN114826603A (zh) * 2022-03-22 2022-07-29 上海交通大学 多人链下状态通道中信息安全保护实现方法及系统
CN114826603B (zh) * 2022-03-22 2023-11-14 上海交通大学 多人链下状态通道中信息安全保护实现方法及系统

Similar Documents

Publication Publication Date Title
Gennaro et al. One round threshold ECDSA with identifiable abort
Libert et al. Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares
US11671255B2 (en) Threshold digital signature method and system
WO2015118160A1 (fr) Procédés de signature pour distribuer des signatures partielles et/ou des signatures-seuils, procédés de validation correspondants et dispositifs électroniques correspondants
US9979551B2 (en) Signing method delivering a partial signature associated with a message, threshold signing method, signature verification method, and corresponding computer program and electronic devices
Schindler et al. Ethdkg: Distributed key generation with ethereum smart contracts
Gennaro et al. Secure distributed key generation for discrete-log based cryptosystems
EP2860905A1 (fr) Méthode pour chiffrer un message au moyen d&#39;une fonction de chiffrage avec clé, et appareil électronique et produit programme d&#39;ordinateur correspondants
Hirt et al. Robust multiparty computation with linear communication complexity
US20170061833A1 (en) Method for ciphering and deciphering digital data, based on an identity, in a multi-authorities context
WO2019034986A1 (fr) Procédé mis en œuvre par ordinateur de génération de coffre-fort réparti
WO2016049406A1 (fr) Procédé et appareil pour signatures à seuil non interactives sécurisées
US20150100794A1 (en) Method for signing a set of binary elements, and updating such signature, corresponding electronic devices and computer program products
CN116391346A (zh) 秘密分享的重新分发
WO2014205570A1 (fr) Protocole d&#39;agrément de clé
US9356783B2 (en) Method for ciphering and deciphering, corresponding electronic device and computer program product
Bacho et al. Network-agnostic security comes (almost) for free in DKG and MPC
CA2730626C (fr) Signature numerique amelioree et protocoles d&#39;accord de clef
CN108964906B (zh) 协同ecc的数字签名方法
EP3627367A1 (fr) Attestation résistante à la subversion pour des environnements d&#39;exécution sécurisés
Yang et al. Lis: Lightweight signature schemes for continuous message authentication in cyber-physical systems
Erwig et al. Large-scale non-interactive threshold cryptosystems in the yoso model
Pan et al. Multi-signatures for ECDSA and Its Applications in Blockchain
Pettit Efficient threshold-optimal ECDSA
CN116961917B (zh) 一种基于ecdsa的多方协同门限签名方法、装置和系统

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 15703289

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 15703289

Country of ref document: EP

Kind code of ref document: A1