WO2015118160A1 - Signing methods for delivering partial signatures, and/or threshold signatures, corresponding verification methods, and corresponding electronic devices - Google Patents

Abstract

In one embodiment, it is proposed 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 keySK_i being obtained from an output of a secret sharing scheme, said partial secret keySK_i being equal to {u1 (i), u_K+1 (i)}, where elements uj (i) ∈ Zpfor allj ∈ {1,...,K + 1}, withp being a prime number, andK being an integer greater or equal to one; - determining from said partial key,K elementstj = g^-uj(i), withj ∈ {1,...,K + 1} andg being a generator of a group G, said group G being part of a bilinear group (G, Ĝ, G_T) with Ĝ 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; - determining Groth-Sahai commitments on saidK + 1 elementst_j withj ∈ {1,...,Κ + 1} from said Groth-Sahai common reference string, said Groth-Sahai commitments belonging to said group G; and - determining a non-interactive witness indistinguishable proof comprisingK(K + 1) elements, all theK(K + 1) elements belonging to said group Ĝ, said proof guarantying that saidK + 1 elementstj verifyK pairing equations; - delivering said partial signature associated with said message, said partial signature comprising said Groth-Sahai commitments, and said non-interactive witness indistinguishable proof.

Description

SIGNING METHODS FOR DELIVERING PARTIAL SIGNATURES, AND/OR THRESHOLD SIGNATURES, CORRESPONDING VERIFICATION METHODS, AND CORRESPONDING

ELECTRONIC DEVICES

Technical Field The disclosure relates to cryptography techniques, and more precisely to threshold signature techniques, where the signing capabilities are distributed over several devices.

Background

This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.

In 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. So far, most existing threshold signature schemes either require interaction among the servers during the signing process or only provide security against static corruptions. For example, 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. 207-220, 2000), by Katz and Yung (in the article entitled "Threshold Cryptosystems Based on Factoring", published in the conference proceedings of Asiacrypt'02, LNCS series, pp. 199-205) and by Boldyreva (in the article entitled "Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap- Diffie Hellmgn-Group Signgture Scheme", published in the conference proceedings of Public- Key Cryptography 2003 (PKC'03), LNCS 2567, pp. 31-46). Moreover, the latter construction described by Boldyreva was subsequently generalized by Wee (in the article entitled "Threshold and Revocation Cryptosystems via Extractable Hash Proofs", published in the conference proceedings of Eurocrypt'll, LNCS 6632, pp. 589-609). However, these solutions are only known to resist static adversaries, who have to choose which servers they want to corrupt before even seeing the public key.

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). Other constructions were suggested for example in the article entitled "Adaptive Security in the Threshold Setting: From Cryptosystems to Signature Schemes" by A. Lysyanskaya, C. Peikert, and published in the conference proceedings of Asiacrypt'01, LNCS 2248, pp. 331-350, but the results described in the previously mentioned articles "Adaptive Security for Threshold Cryptosystems" , "Adaptively- Secure Distributed Public-Key Systems" and "Adaptively-Secure Optimal-Resilience Proactive RSA", are more promising to avoid interaction. The reason is that they can be applied to distributed RSA signatures, which are deterministic and thus potentially easier to thresholdize in the non-interactive setting. Indeed, unlike the threshold Schnorr signature described in the article entitled "Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography" , by M. Abe, S. Fehr, and published in the conference proceedings of Crypto'04, LNCS 3152, pp. 317-334, threshold RSA signatures do not require the servers to jointly generate a randomized signature component in a first round before starting a second round.

The constructions depicted in the previously mentioned articles "Adgptive Security for Threshold Cryptosystems" , "Adgptively-Secure Distributed Public-Key Systems" and "Adgptively- Secure Optimgl-Resilience Progctive RSA", rely on a technique, called the "single inconsistent player" (SIP) technique, which inherently requires interaction. The SIP technique basically consists in converting a i-out-of-n secret sharing into an n-out-of-n secret sharing in such a way that, in the latter case, there is only one server whose internal state cannot be consistently revealed to the adversary. Since this server is chosen at random by the simulator among the n severs, it is only corrupted with probability ½ 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.

In 2006, Almansa, Damgard and Nielsen, in the article entitled "Simplified Threshold RSA with Adaptive and Proactive Security", published in the conference proceedings of Eurocrypt'06, LNCS 4004, pp. 593-611, showed a variant of Rabin's threshold RSA signatures (as depicted in the article "A Simplified Approach to Threshold and Proactive RSA", published in the conference proceedings of Crypto'98, LNCS series, pp. 89-104) and proved them adaptively secure using the SIP technique as well as ideas from the previously mentioned articles "Adaptively-Secure Distributed Public-Key Systems" and "Adaptively-Secure Optimal-Resilience Proactive RSA". While the SIP technique does provide adaptively secure threshold RSA signatures, these fall short of minimizing the amount of interaction. The constructions described in the previously mentioned articles "Adaptively-Secure Distributed Public-Key Systems" and "Adaptively-Secure Optimal-Resilience Proactive RSA" proceed by turning a (t,n) polynomial secret sharing into a (t, t) additive secret sharing by first selecting a pool of at least t participants. However, if only one of these fails to provide a valid contribution to the signing process, the whole protocol must be restarted from scratch. The protocol of Almansa (described in the previously mentioned article "Simplified Threshold RSA with Adaptive and Proactive Security") proceeds by sharing an RSA private key in an additive (n, n) fashion (i.e. the private RSA exponent d is split into shares d_lt ... , d_n such that d =∑_£ d_t ). In turn, 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. This is done in such a way that, if one participant fails to provide a valid RSA signature share H(M)^di, the missing signature share can be re-constructed by running the reconstruction algorithm of the verifiable secret sharing scheme that was used to share d_t. The first drawback of this approach is that it is only non- interactive when all players are honest: if even only one additive signature share H(M)^di is missing, the remaining participants have to conduct a second round of interaction to reconstruct the missing signature shares H(M)^di. Another drawback of this approach is that each player has to store 0(n) values where n is the number of players (as each player has to store a polynomial share of other players' additive share). Ideally, it should be better to have a solution where each player only stores 0 (1) elements, regardless of the number of players.

In 2011, Libert and Yung, in the article entitled "Adaptively Secure Non-Interactive Threshold Cryptosystems" , published in the conference proceedings of Theoretical Computer Science, vol. 478, pp. 76-100, suggested an adaptively secure threshold variant of Waters signatures (as depicted in the article entitled "Efficient Identity-Based Encryption Without Random Oracles", published in the conference proceedings of Eurocrypt'05, LNCS series) using groups of composite order and the techniques of Lewko and Waters developed in the article entitled "New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts", published in the conference proceedings of TCC 2010, LNCS 5978, pp. 455-479. The use of composite order groups makes 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). The techniques of Lewko (described in the article entitled "Tools for Simulgting Fegtures of Composite Order Bilinegr Groups in the Prime Order Setting", published in the conference proceedings of Eurocrypt 2012, LNCS 5978, pp. 318-33, 2012.) can be used to adapt the construction of the scheme described in previous mentioned article "Adgptively Secure Non- Intergctive Threshold Cryptosystems" to the setting of prime-order groups. In the resulting construction, each signature consists of 6 group elements. The use of asymmetric bilinear maps allows reducing the signature size to 4 group elements. Hence, the most efficient adaptively secure non-interactive threshold signature is currently the construction obtained by applying the techniques described in the article entitled "Shorter IBE and Signatures via Asymmetric Pairings", published in the conference proceedings of Pairing 2012, LNCS 7708, pp. 122-140, to the system described in the previous mentioned article "Adgptively Secure Non-lntemctive Th resh old Cryp tos ys terns". Concretely, at the 128-bit security level, each signature is comprised of 1024 bits (or 4 times 256 bits as each signature contains 4 group elements). However, the techniques described in the previous mentioned article "Shorter IBE gnd Signgtures vig Asymmetric Pgirings" seem hardly compatible with a round-optimal distributed key generation phase. The reason is that the techniques described in the previous mentioned article "Shorter IBE gnd Signgtures vig Asymmetric Pgirings" require to generate public keys containing pairs of matrices of the form g^A E G^nxn and g^{A 1} E G^nxn, for some matrix A E Έ ~^η with G a cyclic group, g a generator of G and a prime number. Indeed it is not clear how these non-linear operations can be achieved in a round-optimal distributed manner (let alone with adaptive security). The problem of devising a new construction in the standard model which is as efficient as the combination of the techniques of the previous mentioned articles "Shorter IBE gnd Signgtures vig Asymmetric Pgirings" and "Adgptively Secure Non-lntemctive Threshold Cryptosystems" is now considered. I n particular, it is a goal of one embodiment of the disclosure to retain private key shares of 0(1) size (no matter how many players are involved in the protocol). Moreover, it is a goal of one embodiment of the disclosure not to rely on a trusted dealer in the key generation phase. The public key should be jointly generated by all players while guaranteeing the security of the scheme against an adaptive adversary. Moreover, it is a goal of one embodiment of the disclosure not to assume reliable erasures in the security proof. This means that, whenever the adversary corrupts a player, it learns the entire history of that player.

At the same time, the key generation phase should be as communication-efficient as possible. Ideally, a single communication round should be needed when the players follow the protocol. Finally, it is a goal of one embodiment of the disclosure to avoid interaction during the distributed signing process: 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.

It is a goal of one embodiment of the disclosure to provide an adaptively secure non- interactive threshold signatures in the standard model, where the key generation phase only requires one round when all players are honest.

Summary of the disclosure

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;

- determining from said partial key, 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;

- determining Groth-Sahai commitments on said K + 1 elements tj with j Ε {1, ... , Κ + Ϊ] from said Groth-Sahai common reference string, said Groth-Sahai commitments belonging to said group G; and

- determining 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;

- delivering said partial signature associated with said message, said partial signature comprising said Groth-Sahai commitments, and said non-interactive witness indistinguishable proof.

In a preferred embodiment, the signing method is remarkable in that when said message M comprises L binary elements, with L an integer greater or equal to one, said vector corresponds to /_M = /₀- Π;=ι /ί with vectors^■ comprising K+l elements of said group G, and said Groth-Sahai common reference string corresponds to K elements v₁, ... , v_K, f_M), with elements Vj E G^K+1 with £ {1, ... , K}.

In a preferred embodiment, the signing method is remarkable in that said Groth-Sahai commitment associated with an element tj is obtained from determining

1_G, tj). ¾^rfe) · ΪΜ^Κ+1_> with elements y_fc being random elements, for k E {1, ... , K + 1}.

In a preferred embodiment, the signing method is remarkable in that said secret sharing scheme is a (t, n) Shamir secret sharing scheme.

In a preferred embodiment, the signing method is remarkable in that said secret sharing scheme is a non-interactive secret sharing scheme. In a preferred embodiment, the signing method is remarkable in that said secret sharing scheme is based on Pedersen's protocol. In a preferred embodiment, the signing method is remarkable in that said group G and said group G are permuted.

In a preferred embodiment, the signing method is remarkable in that said group G and said group G are a same group.

In a preferred embodiment, it is proposed 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.

In a preferred embodiment, 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.

In a preferred embodiment, 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.

According to an exemplary implementation, 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.

Consequently, 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. For example, 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. Furthermore, 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.

Alternately, 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.

According to one embodiment, an embodiment of the disclosure is implemented by means of software and/or hardware components. From this viewpoint, the term "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.).

Similarly, 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. In a variant, 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. Moreover, 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. I n one embodiment, 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). I n a variant, the hardware component is a Radio-frequency identification (RFI D) tag. In one embodiment, 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.

It should be noted that 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). I n a preferred embodiment, it is proposed an electronic device being able to deliver a partial signature associated with a message, said partial signature being used in a threshold signing scheme. The electronic device is remarkable in that it comprises:

- 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>—_>^UK+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;

- a hardware module configured to determine from said partial key, 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;

- a hardware module configured to deliver said partial signature associated with said message, said partial signature comprising said Groth-Sahai commitments, and said non-interactive witness indistinguishable proof. In a preferred embodiment, it is proposes 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.

Brief description of the drawings

The above and other aspects of the disclosure will become more apparent by the following detailed description of exemplary embodiments thereof with reference to the attached drawings in which: - Figure 1 discloses a flowchart which depicts some steps performed during a key distribution process according to one embodiment of the present principles;

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.

Detailed description

Figure 1 discloses a flowchart which depicts some steps performed during a key distribution process according to one embodiment of the present principles.

In the following notations, for each h E G, and any vector g = {g₁, g₂) ε <£>², where G, G are cyclic groups, E(g, h) corresponds to the vector (e(g₁, h), e (g_2> h)) E G_j , where G_T is a target group (defined according to the choice of the bilinear map (or pairing) e: G x G→ G_T).

Indeed, it is assumed that 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

/⁼ (f> 9^{e a nc}' fi⁼ ifi' dd^eR for ί = 0 to L, where L E poZy(l), for some security parameter l.

The key distribution process takes in input the following elements:

- params = {(G, G , G_T ), g, g_z, g_r , f, { /.}_i=1} ;

- a security parameter l;

the integers t, n E M such that n≥ 2t + 1. Then, each player P_£ (corresponding to an electronic device as the one depicted in Figure 16) performs the following steps described in Figure 1.

In a step, referenced 101, each player P_£ shares a random pair (a_i0,b_i0) according to the following process: pick two random polynomials Ai[X] = a_iQ + a_tlX +— h a_itX^t and S_£| | = b_iQ + b_ixX +— V b_itX^t of degree t, and it broadcasts the element W_i( = g_z^{au '} .g_r^bu , for all £ E {0,...,t};

for all j £ {0, ...,n], sending (l_j /), H_£ /)) to the player Pj.

In a step referenced 102, 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.

In a step referenced 103, 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. Let Q c {1, ...,ri} be the set of non-disqualified players at the end of the step 103.

The public key PK is obtained as PK = g_ir where g = X[_ieQW_i0 = g_z^∑ieQ^ai0.g_r^∑ieQ^bi0.

Each player P_£ locally determines its private key SK_t as: SKi = (,Α(ί),β(θ) = (∑_;

ερβ(0)^ar|d anyone can compute his corresponding verification key which is VK_t = V_t = §_ζ^Αω.§_τ^Βίί = Π; eg

·

Any disqualified player Pj with j £ {1, ... , n}\Q is implicitly assigned the share SK_t = (0,0), and the matching verification key VK_t = lg.

The vector of private key shares \sSK = (SK_lt ...,SK_n) and the corresponding vector of verification keys VK = (VK^ ... , VK_n). The public key consists of PK = (params.g^

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.

In order to perform such generation, an electronic device must obtain a L-bit message M = M[l] ...M[L] £ {0,1}^L, as well as a secret key (that can be generated according to the process of Figure l)Stf_£ = (A i),B(() E Ί².

Then, the electronic device, noted electronic device i, determines, in a step referenced 201, the following values z_£ = g^~A^ and r_£ = g^~B^ that belong to the group G. These values can also be obtained by reading them from a memory unit (as they can be pre-computed).

Then, in a step referenced 202, the electronic device i determines, from the bits

M[l] ...M[L] E {0,1} of the message M, the vector f_M = so as to assemble a Groth-Sahai common reference string (or CRS) f_M = (f,f_M)-

In a step referenced 203, the electronic device uses such Groth-Sahai CRS f_M = (f,f_M , in order to determine the following Groth Sahai commitments to the elements z_£ and r_£ respectively :

C_z,i = -G>^zi)-f^{Vz i}-fM^{Z'2'1 and} Cr.i = -G>n)-f^{Vr i}-fM^{r;Z' wnere tne} elements v_z> ,^νζ,2,ί_>^vr,i,i^and^vr,2,i^are random values belonging toZ_p. Moreover, the electronic device determines a non-interactive witness indistinguishable proof n_{l i},n_2ii) E G² that the pair (z_£, r_£) £ G² satisfies the following verification equation: l_Gr = e(z_£,_z).e(r_£,,g_r).e(#,_£)

This proof is obtained by determining {_1:i,_2:i) = (gz^~Vz,1,i- 9r^~Vr,1,i_> §z^~Vz'²'ⁱ-9r^~Vr'²'ⁱ) ·

Then, the electronic device delivers the partial signature^ = (C_z<£jC_r<£j7r_1<£j7r_2<£) £ G⁴ x 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.

The electronic device obtains before the execution of such verification a message comprising L-bits M = M[l] ... M[L] E {0,1}^L and a partial signature σ_έ.

In a step referenced 301, the electronic device checks the format of the partial signature. More precisely, it checks that a_t can be written as follows a_t = (C_{z i}, Ο_τ._ί, π_{1 ί}, π_2ιί) ε G⁴ x G².

In a step referenced 302, it checks that the following pairing equation is verified by the elements comprised in the obtained partial signature:

In another embodiment it checks the following equation:

1<G_T =

Indeed, it can save one inversion operation in the group G_T. If an error occurs either in step 301 (e.g. the format of the obtained partial signature is not correct), or in 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. Given a (t + 1) set of valid shares {(i, ^)}_iES, an electronic device parses, in a step referenced 401, each share σ_έ as (C_{z ,}i, C_r,i' 7¾, 7¾) ε G⁴ x G² for all i E S. Then it computes, in a step referenced 402:

{L_z, L_r, n , n ) - {[ [_ies_{z i} , l lies t>_{r i} , l hes ^ Λ hes ¾ ) by Lagrange interpolation in the exponent. Then, in a step referenced 403, a re-randomization process is applied to the obtained vector (C_z, C_r, it 1, ni- ) .

The resulting re-randomized full signature σ = (C_z, C_r, π , π₂) is outputted.

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.

Given a L-bit message M = M [l] ... M[L] E {0,1}^L and a putative signature σ, an electronic device, in a step referenced 501, parses σ as (C_z, C_r, π , π₂ ) ε G⁴ x G².

Then, in a step referenced 502, it returns/outputs an information (for example a value equal to 1) if the pair (π₁, π₂) satisfies the pairing equation:

ECClcfl_'¹ = E (C_{z z}). E (C_{r r}). E(f, it₁). E( f_M, it₂),

That can also be written as follows

1<G_T = E (C_z, g_z). E (C_r, g_r). E (f, n₁). E( f_M, n₂). E ((1_G, g), §J

That enables avoiding the inversion operation in the group G_T. If the pair [ft^ ^ ) doesn't satisfy the pairing equation, , it returns/outputs an error information (for example a value equal to 0)

It should be noted that the scheme can be simplified by having each player set his private key share as SK_t = {_z_it r{) = (g^~A<^ , g^~B^ so as to spare two exponentiations in the signing phase. In the description, we defined SK_t = (^(O^ HC )^t0 emphasize the fact that no reliable erasures are needed. At each corruption query, the adversary obtains (A(j), B (i)) and, not only (g^~A^ , g^~B(-¹^)- 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. I n the security proof, all intermediate values (including Ai [X] and Bi [X] ) are made available to the adversary upon request. At the 128-bit security level, if each element of G (respectively G) has a 256-bit (resp. 512 bit) representation on Barreto-Naehrig curves (as described in the article entitled "Pairing-Friendly Elliptic Curves of Prime Order", published in the conference proceedings of SAC'05, LNCS 3897, pp. 319-331), only 2048 bits per signature are needed. From a security standpoint, it can be proved that the scheme is secure if the SXDH assumption (for Symmetric external Diffie-Hellman assumption) holds in G, G).

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. In this embodiment, the following elements are needed: the public parameters params comprise the description of bilinear groups (G, G , G_T^{^}) , generators g E_R G , g_z, g_r, h_z, h_u E_R G as well as vectors v₁ =

(_lt 1, g) E G³ , v₂ = (1, v₂, g) E G³with v_lt v₂ E_R , and /_£ = (_£j g ) E_R G² for i = 0 to L, where L E poly (1), for some security parameter Λ.

The key distribution process takes in input the following elements: - params = ^{G, G , G_T ), g, g_z, g_r , h_z, h_r, v_i, v₂, { f_i} .₌^^■

a security parameter Λ;

the integers t, n E M such that n≥ 2t + 1.

Then, each player P_£ performs the following steps described in Figure 6.

I n a step, referenced 601, each player P_£ shares a random triplet (a_iQ, b_iQ, c_£o) according to the following process: pick three random polynomials A_i[X] = a_iQ + a_tlX +— h a_itX^t , B_i[X] = b_i0 + b_tlX +— h b_itX^t , and C_£| | = c_iQ + c_tlX +— h c_ii-^t , each of degree t, and it broadcasts the element W_i( =_z^li ' .h^ , and V_i( = g_z^au.g_r^b for all £ E {0, t} ; - for all £ {1, ...,n}, sending (_Ai(j ,Bi(j , QQ^'))^{to tne} player Pj. In a step referenced 602, the electronic device (corresponding to the player P) receives the ·^{and tnat}

a complaint against Pj.

In a step referenced 603, any player receiving more than t complaints is immediately disqualified. Each player P_t who received a complaint from another player Pj responds by returning the correct shares (A_i(j^'),B_i(j^'),C_i(jy). If any of these new shares fails to satisfy the equations §_z^A .§_r^B =

. Pi is disqualified. Let Q c {1, ... , n} be the set of non-disqualified players at the end of the step 603. The public key PK is obtained as PK =

= g_z^∑ieQai0.g_r^∑ieabi0 andh₁

= h_z^∑ieQai0.h_u^∑ieQCi0.

Each player Ρ_έ locally determines its private key share SK_t as being: SK_t = (A(i),B(i),C(i)) = (∑_;-_eQAj(i),∑j_eQ Bj(i) ,_εδ C(0), and anyone can compute the corresponding verification key which is VK_t = (y_it W) where V_t = g_z^A^-§_r^B^ = Π; E2 nko and Wi = h_z "^J. h_u = Π, SQ Π^_Ο ¾ ·

Any disqualified player Pj with j E {1, ...,n}\Q is implicitly assigned the share S/Q = (0,0,0), and the matching verification key V7Q = (lg, lg).

The vector of private key shares sSK = (SK_lt ...,SK_n) and the corresponding vector of verification keys VK = (VK^ ... , VK_n). The public key consists of PK = (params,

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.

In order to generate a partial signature on a L -bit message M = M[l] ...M[L] E {0,1}^L using SKi = A(j),B(j),C(j)) E Έρ , an electronic device does the following:

It determines (or computes), in a step referenced 701, z_£ = g^~A^ , r_£ = g^~B^ and

The, by using the bitsM[l] ...M[L] E {0,1}^L, the vector f_M =

is determined, in a step referenced 702, so as to assemble a Groth-Sahai CRS f_M = ( v_lt v₂,f_M)- Then, using CRS f_M = (v_lt v₂,f_M), it computes, in a step referenced 703, the Groth Sahai commitments

Cz,i⁼ (Ifr lfr^zi )·^vl ' ' -^v2 ' ' -fM Cr,i⁼ (Ifr lfr^ri )· ¾^Γ,1,ί·¾^Τ'2'1·ΪΜ

to z_£ , r_£ and u_£ respectively.

Then, it generates, in a step referenced 704, a non-interactive witness indistinguishable proof {(jtj_{l i},TTj_{2 i},Trj_{3 i}) .__i that the triple (z_£,r_£, u_£) £ G³ satisfies the two following verification equations

1<G_T = ί, 9z)- e( , gr)-e(.g,Vi) and l_Gr = e(z_i,h_z).e(u_i,h_u).e(g,W_i). This proof is obtained as 1?21 ί^λ — — 2 i^Λ — ^τ" 2 i^Λ — 3 i^Λ — ^τ" 3 i \

π11,ί>^π12,ί>^π13,ί) — g∑ ''-9r ' g z ''-9r >9z ' ' -9r '')^)-vz,l,i £ ~^vu,l,i^-vz,2,i^-vu,2,i ~^vz,3,i^-vu,3,

~ V"-z^■'ⁱu ' "-z^■'ⁱu >"-z^•'hi ) >

The partial signature is a_i = (C_zi, C_{r i}, C_Uii,n_l ,n_12ii,n_13ii, π_21ιί,π_22ί,π_23ί) £ G⁹ x G⁶.

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.

Given a L-bit message M = M[l] ...M[L] E {0,1}^L and a candidate partial signature a_it an electronic device, in a step referenced 801, parses a_t as follows^σί⁼ i^z >^r >^u,i>^ll,i>^12,i>^13,i>^21,i>^22,i>^23,i)^x ^⁶·

Then, the electronic device, in a step referenced 802, checks if the elements comprised in the partial signature verifies the two following pairing equations £^"((1^, l_Gjig),i^)^_1 = E {C_zi,g_z). E(C_{r i},

=

E (C_zi, h_z). E (C_ui, h_u). E (¾, t₂ ). E (¾, t_22i). E ( f_M, t_23i) where f_M = f₀. Π=ι f"^ that can be written also as follows: l_Gr = E (1_G, 1_G, g), V^.E {C_z , g_z). E (C_r,i, §_r)- E (v_lt n_l ). E (v₂, π_12ιί). E ( f_M, π_13ιί) , and l_Gr = E n₂ ).E(v₂,n₂ ).E(f_M,n_23ii).

The check of these pairing equations enables the saving of one inversion operation in the group G_T. If an error occurs either in step 801 (e.g. the format of the obtained partial signature is not correct), or in 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. Given a (t + 1) set of valid shares {(i, σι)}_ίΕ5, an electronic device, in a step referenced

901, parses each share σ_έ as ^_z,i,C_ri,C_U}i ii,i,^i2,i,^i ,i,^2i,v^22,i,ⁱ^2 ,d ε <G⁹ x <G⁶ for all i £ S. Then, in a step referenced 902, it computes cr< r< r< Λ - ιτ r^Ai^ rr ?^Ai,s(°) π s(o_Λ .

^L_z, L_r, L_U) — (Hies L_{z j} ,llies_r,i >llies_u,i J,

(.^πιι>^πΐ2>^πι ) - (Hies^πιι,ί > kesⁿ₁₂,i Ί«ε5^πι₃₍ϊ )'

(^π21^»π22^»π23) - CllteS π_21(ί 4 lies ^22,i 'HieS ^23,1 )

by Lagrange interpolation in the exponent. Then, in a step referenced 903, a re-randomization process is applied to the obtained vector

(C_z, C_r, C_u, 7l\\, 7^12,^π13>^π21>^π22>^π23)·

The resulting re-randomized full signature σ = {C_z,C_r,C_u,7i₁₁, π₁₂,π₁₃, π₂ι, ^22^23) '^s then outputted.

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.

Given a L-bit message M = M[l] ...M[L] £ {0,1}^L and a putative signature σ, an electronic device, in a step referenced 1001, parses σ as (C_z, C_r, C_UJ7r_llJ7r₁₂,7r_13j ^21^22^23)·

Then, in 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):

ECClG.lcfl .¹ = E(C_z,g_z).E (C_r,g_r).E (ν^π^.Ε (ν₂,π₁₂).Ε (/_Μ,π₁₃) and E ((l&l&fl )^-1 = E{C_z,h_z).E{C_u,hy).Ey₁,ii₂^.E v₂,ii₂₂).E (f_Mlit₂₃) , where

That can be written also as follows l_Gr = E ( 1_G, 1_G, g), E (C_z, g_Z) . E (C_R, g^. E , π^). E(v₂, n₁₂) . E ( f_M, π₁₃) and

IG_T =^E (O-_fr 9)_> ^i)■ E (C_Z» h_Z) . E (C_r, h_u). E(v_lt π₂₁). Ε (ν₂, n₂₂) . E ( f_M, π₂₃) That enables the saving of one inversion operation in the group G_r.

If the above embodiment is implemented with asymmetric pairings (where G ≠ G) using Barreto-Naehrig curves, each element of G (respectively each element of G) can have a 256-bit (respectively 512-bit) representation, so that each signature fits within 5376 bits.

I n an instantiation using symmetric pairings (i.e., where G = G) and super-singular curves, 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).

It should also be noted that it is possible to generalize the above construction so as to rely on the weaker K linear assumption with K > 2 (recall that the DLI N assumption corresponds to K = 2). In this case, each signature is comprised of (K + Y) (2K + 1) group elements. More precisely, the commitments require (K + l)² 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.

Figure 11 discloses a flowchart which depicts some steps performed during a key distribution process according to one embodiment of the present principles. In this embodiment of the present principles, public parameters params comprise the description of bilinear groups (G, G , G_T ), generators E_R G, g_z,g_r,h_z,h_u E_R Gas well as vectors v₁ = (v_lt l,g) E G³ ,v₂ = (_l,v₂,g) E G³with v₁,v₂ E_R G , and /_£ = (/_£, g_£) E_R G² for i = 0 to L. The key distribution process takes in input the following elements:

- params = j(G, G , G_T ), g, g_z, g_r, h_z, h_u, v , v₂, { /i}._J ;

a security parameter Λ;

the integers t,n E M such that n≥ 2t + 1.

Then, each player P_£ performs the following steps described in Figure 11. In a step, referenced 1101, each player P_£ shares a random triplet (a_£o, ¾_£o, c_£o) according to the following process: pick three random polynomials Αι[Χ] = a_i0 + a_tlX +— h a_itX^t , B_i[X^'\ = b_i0 + b_tlX +— h ¾_£tA^rt , and C_£[ ] = c_£o + c_£l +— h c_£i-^t , each of degree t, and it broadcasts the element W_i{ = h_z^a .h_u^C , and V_i{ = g_z^a .g_r^b for all i E {0,...,t}; - for all £ {0, ...,n}, sending (Α^,Β^ ,^)) to the player Pj.

In a step referenced 1102, the electronic device (corresponding to the player P) receives

the shares Aj (i),Bj (i),Cj(i)), and it verifies that^{and tnat}

if the latter equality does not hold, P_£ broadcasts a complaint against Pj. In a step referenced 1103, 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(j^'),C_i(jy). If any of these new shares fails to satisfy the equations

= o w . Pi disqualified. Let Q c {1, ... , n} be the set of non-disqualified players at the end of the step 1003. = g_z^{∑ieQ ai0}. g_r^{∑ieQ bi0}

Each player P_t locally determines its private key S/Q as being : S/Q = (A(i) , B (i) , C (i)) = (∑;

, and anyone can compute the corresponding verification key which is VK_t = (V_u 1 ^) where K_£ = g_z^A{^ . g_r^B<S) = Ylj≡Q ΓΠ<=_Ο^AND

Any disqualified playery £ {1, ... , n}\Q is implicitly assigned the share SK_t = (0,0,0), and the matching verification key V7Q = (lg, lg).

The vector of private key shares s SK = (SK_lt ... , SK_n) and the corresponding vector of verification keys VK = (VK_lt ... , VK_n). The public key consists of

PK = (params. gi. hi)

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.

In order to generate a partial signature on a L -bit message M = M[l] ... M[L] E {0,1}^L using SK_t = A(j), B (j), C(j)) E Έρ , an electronic device does the following.

In a step, referenced 1201, it computes ζ_έ = g^~A^ , = g^~B<^> and ύι = g^~c(-^l Then, by using the bits M[l] ... M[L] E {0,1}^L, it determines, in a step referenced 1202, the vector_M

so as to assemble a Groth-Sahai CRS f_M = ( v_1} v₂, f_M)-

By using CRS f_M = ( v_lt v₂, f_M), it computes, in a step referenced 1203, the Groth Sahai commitments

→ →^vz,l,i →^vz,2,i ~^Vz'³'' _, _» V_{r l} i ->^vr,2,i ~^vr,3,i

to z_£ ,_£ and u_£ respectively.

Then, in 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³ satisfies the two following verification equations

1<G_T = e(g_z,Zi ).e{g_r,r_i .e(V₀§) and l_Gr = e(/i_z,z_£ ).e{h_u,u_i ).e( W^).

This proof is obtained as

(πιι,.,π₁₂₍ΐ,π_13(ί) = {g_z-^Vz^.g_r^{~Vr i}, gz^~Vz- -9r^~Vr- ,9z^~Vz- -9r^~Vr ) ; (7T_21(i, 7T_22(ij 7T_23(i) =

The partial signature is a_i = {_iii,Cf_ii,C_Qii,n_l ,n_12ii,n₁-_iii,n₂ ,n_22ii,n₂-_{i i}) £ G⁹ x G⁶.

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. Given a L-bit message M = M[l] ...M[L] E {0,1}^L and a partial signature a_it an electronic device, in a step referenced 1301, parses σ_£ as follows^σί⁼ C†,i> Cu,i>^π11,ί>^π12,ί>^π13,ί>^π21,ί>^π22,ί>^π23,ί)^Χ

Then, in a step referenced 1302, it checks if the elements comprised in the candidate partial signature verify the two following pairing equations E(y_it (lg, lg,,g) )^_1 = E(g_z, C ).E(g_r, C_f ).E(n_l , ¾). E(n_12>i, v₂). E (π_13ί , /_M), and

E (W_it (lg, lg, g)Y¹ = E {h_z, C ). E (h_u, C_¾i ). E (n₂ , ¾). E n_22i, ¾). E (π_23ί , /_M) where f_M =

If an error occurs either in step 1301 (e.g. the format of the obtained partial signature is not correct), or in 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.

Given a (t + 1) set of valid shares {(ί, σ_έ)}_έε5, an electronic device, in a step referenced

1401, parses each share σ_έ as ζχ> £τχ> £^π\\χ>^π\τχ>^π\ χ>^π2\χ>^π22χ>^π2 ,ί) ε <G⁹ x <G⁶ for all i E S. Then, in a step referenced 1402, it computes

y Lagrange interpolation in the exponent.

Then, in a step referenced 1403, a re-randomization process is applied to the obtained vector (C~, C_†', C~, π^' , π₁'₂, π₃, π₂'₁, π₂'₂, π₂₃).

The resulting re-randomized full signature σ = {ζ^, Ο, , Ο,^, π^, π^, π₁₃, π₂₁, π₂₂, π₂₃) 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. Given a L-bit message M = M[l] ... M[L] E {0,1}^L and a putative signature σ, an electronic device, in a step referenced 1501, parses σ as follows (¾, C_f, C_Qj n_llt π₁₂, π₁₃, π₂₁, π₂₂, π₂₃) .

Then, in 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, §)¹ = E(g_z, ¾). E(g_r, C_f). E(n_llt ¾, ). E (π₁₂, ¾, ). E (π₁₃, /_Μ) and E (¾i, (le, 1& §) )^_1 = £( i_z, ¾. £( i_u, )-£ (n₂₁, v_lt ). E(n₂₂, v₂, ). E (n₂₃, f_M^) , where

The choice of parameters in this embodiment significantly longer signatures compared to the first embodiment. Indeed, in asymmetric bilinear groups instantiated with Barreto-Naehrig curves, it requires 6144 bits per signature at the 128-bit security level.

Finally it should be noticed that a fourth embodiment can be obtained by similarly exchanging the roles of G and G in the first embodiment. In this case, 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.

At last, the main ideas of the present disclosure can be sum up as follows. 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). In short, 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. The advantage of Pedersen's protocol is its efficiency and its simplicity: when all parties follow the protocol, a single communication round is needed. However, 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. Fortunately, 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. 373-390, such as the construction of threshold Schnorr signatures. Still, these applications are only known to provide security against static adversaries. In the present disclosure, a secure application of Pedersen's protocol in the adaptive corruption setting is provided. Perhaps surprisingly, the efficiency of the original protocol is retained, and it is not needed to rely on zero-knowledge proofs (unlike more complex protocols like the one depicted in the article " 'Adoptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures" by S. Jarecki, A. Lysyanskaya, and published in the conference proceedings of Eurocrypt'00, LNCS 1807, pp. 221-242) or reliable erasures at any time.

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. In its centralized (i.e., non-distributed) version, the construction involves a public key g₁ = g . §r , where {a, b) E Έρ is the private key, which perfectly hides a E Έ_ρ . 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" . The key idea is that, due to the witness indistinguishable property of Groth-Sahai proofs, this proof of knowledge will not reveal any information about the specific pair (a, b) used to generate the proof (recall that there are exactly p pairs (a, b) E Έρ satisfying g₁ = g^ - oft). Hence, in the security proof, the reduction can generate g₁ = g^ - oft for a chosen pair {a, b) E Έρ and use the latter to faithfully answer signing queries. Thanks to the witness indistinguishability property of GrothSahai proofs, no information leaks about the specific pair (a, b) used by the reduction. For this reason, when the adversary creates a fake signature, the reduction is able to extract a different pair (g^a', g^b')≠ (g^a, g^b) such that g₁ = g^. g^ = This will allow the reduction to solve an instance of a problem which is known to be at least as hard as SXDH.

I n order to thresholdize the signing process, homomorphic properties of Groth-Sahai proofs are used. More precisely, the fact that linear pairing product equations and their proofs can be linearly combined in order to obtain a valid proof for the desired statement when performing a Lagrange interpolation in the exponent, is used. I n order to avoid interaction during the signing process, the property that the centralized signature scheme is key homomorphic is also used. Namely, for any given message M and signatures σ₁ = Sign(sk_lt M), σ₂ = Sign(sk₂, M), anyone can publicly compute σ =

+ sk₂, M) .

The reason why adaptive security in the threshold setting ca n be proven is that, in the security proof, the reduction knows the private key (a, b) E Έρ (or, more precisely, all its polynomial shares) at any time, which makes it very easy to answer adaptive corruption queries. However, it should be proven that the scheme remains adaptively secure, even when used in combination with Pedersen's distributed key generation protocol, although the latter is known not to guarantee the uniform distribution of public keys. To do this, key homomorphic property is used. In the security proof, it can be implicitly shown that, if the adversary ca n forge a signature for a jointly generated public key PK of possibly biased distribution. This forgery can be turned into a forgery for another public key PK' , which is uniformly distributed.

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. In particular, 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"). It should be noted that the arrows in Figure 16 signify that the linked unit can exchange data through buses for example together.

In an alternative embodiment, 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. In another embodiment, some or all of the steps of the method previously described, can be implemented in hardware in the form of an integrated circuit.

In an alternative embodiment, some or all of the steps of the method previously described, can be executed on an electronic device comprising memory units and processing units as the one disclosed in the Figure 16.

At last, it should be noticed that 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.

Claims

Claims

1. 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, and being characterized 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) E Έ_ρ for all y E {1, ... , K + 1} , with p being a prime number, and K being an integer greater or equal to one;

determining from said partial key, K elements tj = g^~u>^ , 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; determining from said message a vector so as to define a Groth-Sahai common reference string;

determining Groth-Sahai commitments on said K + 1 elements tj with j E {Ι, .,. , Κ + lj from said Groth-Sahai common reference string, said Groth- Sahai commitments belonging to said group G; and

determining 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;

delivering said partial signature associated with said message, said partial signature comprising said Groth-Sahai commitments, and said non-interactive witness indistinguishable proof.

2. The signing method according to claim 1, characterized in that when said message M comprises L binary elements, with L an integer greater or equal to one, said vector corresponds to f_M = f₀. Π;=ι ϊ with vectors f_t comprising K+l elements of said group G, and said Groth-Sahai common reference string corresponds to K elements (v_lt ... , v_K, f_M), with elements Vj E G^K+1 with j E {1, ... , K}.

3. The signing method according to claim 2, characterized in that said Groth-Sahai commitment associated with an element tj is obtained from determining

1_Gj tj).

¾^rfe) -_Μ^Κ+1 , with elements y_fc being random elements, for k £ {1, ... , K + 1}.

4. The signing method according to any claims 1 to 3, characterized in that said secret sharing scheme is a (t, n) Shamir secret sharing scheme.

5. The signing method according to any claims 1 to 3, characterized in that said secret sharing scheme is a non-interactive secret sharing scheme.

6. The signing method according to claim 5, characterized in that said secret sharing scheme is based on Pedersen's protocol.

7. The signing method according to any claims 1 to 6, characterized in that said group G and said group G are permuted.

8. The signing method according to any claims 1 to 7, characterized in that said group G and said group G are a same group.

9. 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, said threshold signing method being characterized in that each partial signature being obtained through the execution of a signing method according to any claims 1 to 8, 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.

10. The threshold signing method according to claim 9, characterized 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 V7Q from said vector being associated with a corresponding partial secret key SK_{i t} and said verifying comprising determining if K pairing product equations hold.

11. The threshold signing method according to any claims 9 and 10, characterized 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.

12. A signature verification method of a threshold signature associated with a message, said threshold signature being obtained from an execution of said threshold signing method of any of claims 9 to 11, said signature verification being characterized in that it comprises verifying if K pairing equations hold.

13. A computer-readable and non-transient storage medium storing a computer program comprising a set of computer-executable instructions to implement a method for cryptographic computations when the instructions are executed by a computer, wherein the instructions comprise instructions, which when executed, configure the computer to perform signing method of claims 1 to 8, and/or to perform a threshold signing method according of claims 9 to 11, and/or a signature verification method of claim 12.

An electronic device being able to deliver a partial signature associated with a message, said partial signature being used in a threshold signing scheme, said electronic device being characterized in that it comprises:

a processor 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 ½(ί), ... , u_K+1 (i)}, where elements Uj (i) E Έ_ρ for all j E {1, ... , K + 1}, with p a prime number, and K being an integer greater or equal to one;

a processor configured to determine from said partial key, K elements tj = g-uj(i) ^ with £ {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;

a processor configured to determine from said message a vector so as to define a Groth-Sahai common reference string;

a processor 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 processor 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;

a processor configured to deliver said partial signature associated with said message, said partial signature comprising said Groth-Sahai commitments, and said non-interactive witness indistinguishable proof.

15. 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 said electronic device being characterized in that it comprises a processor 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.