Xavier Boyen

Céline Chevalier

Georg Fuchsbauer

David Pointcheval

Strong Cryptography from Weak Secrets Building Efficient PKE and IBE from Distributed Passwords

. Furthermore, we strenghten their security model by suppressing the useless testPwd queries in the functionality.

Introduction

Recently, Abdalla et al. [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] proposed the notion of distributed-password public-key cryptography (DPwPKC), which allows the members of a group of people, each one holding a small independent secret password, to act collectively (for the benefit of one of them, who "owns" the group) as the custodian of a private key in some ordinary public-key cryptosystem -without relying on any secure (secret and/or authentic) storage -as long as each member remembers his or her password. Precisely, in DPwPKC, the members initially create a "virtual" key pair (sk, pk), by engaging in some distributed protocol over adversarial channels, where only pk is revealed, while sk is implicitly determined by the collection of passwords. Third parties can perform the public-key operation(s) of the underlying system using pk. Members can help the leader of the group perform private-key operation(s) in a distributed manner, by engaging in some protocol using only their knowledge of their respective passwords.

Password-based public-key cryptography is generally considered infeasible because password-based secret-key spaces are easy to enumerate, and the knowledge of the public key makes it possible to test the correct key from that space, without interacting with anyone (offline dictionary attack). In DPwPKC, there are as many passwords as participants, and (unlike in virtually all applications of passwords) the passwords are not meant to be shared: they are chosen independently by each player. Since the passwords need not be related, they will likely be diverse, and the min-entropy of their combination ought to grow linearly with the number of participants, even if every single password is itself minuscule. For instance, with ten players each holding a random 20-bit password, the virtual secret key will be a random 200-bit string, which is more than enough to build a secure public-key system for usual values of the security parameter. This is what makes sk in DPwPKC resistant to brute-force off-line dictionary attacks, even though the corresponding pk is public.

The main contribution of [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] was to define general functionalities for distributed password-based key generation and private computation in the UC model, and to give a construction for ElGamal decryption as a proof of concept. However, the construction proposed in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] was merely illustrative because it required generic simulation-sound non-interactive zero-knowledge (SSNIZK) proofs for NP languages, which can only be performed efficiently in the random oracle model [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF]. Furthermore, their distributed private computation protocol could only perform the task of computing c sk from the implicit secret key sk, and the security of their protocol relied on the DDH assumption. Together, these restrictions limited its applicability to ElGamal decryption.

In this work, we first improve and strengthen the ideal functionalities defined in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF], by further restricting the information that the adversary can gain from an attack. This will make any protocol that we can prove to realize those functionalities stronger, since the simulation will have to work without this information. (Recall that in the UC model, the functionalities are supposed to capture everything that we allow the adversary (and thus the simulator) to learn.)

Then, we extend the techniques from [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] to support a much broader class of private-key operations in discrete-log-hard groups, including operations involving random ephemerals and/or operations in bilinear groups. More precisely, our construction still targets the distributed computation of c sk , but under the Decision Linear assumption, which makes the proof more intricate since the DDH is now verifiable: we had to change the workings of the protocol to introduce secret values. Furthermore, the construction works for several values of c at once, and now allows to share random ephemerals in the exponent. It thus allows a much greater variety of public-key cryptosystems to be converted to distributed password-based cryptosystems, including extraction of identity-based private keysthus giving us the new interesting notion of "password-based distributed identity-based encryption" (DPwIBE). Contrarily to regular IBE, the "central" key extraction authority is now distributed among a group of people (sufficiently many of them trusted), with the "master key" being implicitly contained in the collections of short independent passwords held by those users.

In the process of strengthening and generalizing the protocols, we also make them much more efficient. To do so, we develop special-purpose simulation-sound non-interactive zero-knowledge proofs (SSNIZK) for our languages of interest, in the standard model, and show how to use them instead of the inefficient general SSNIZK considered in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF]. We do this using bilinear maps, in the CRS model, relying on a classic decisional hardness assumption for bilinear groups. The SSNIZK proofs we construct revisit the techniques of [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] and use efficient proofs inspired by the recent Groth-(Ostrovsky)-Sahai sequence of efficient NIZK construction in bilinear groups [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], but do not trivially follow from them.

In summary, we revisit the recent and intriguing notion of DPwPKC, which we strengthen and extend in several directions. Our general results are, more precisely: 1) to propose new, simpler and stronger versions of the DPwPKC functionalities defined in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] by getting rid of the testPwd query; 2) to show how we can realize the general functionalities much more efficiently, without random oracles, by constructing new SSNIZK proof techniques from bilinear pairings, inspired from the NIZK proof system proposed by Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] under the Decisional Linear assumption [START_REF] Boneh | Short group signatures[END_REF]; 3) to show how to apply our protocol to implement a very broad class of public-key cryptosystems from discrete-log-type hardness assumptions in bilinear groups; and 4) in particular, to show how to apply our technique to transform the pairing-based Boneh-Franklin [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] and Boneh-Boyen [START_REF] Boneh | Efficient selective-ID secure identity based encryption without random oracles[END_REF] identity-based cryptosystems (and most of the latter's many extensions), to realize the notion of distributed password-based identity-based encryption (DPwIBE). In DPwIBE, contrarily to regular IBE, the "central" key extraction authority is now distributed among a group of people (sufficiently many of them trusted), with the "master key" being implicitly contained in the collections of short independent passwords held by those users.

In order to do all this, and in particular to get the efficient pairing-based approach working, a number of new technical challenges had to be solved. We specifically mention the following: 1) the use of pairings not only helps us make efficient zero-knowledge proofs for various languages, it would also help the adversary verify the result of the private computation c sk in the basic DPwPKC protocol from [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF]. Since the UC model requires that the simulation be carried out until the end on both correct and incorrect inputs, this will make our new security reduction somewhat more intricate since the result sent at the end of the simulation is random and we do not want the adversary to become aware of it.

2) In connection with the stronger and simpler functionality definitions we propose, the adversary is no longer allowed to conduct explicit password compatibility tests prior to the private-key operation. This should intuitively further complicate the simulation, though we remarkably note that these queries were indeed useless in the proofs and thus getting rid of them has no negative impact. 3) Generally speaking, we achieved much of our security and efficiency gains over [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF], by succeeding to make our protocols being fully robust by the use of public verifications (computations of pairings) rather than intermediate validity tests (SSNIZK proofs, relying on the random oracle model in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF]). This is generally both more efficient (no more SSNIZK proofs) and more secure than testing, but it can lead to significantly more complex simulations owing to the ideal functionality being less "helpful".

Security Model

Split Functionalities. Throughout this paper, we assume basic familiarity with the universal composability framework [START_REF] Canetti | Universally composable security: A new paradigm for cryptographic protocols[END_REF]. See Appendix A for a short introduction of some UC notions we shall use in this work. Without any strong authentication mechanisms, the adversary can always partition the players into disjoint subgroups and execute independent sessions of the protocol with each subgroup, playing the role of the other players. Such an attack is unavoidable since players cannot distinguish the case in which they interact with each other from the case where they interact with the adversary. The authors of [START_REF] Barak | Secure computation without authentication[END_REF] addressed this issue by proposing a new model based on split functionalities which guarantees that this attack is the only one available to the adversary.

The split functionality is a generic construction based upon an ideal functionality: Its description can be found in Figure 5. In the initialization stage, the adversary A adaptively chooses disjoint subsets of the honest parties (with a unique session identifier that is fixed for the duration of the protocol). During the computation, each subset H activates a separate instance of the functionality F. All these functionality instances are independent: The executions of the protocol for each subset H can only be related in the way A chooses the inputs of the players it controls. The parties P i ∈ H provide their own inputs and receive their own outputs, whereas A plays the role of all the parties P j / ∈ H. Note that the use of these split functionalities already allows the adversary to try some passwords for users by choosing subgroups of size 1 and trying a password for each of them while impersonating the other players. They are thus enough to model on-line dictionary attacks. In [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF], additional TestPwd queries were available to the adversary, thus allowing additional password trials. In this paper, we limit the adversary against the ideal functionality (i.e. the simulator), to the unavoidable on-line dictionary attack but in the strict sense, and thus without any additional TestPwd queries. This means that we give less power to the simulator. Both the constructions in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] and ours do not need them in the security proofs, which means that a stronger security level is reached.

In the sequel, as we describe our two general functionalities F pwDistPublicKeyGen and F pwDistPrivateComp (the complete descriptions can be found in Figures 3 and4), one has to keep in mind that an attacker controlling the communication channels can always choose to view them as the split functionalities sF pwDistPublicKeyGen and sF pwDistPrivateComp , which implicitly consist of multiple instances of F pwDistPublicKeyGen and F pwDistPrivateComp for non-overlapping subsets of the original players. Furthermore, one cannot prevent A from keeping some flows, which will never arrive. This is modelled in our functionalities by a bit b, which specifies whether the flow is really sent or not. The Players and the Group Leader. We denote by n the number of users involved in a given execution of the protocol. All the computation is done for the benefit of only one of them, denoted as the group leader. The role of all the other ones, the players, is to help it in its use of the group's virtual key. A group is thus formed arbitrarily and is defined by its composition, which cannot be changed: a leader, which is the only one to receive the result of a private computation in the end, and a (ordered or not, according to the secret key computation from the passwords) set of players to assist it. The Aim of the Functionalities. The functionalities are intended to capture distributed-password protocols for (the key-generation and private-key operation of) an arbitrary public-key primitive, but taking into consideration the unavoidable on-line dictionary attacks. More precisely, the aim of the distributed key generation functionality F pwDistPublicKeyGen (Figure 3, page 17) is to provide a public key to the users, computed according to their passwords with respect to a function PublicKeyGen given as parameter. Moreover, it ensures that the group leader never receives an incorrect key in the end, whatever the adversary does.

In the distributed private computation functionality F pwDistPrivateComp (Figure 4, page 18), the aim is to perform a private computation for the sole benefit of the group leader, which is responsible for the correctness of the computation; in addition, it is the only user to receive the end result. This functionality will thus compute a function of some supplied input in, depending on a set of passwords that must define a secret key corresponding to a given public key. More precisely, it will be able to check the compatibility of the passwords with the public key thanks to a verification function PublicKeyVer, and if it is correct it will then compute the secret key sk from the passwords with the help of a function SecretKeyGen, and from there evaluate PrivateComp(sk, in) and give the result to the leader. The function PrivateComp could be the decryption function Dec of a public-key encryption scheme, or the signing function Sign in a signature scheme, or the identity-based key extraction function Extract in an IBE system.

Note that SecretKeyGen and PublicKeyVer are naturally related to the function PublicKeyGen called by the former functionality. In all generality, unless SecretKeyGen and PublicKeyGen are both assumed to be deterministic, we need the predicate PublicKeyVer in order to verify that a public key is "correct" without necessarily being "equal" (to some canonical public key). Also note that the function SecretKeyGen is not assumed to be injective, lest it unduly restrict the number of users and the total size of their passwords. The distributed computations should not reveal more information than the non-distributed ones, and thus the ideal functionalities can make use of these functions as black-boxes. The Functionalities.

We only recall here the main points of the functionalities, referring the interested reader to [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] for details. But, importantly, as in [START_REF] Canetti | Universally composable password-based key exchange[END_REF], the functionalities are not in charge of providing the passwords to the participants. The passwords are chosen by the environment which then hands them to the parties as inputs. This guarantees security even in the case where an honest user executes the protocol with an incorrect password: This models, for instance, the case where a user mistypes its password. It also implies that the security is preserved for all password distributions (not necessarily the uniform one) and in all situations where related passwords are used in different protocols.

The private-computation functionality fails directly at the end of the initialization phase if the users do not share the same (public) inputs. In principle, after the initialization stage (the NewSession queries) is over, the eligible users are ready to receive the result. However the functionality waits for the adversary S to send a compute message before proceeding. This allows S to decide the exact moment when the result should be sent to the users and, in particular, it allows S to choose the exact moment when corruptions should occur (for instance S may decide to corrupt some party P i before the result is sent but after P i decided to participate to a given session of the protocol; see [START_REF] Katz | Modeling insider attacks on group key-exchange protocols[END_REF]). Also, although in the key generation functionality all users are normally eligible to receive the public key, in the private computation functionality it is important that only the group leader receives the output (though he may choose to reveal it afterwards to others, outside of the protocol, depending on the application). In both cases, after the result is computed, S can choose whether the group leader indeed receives it. If delivery is denied (b = 0), then nobody gets it, and it is as if it was never computed. Otherwise, in the first functionality, the other players may be allowed to receive it too, according to a schedule chosen by S.

Note that given the public key, if the adversary knows/controls sufficiently many passwords so that the combined entropy of the remaining passwords is low enough, he will be able to recover these remaining passwords by brute force attack. This is unavoidable and has nothing to do with the fact that the system is distributed: off-line attacks are always possible in principle in public-key systems, and become feasible as soon as a sufficient portion of the private key is known.

Notations and Building Blocks

The authors of [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] propose a protocol that deals with a particular case of unauthenticated distributed private computation [START_REF] Barak | Secure computation without authentication[END_REF], as captured by their functionalities recalled in the former section. Informally, assuming s to be a secret key, the aim of the protocol is to compute a value c s given an element c of the group. They claim that this computation can be used to perform distributed BLS signatures [START_REF] Boneh | Short signatures from the Weil pairing[END_REF], ElGamal decryptions [START_REF] Boneh | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], linear decryptions [START_REF] Boneh | Short group signatures[END_REF], and BF or BB1 identity-based key extraction [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF][START_REF] Boneh | Efficient selective-ID secure identity based encryption without random oracles[END_REF] but they only focus on ElGamal decryptions, relying on the DDH assumption.

Here, we show how to really achieve such results, by constructing a protocol relying on the Decision Linear assumption [START_REF] Boneh | Short group signatures[END_REF] for compatibility with bilinear groups. This protocol will easily enable "passwordbased" Boneh-Franklin IBE scheme [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF]. In the following section, we show how to modify the protocol to obtain "password-based" Boneh-Boyen (BB 1 ) IBE scheme [START_REF] Boneh | Efficient selective-ID secure identity based encryption without random oracles[END_REF] and linear decryptions [START_REF] Boneh | Short group signatures[END_REF].

Notations.

Let G be a multiplicative cyclic group of prime order p and g 3 a generator of G. The linear encryption works as follows: The private key is a pair of scalars, sk lin = (x 1 , x 2 ), and the public key, pk lin = (g 1 , g 2 , g 3 ), where g 1 = g 3 1/x 1 , g 2 = g 3 1/x 2 . In order to encrypt M ∈ G, one chooses

r 1 , r 2 $ ← Z p , and the ciphertext consists of C = E pk lin (M ; r 1 , r 2 ) = (C 1 , C 2 , C 3 ) = (g 1 r 1 , g 2 r 2 , M g 3 r 1 +r 2 ). The decryption process consists of M = D pk lin (C) = C 3 /(C 1 x 1 C 2 x 2 )
. This encryption scheme is secure under the Decisional Linear (DLin) assumption, first presented in [START_REF] Boneh | Short group signatures[END_REF] and stated here for completeness: For random x, y, r, s ∈ Z * p and (g, f = g x , h = g y , f r , h s ) ∈ G 5 , it is computationally intractable given g d to distinguish between the case where d = r + s or d is random. More precisely, a triple (f r , h s , g d ) is named a linear triple in basis (f, h, g) if d = r + s. We also consider a one-time signature scheme consisting of the three algorithms (SKG, Sign, Ver). Passwords, Public Key and Private Key. Each user P i owns a privately selected password pw i , to act as the i-th share of the secret key sk (see below). For convenience, we write pw i = pw i,1 . . . pw i,ℓ ∈ {0, . . . , 2 ℓ -1}, i.e., we further divide each password pw i into ℓ bits pw i,j , where p < 2 ℓ (p is the order of the group G). Notice that although we allow full-size passwords of up to ℓ bits (the size of p), users are of course permitted to choose shorter passwords.

The authors of [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF] discussed the use of such passwords to combine properly into a private key sk: the combination should be reproducible, it should allow to recover either of the passwords from the key and the other passwords, and it should preserve the joint entropy of the set of paswords. They also discussed possible cancellation or aliasing effects of the passwords. The preferable solution is to do standard pre-processing using hashing, i.e. that each user independently transforms his or her true password pw * i into an effective password pw i by applying a suitable extractor pw i = H(i, pw * i , Z i ) where Z i is any relevant public information. We can then safely take sk = i pw i and be assured that the entropy of sk will closely match the joint entropy of the vector (pw * 1 , . . . , pw * n ). The discrete-log-based key pair (sk, pk = g sk ) is then defined as follows:

sk = SecretKeyGen(pw 1 , . . . , pw n ) def = n i=1 pw i pk = PublicKeyGen(pw 1 , . . . , pw n ) def = g P pw i
The password/public-key verification function is then

PublicKeyVer(pw 1 , . . . , pw n , pk) def = pk ? = g P pw i .
In the following, we focus on a specific format for the PrivateComp function, defined by (sk, c) → m = c sk . We show how to perform it in a distributed way, and how to use if for decryption processes, and private key extraction in IBE. Building Blocks. Extractable Homomorphic Commitments. As in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF], the first step of our distributed decryption protocol is for each user to commit to his password (the details are given in the following section). The commitment needs to be extractable, homomorphic, and compatible with the shape of the public key. Generally speaking, one needs a commitment Commit(pw, R) that is additively homomorphic on pw and with certain properties on R. Instead of ElGamal's scheme [START_REF] Boneh | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] used in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF], we focus here on linear commitments Commit g (pw, r, s) = (U 1 pw g 1 r , U 2 pw g 2 s , g pw g 3 r+s ), where (U 1 , U 2 , U 3 = g) is not a linear triple in basis (g 1 , g 2 , g 3 ) in order to provide extractability, or encryptions Encrypt g (pw, r, s) = (g 1 r , g 2 s , g pw g 3 r+s ) (here, g 1 , g 2 and g 3 are defined as before and g is a generator of G). In both cases, the hiding property or the semantic security rely on the DLin assumption. Extractability is possible granted the private/decryption key (x 1 , x 2 ), such that

g 3 = g 1 x 1 = g 2 x 2
, and recalling that the users commit to bits. Denoting by (c 1 , c 2 , c 3 ) the commitment, it is thus enough to check that c 3 /(c 1

x 1 c 2 x 2 ) = 1 or (c 3 /g)/((c 1 /U 1 ) x 1 (c 2 /U 2 ) x 2 ) = 1.

Proofs of Membership.

For the robustness and soundness of the protocols, we need some proofs of honest computations. We use witness-indistinguishable and SSNIZK proofs/arguments. The difficulty consists in designing such simulation-sound proofs without random oracles: they are described in Section 6. Along these lines, we use the following kinds of non-interactive proofs:

-CDH(g, G, h, H), to prove that (g, G, h, H) lies in the CDH language: there exists a common exponent x such that G = g x and H = h x . Granted pairing-friendly groups, this can be easily done by simple pairing computations; -WIProofBit(C), to prove that the commitment or the ciphertext C contains a bit. We will use a WI proof from [START_REF] Groth | Non-interactive zaps and new techniques for NIZK[END_REF], which basically proves that either C or C divided by the basis is a linear 3-tuple; -SSNIZKEq g,c (C 1 , C 2 ), to prove that the ciphertexts/commitments C 1 and C 2 contain the same value, possibly in the different bases g and c, that is, C 1 encrypts/commits to g a and C 2 encrypts/commits to c a , with the same a. We use a SSNIZK argument, following the overall approach by Groth [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] to obtain simulation soundness, but using the Groth-Sahai proof system [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] for efficiency (see Section 6 -the proof is omitted, but very similar to [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF]).

Description of the Protocols

The Distributed Key Generation Protocol. This protocol is described in Figure 1 and realizes the functionality F pwDistPublicKeyGen . All the users are provided with a password pw i and want to obtain a public key pk. One of them is the leader of the group, denoted by P 1 , and the others are P 2 , . . . , P n . The protocol starts with a round of commitments of these passwords. Each user sends a commitment C i of pw i (divided into ℓ blocks pw 1,1 , . . . , pw i,ℓ of length L -here, L = 1): it computes

C i,j = (C (1) i,j , C (2) i,j , C (3)
i,j ) = (U 1 pw i,j g 1 r i,j , U 2 pw i,j g 2 s i,j , g pw i,j g 3 r i,j +s i,j ) for j = 1, . . . , ℓ and random values r i,j and s i,j , and publishes C i = (C i,1 , . . . , C i,ℓ ), with a set of proofs WIProofBit(C i,j ) that each commitment indeed commits to an L-bit block. As we see in the proof (see Appendix B), this commitment needs to be extractable so that the simulator is able to recover the passwords used by the adversary, which is the reason why we segmented all the passwords and make commitments of bits, along with a WIProofBit that the committed value is actually a bit. Each user also runs the signature key generation algorithm to obtain a signature key SK i and a verification key VK i . The users will be split according to the values received in this first flow (i.e. the commitments, the proofs and the verification keys), as we see in the second flow where they send a signature of all they have received up to this point. Thus, the protocol cannot continue past this point if some players do not share the same values as the others (i.e. one of the signatures σ i will be rejected later on and at least a user will abort).

Once this first step is done, the users commit again to their passwords (by encrypting them, for efficiency reasons), but this time in a single block:

C ′ i = (C ′ i (1) , C ′ i (2) , C ′ i (3) ) = (g 1 t i , g 2 u i , g pw i g 3 t i +u i ) (with
random values t i and u i ) and publish it along with a SSNIZK proof that the passwords committed are the same in the two commitments: SSNIZKEq g,g (C i , C ′ i ), C i roughly being the product of the C i,j , i.e. a commitment of pw i . The new encryptions C ′ i will be the ones used in the rest of the protocol. They need not be segmented (since we will not extract anything from them, but just make computations on encrypted values), but we ask the users to prove that they are compatible with the former commitments.

Each user P i computes H = H(C 1 , . . . , C n ), and sends a signature of the values that identifies this execution, under an ephemeral one-time signature key, to avoid malleability and replay from previous sessions: σ i = Sign(H; SK i ). This allows the protocol to realize the split functionality by ensuring that everybody has received the same values in the first round (more precisely, the players have been split according to what they received in the first round, so that we can assume that they have all received the same values). Note that the protocol will fail if the adversary drops or modifies a flow received by a user, even if everything was correct. This situation is modeled by the bit b of the key delivery queries in the functionality, for when everything goes well but some of the players do not obtain the result.

The need for an additional extractable commitment C i of g pw i (and a proof that the password used is the same, and that everybody received the same value) is a requirement of the UC model, as in [START_REF] Canetti | Universally composable password-based key exchange[END_REF]. Indeed, we show later on that S needs to be able to simulate everything without knowing any passwords: Thus, he recovers the passwords by extracting them from the commitments C i made by the adversary in the first round, enabling him to adjust his own values before the subsequent encryptions C ′ i , so that all the passwords are compatible with the public key (if they should be in the situation at hand).

After these rounds of commitments/encryptions, the players check the signatures and abort if one of them is not valid. A computation step then allows them to compute the public key. Note that everything has become publicly verifiable.

Computation starts from the ciphertexts C ′ i , and involves two "blinding rings" to raise sequentially the values

i C ′ i (3) = g P i pw i g 3 P i (t i +u i ) , g 1 , g 2 and g 3 to some distributed random exponent α = i α i .
The players then broadcast g 3 α(t i +u i ) (the values g 1 and g 2 are only here to check the consistency of the values t i and u i and avoid cheating), leaving every player able to compute g α P i pw i . A final "unblinding" allows for the recovery of g P i pw i = pk. We stress that every user is able to check the validity of this computation (at each step, it checks the CDH values to ensure that the same exponent was used each time): A dishonest execution cannot continue without an honest user becoming aware of it (and aborting). Note however that an honest execution can also be stopped by a user if the adversary modifies a flow, as reflected by the bit b in the functionality. The Distributed Private Computation Protocol. This protocol is presented in Figure 2 and realizes F pwDistPrivateComp . Here, in addition to their passwords, the users are also provided a public key pk and a group element c ∈ G. For this given c ∈ G, the leader wants to obtain m = c sk . A big difference with the previous protocol is that this result will be private to the leader. But before computing it, everybody wants to be sure that all the users are honest, or at least that the combination of the passwords is compatible with the public key. This verification step is exactly the same as the computation step in the previous protocol. The protocol starts by verifying that they will be able to perform this computation, and thus that they indeed know a representation of the secret key into shares. Each user sends a commitment C i = {C i,j } j of its password as before, and the associated set of WIProofBit(C i,j ).

As in the former protocol, once this first step (which enables the users to be split into subgroups according to what values they have received) is done, the users commit again to their passwords in the value C ′ i , which will be the ones used in the rest of the protocol, and also send a signature which enables them to check that they share the same public key pk, the same group element c, and have received the same values in the first round. It thus avoids situations in which a group leader with an incorrect key obtains a correct private computation result, contrary to the ideal functionality. The protocol will thus fail if all these values are not the same to everyone, which is the result required by the functionality.

Next, the users make yet another encryption A i of their passwords, but this time they do a linear encryption of pw i in base c instead of in base g (in the above

C ′ i ciphertext): A i = Encrypt c (pw i , v i , w i ) = (g 1 v i , g 2 w i , c pw i g 3 v i +w i ).
The ciphertexts C ′ i will be used to check the possibility of the private computation (i.e. that the passwords are consistent with the public key pk = g sk ), whereas the ciphertexts A i will be used to actually compute the expected result c sk , hence the two different bases g and c in C ′ i and A i , respectively. All the users send these last two ciphertexts to everybody, along with a SSNIZK argument that the same password was used each time:

Π 2 i = SSNIZKEq g,c (C ′ i , A i ). Commitment First Step z }| { (1a) ri,j, si,j R ← Z * p
Ci,j = Commitg(pw i,j , ri,j, si,j) = (U1 pw i,j g1 r i,j , U2 pw i,j g2 s i,j , g pw i,j g3 r i,j +s i,j )

Π 0 i,j = WIProofBit(Ci,j) (SKi, VKi) ← SKG C i ={C i,j } j ,{Π 0 i,j } j ,VK i ----------------→ Commitment Second Step z }| { (1b) H = H(C1, . . . , Cn, VK1, . . . , VKn) ti, ui R ← Z * p C ′ i = Encrypt g (pw i , ti, ui) = (g1 t i , g2 u i , g pw i g3 t i +u i ) Ci = " Q " Ci,j (1) " 2 j , Q " Ci,j (2) " 2 j , Q " Ci,j (3) " 2 j « Π 1 i = SSNIZKEq g,g (Ci, C ′ i ) σi = Sign(H; SKi) C ′ i ,Π 1 i ,σ i ------→ Blinding Ring z }| { (1c) abort if one of the signatures σi is invalid γ (0) 0 = Q i C ′ i (3) = g P i pw i g3 P i t i + P i u i γ (1) 0 = g1 γ (2) 0 = g2 γ (3) 0
= g3 This round is done sequentially, for i=1,. . . ,n. Upon receiving (γ

(0) j , γ (1)
j , γ (2) j , γ (3)
j ) for j = 1, . . . , i -1, check CDH(γ (0) j-1 , γ (0) j , γ (1)
j-1 , γ (1) j ), CDH(γ (0) j-1 , γ (0) j , γ (2) j-1 , γ (2) j )
and CDH(γ

(0) j-1 , γ (0) j , γ (3) j-1 , γ (3) j ); abort if one of them is invalid αi R ← Z * p γ (0) i = (γ (0) i-1 ) α i γ (1) i = (γ (1) i-1 ) α i γ (2) i = (γ (2) i-1 ) α i γ (3) i = (γ (3) i-1 ) α i γ (0) i ,γ (1) i ,γ (2) i ,γ (3) i ------------→ (1d) given γ (0) n = g α P i pw i g3 α( P i t i + P i u i ) γ (1)
n = g1 α γ (2) n = g2 α γ (3) n = g3 α check CDH(γ (0) n-1 , γ (0) n , γ (1)
n-1 , γ (1) n ), CDH(γ (0) n-1 , γ (0) n , γ (2) n-1 , γ (2) n ) and CDH(γ (0) n-1 , γ (0) n , γ (3)
n-1 , γ (3)
n ) for all i, Pi computes G1,i = (γ (1) n ) t i , G2,i = (γ (2) n ) u i , G3,i = (γ (3) n ) t i , G4,i = (γ (3) n ) u i G 1,i ,G 2,i ,G 3,i ,G 4,i -------------→ Unblinding Ring z }| { (1e) given, for j = 1, . . . , n G1,j, G2,j, G3,j, G4,j check CDH(g1, C ′ j (1) , γ (1)
n , G1,j), CDH(g2, C ′ j (2) , γ (2)
n , G2,j), CDH(γ

(1) n , G1,j, γ (3)
n , G3,j) and CDH(γ

(2) n , G2,j, γ (3) n , G4,j) ζn+1 = γ (0) n / " Q j G3,jG4,j " = g α P j pw j
This round is done sequentially, for i from n down to 1.

given, for j from n down to i + 1, ζj, check CDH(γ After these rounds of commitments/encryptions, a verification step allows for all the players to check whether the public key and the passwords are compatible. Note that at this point, everything has become publicly verifiable so that the group leader will not be able to cheat and make the other players believe that everything is correct when it is not. Verification starts from the ciphertexts C ′ i , and involves a blinding and an unblinding ring as described above. This ends with a decision by the group leader on whether to abort the protocol (when the passwords are incompatible) or go on to the computation step. Every user is able to check the validity of the group leader's decision, as in the former protocol.

(1) j-1 , γ (1)
j , ζj, ζj+1) ζi = (ζi+1) 1/α i ζ i -→ (1f ) given, for j from i -1 down to 1, ζj, check CDH(γ (1) j-1 , γ (1) j , ζj, ζj+1) pk = ζ1
If the group leader decides to go on, the players assist it in the computation of c sk , again with the help of a blinding and an unblinding rings, starting from the ciphertexts A i . However, note that this time, the group leader does not reveal the values

G ′ 1,1 = (δ (1) n ) v 1 , G ′ 2,1 = (δ (2) n ) w 1 , G ′ 3,1 = (δ (3) n ) v 1 and G ′ 4,1 = (δ (3)
n ) w 1 at the end of the blinding ring, but it is the only one able to compute c β P j pw j .

Instead of revealing it to the others, it chooses at random an exponent x R ← Z * q and broadcasts the value c βx P j pw j . The unblinding ring then takes place as before, leading to a public value c β 1 x P j pw j that the environment cannot distinguish from random thanks to the random exponent x. Furthermore, the whole process is robust, which means that nobody can make the decryption result become incorrect. Except of course the group leader itself who broadcasts any value it wants as ζ ′ n+1 , without having to prove anything. But this does not help it to obtain a computation which it could not do alone, except the result c sk .

Note that if at some point a user fails to send its value (denial of service attack) or if the adversary modifies a flow (man-in-the-middle attack), the protocol will fail. In the ideal world this means that the simulator makes a computation delivery query to the functionality with a bit b set to zero. Because of the public verifications of the CDH values, in these blinding/unblinding rounds exactly the same sequence of passwords as in the first rounds has to be used by the players. This necessarily implies compatibility with the public key, but may be an even stronger condition.

As a side note, observe that all the blinding rings in the verification and computation steps could be made concurrent instead of sequential, to simplify the protocol. Notice however that the final unblinding ring of c sk in the computation step should only be carried out after the public key and the committed passwords are known to be compatible, and the passwords to be the same in both sequences of commitments/encryptions, i.e. after the verification step succeeded.

All the witness-indistinguishable and SSNIZK proofs and arguments will be described in Section 6. We show in Appendix B that we can efficiently simulate these computations without the knowledge of the pw i 's, so that they do not reveal anything more about the pw i 's than pk already does. More precisely, we show that such computations are indistinguishable to A under the DLin assumption.

Security Theorems.

Assuming that the proofs of membership WIProofBit and SSNIZKEq are instantiated as described in Section 6 (relying on the CDH), we have the following results, provided that DLin is infeasible in G and H is collision-resistant. The proofs of these theorems can be found in Appendix B.

Theorem 1 Let F pwDistPublicKeyGen be the concurrent multi-session extension of F pwDistPublicKeyGen . The distributed key generation protocol in Figure 1 securely realizes F pwDistPublicKeyGen for ElGamal key generation, in the CRS model, in the presence of static adversaries.

Theorem 2 Let F pwDistPrivateComp be the concurrent multi-session extension of F pwDistPrivateComp . The distributed decryption protocol in Figure 2 securely realizes F pwDistPrivateComp for ElGamal decryption, in the CRS model, in the presence of static adversaries.

As stated above, our protocols are only proven secure against static adversaries. Unlike adaptive ones, static adversaries are only allowed to corrupt protocol participants prior to the beginning of the protocol execution.

Extensions of the Protocols

Boneh-Franklin IBE Scheme [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF].

We need to compute d id = H(id) sk where H(id) is a public hash of a user's identity. This is analogous to c sk , and thus our protocol works as is. Boneh-Boyen (BB 1 ) IBE Scheme [START_REF] Boneh | Efficient selective-ID secure identity based encryption without random oracles[END_REF]. Here, d id is randomized and of the form (h 0 sk (h id 1 h 2 ) r , h 3 r ). Since (h 0 sk ) is a private value, the protocol can be adapted as follows: 1) In the commitment steps, the user also commits (once) in (2a) to a value r i , which will be its share of r. 2) Up to (2f ), everything works as before in order to check pk (there is no need to check r, constructed on the fly). 3) The blinding rings are made in parallel, one for (h 0 sk ) β , one for ((h id 1 h 2 ) r ) β , and one for (h 3 r ) β , the CDH being checked to ensure that the same r and β i are used each time. 4) The players obtain (h 0 sk (h id 1 h 2 ) r ) β and the unblinding ring is made globally for this value. An unblinding ring is also done for (h 3 r ) β , with the same verification for the exponents β i .

Commitment Steps z }| { (2a) = (1a) {C i,j ,Π 0 i,j } j --------→ (2b) = (1b) except vi, wi R ← Z * p Ai = Encrypt c (pw i , vi, wi) = (g1 v i , g2 w i , c pw i g3 v i +w i ) Π 2 i = SSNIZKEq g,c (C ′ i , Ai) C ′ i ,A i ,Π 2 i ------→ Blind. Ring z }| { (2c) = (1c) γ (1) i ,γ (2)
i ,Π 2 i --------→ (2d) = (1d) (G 1,i ,G 2,i ,G 3,i ,G 4,i ) --------------→ Unblind. Ring z }| { (2e) = (1e) ζ i -→ (2f ) = (1f ) pk ? = ζ1
Blinding Ring z }| { (3a) abort if one of the signatures σi is invalid δ

(0) 0 = Q i Ai (3) = c P i pw i g3 P i v i + P i w i δ (1) 0 = g1 δ (2) 0 = g2 δ (3) 0 = g3 P1 chooses at random β1 R ← Z * p and computes δ (0) 1 = (δ (0) 0 ) β 1 δ (1) 1 = (δ (1) 0 ) β 1 δ (2) 1 = (δ (2) 0 ) β 1 δ (3) 1 = (δ (3) 0 ) β 1
This round is done sequentially, for i=2,. . . ,n. Upon receiving (δ

(0) j , δ (1)
j , δ (2) j , δ (3)
j ) for j = 1, . . . , i -1, check CDH(δ (0) j-1 , δ (0) j , δ (1)
j-1 , δ (1) j ), CDH(δ (0) j-1 , δ (0) j , δ (2)
j-1 , δ (2) j ), CDH(δ (0) j-1 , δ (0) j , δ (3)
j-1 , δ (3)
j ); abort if one of them is invalid βi R ← Z * p δ (0) i = (δ (0) i-1 ) β i δ (1) i = (δ (1) i-1 ) β i δ (2) i = (δ (2) i-1 ) β i δ (3) i = (δ (3) i-1 ) β i δ (1) i ,δ (2) i -----→ (3b) given δ (0) n = c β P i pw i g3 β( P i v i + P i w i ) δ (1)
n = g1 β δ (2) n = g2 β δ (3) n = g3 β check CDH(δ (0) n-1 , δ (0) n , δ (1)
n-1 , δ (1) n ), CDH(δ (0) n-1 , δ (0) n , δ (2) n-1 , δ (2) n ) CDH(δ (0) n-1 , δ (0) n , δ (3) n-1 , δ (3)
n ) for i = 1, Pi computes G ′ 1,i = (δ (1)
n ) v i , G ′ 2,i = (δ (2)
n ) w i , G ′ 3,i = (δ (3)
n ) v i , G ′ 4,i = (δ (3)
n ) w i G ′ 1,i ,G ′ 2,i ,G ′ 3,i ,G ′ 4,i -------------→ Unblinding Ring z }| { (3c) given, for j = 1, . . . , n G ′ 1,j , G ′ 2,j , G ′ 3,j , G ′ 4,j
check CDH(g1, Aj (1) , δ

n , G ′ 1,j ), CDH(g2, Aj (2) , δ

n , G ′ 2,j ), CDH(δ

(1) n , G ′ 1,j , δ (3)
n , G ′ 3,j ) and CDH(δ

(2) n , G ′ 2,j , δ (3)
n , G ′ 4,j ) P1 computes G ′ 1,1 = (δ (1)
n ) v 1 , G ′ 2,1 = (δ (2)
n ) w 1 , G ′ 3,1 = (δ (3)
n ) v 1 , G ′ 4,1 = (δ (3)
n ) w 1 P1 chooses at random x R ← Z * p and computes ζ ′ n+1 = " δ (0) n / Q j (G ′ 3,j G ′ 4,j ) " x = c βx P j pw j ζ ′ n+1
---→ This round is done sequentially, for i from n down to 2. Upon receiving, for j from n down to i + 1 Linear Decryptions [START_REF] Boneh | Short group signatures[END_REF].

ζ ′ j check CDH(δ (1)
j-1 , δ (1)
j , ζ ′ j , ζ ′ j+1 ) ζ ′ i = (ζ ′ i+1 ) 1/β i ζ ′ i -→ (3d) given, for j from i -1 down to 2 ζ ′ j check CDH(γ (1)
j-1 , γ (1)
j , ζ ′ j , ζ ′ j+1 ) P1 gets ζ ′ 1 = (ζ ′ 2 ) 1/β 1 = c x P pw i = c xsk and finally c sk
Let (f = g 1/x , g, h = g 1/y ) be the public key of a linear encryption scheme, (x, y) being the private key. Assuming z = y/x, these keys can be seen as pk = (h z , h y , h) and sk = (y, z). Using these notations,

c = E pk (m; r) = (c 1 , c 2 , c 3 ) = (f r , h s , mg r+s ) m = D sk (c) = c 3 (c 1 x c 2 y
) -1 = mg r+s g -r g -s In the first protocol, the players need to use two passwords z i and y i to create the public key pk. In the second one, the commitment steps are doubled to commit to both z i and y i . As soon as pk is checked, the blinding rings are made separately, one for (c 1

x ) β and one for (c 2 y ) β . The players obtain (c 1

x c 2 y ) β and the unblinding ring can be made globally for this value. In both rings, the CDH is checked to ensure that the same β i is used each time.

6 Employed Proof Systems

GOS WI Proof of Commitments Being to Bits

Let (g 1 , g 2 , g 3 ) ∈ G 3 be a "basis" and let (U 1 , U 2 , g) ∈ G 3 be a commitment key (which is in general non-linear w.r.t. (g 1 , g 2 , g 3 ), but for simulation purposes it will be linear). Let C = (U x 1 g r 1 , U x 2 g s 2 , g x g r+s 3 ) be a commitment to x using randomness (r, s). Groth et al. [START_REF] Groth | Non-interactive zaps and new techniques for NIZK[END_REF] construct a WI proof system to show that one of two triples is linear. Applying it to (C 1 , C 2 , C 3 ) and

(C 1 U -1 1 , C 2 U -1 2 , C 3 g -1
) yields a proof that x ∈ {0, 1}, thus implements WIProofBit, in an efficient way and without random oracles. A proof consists of 6 group elements and is verified by 6 equations using 18 pairings in total. To simulate, one chooses (U 1 , U 2 , g) to be linear, thus the commitment C is linear whether x is 0 or 1. Witness indistinguishability of the proof guarantees that the case where the commitments and the proofs where constructed for x = 0 is perfectly indistinguishable from the case x = 1.

We provide below more details how to implement WIProofBit: choose t ← Z p and set

π 1,1 := U (2x-1)r 1 g r 2 1 π 1,2 = U (2x-1)r 2 g t+rs 2 π 1,3 := g -(2x-1)r g -t-(r+s)r 3 π 2,1 := U (2x-1)s 1 g -t+rs 1 π 2,2 = U (2x-1)s 2 g s 2 2
π 2,3 := g -(2x-1)s g t-(r+s)s 3

A proof π = (π 1,1 , . . . , π 2,3 ) for a commitment (C 1 , C 2 , C 3 ) is verified by checking:

e(g 1 , π 1,1 ) = e(C 1 , C 1 U -1 1 ) e(g 1 , π 1,2 )e(g 2 , π 2,1 ) = e(C 1 , C 2 U -1 2 )e(C 2 , C 1 U -1 1 ) e(g 2 , π 2,2 ) = e(C 2 , C 2 U -1 2 ) e(g 1 , π 1,3 ) -1 e(g 3 , π 1,1 π 2,1 ) = e(C 1 , C 3 g -1 )e(C 3 , C 1 U -1 1 ) e(g 3 , π 1,3 π 2,3 ) -1 = e(C 3 , C 3 g -1 ) e(g 2 , π 2,3 ) -1 e(g 3 , π 1.2 π 2,2 ) = e(C 2 , C 3 g -1 )e(C 3 , C 2 U -1 2 )
Correctness. We show correctness of two exemplary equations. The first one: e(g 1 , π 1,1 ) = e(g r 1 , U 2x-1

1 g r 1 ) which is e(C 1 , C 1 U -1
1 ) when x = 0 and e(C 1 U -1 1 , C 1 ) when x = 1. The fourth equation: e(g 1 , π 1,3 ) -1 e(g 3 , π 1,1 π 2,1 ) = e(g 1 , g (2x-1)r g t+(r+s)r 3

)e(g 3 , U

(2x-1)r 1 g r 2 1 U (2x-1)s 1 g -t+rs 1 )
= e(g r 1 , g 2x-1 )e(g 1 , g t 3 )e(g r 1 , g r+s 3 )e(g r 3 , U 2x-1 1

)e(g r 3 , g r 1 )e(g s 3 , U 2x-1 1

)e(g 3 , g -t 1 )e(g s 3 , g r 1 ) = e(g r 1 , g 2x-1 g r+s 3 )e(g r+s 3 , U 2x-1 1

)e(g r+s 3 , g r 1 ) = e(g r 1 , g 2x-1 g r+s 3 )e(g r+s 3 , U 2x-1

1 g r 1 ) = e(C 1 , C 3 g -1 )e(C 3 , C 1 U -1 1 )
The remaining equations are shown to hold analogously.

Soundness. Let (U 1 , U 2 , g) be a binding commitment key, let C = (U x 1 g r 1 , U x 2 g s 2 , g x g r+s 3 ) (note that for any C, there exist such x, r, s), and let π be a proof for C that passes verification. Define ρ := log g 1 U 1 , σ := log g 2 U 2 , τ := log g 3 g, define m i,j := log g j π i,j Then from the verification relation we get

m 1,1 = (ρx + r)(ρ(x -1) + r) m 1,2 + m 2,1 = (ρx + r)(σ(x -1) + s) + (σx + s)(ρ(x -1) + r) m 2,2 = (σx + s)(σ(x -1) + s) -m 1,3 + m 1,1 + m 2,1 = (ρx + r)(τ (x -1) + r + s) + (τ x + r + s)(ρ(x -1) + r) -m 1,3 -m 2,3 = (τ x + r + s)(τ (x -1) + r + s) -m 2,3 + m 1,2 + m 2,2 = (σx + s)(τ (x -1) + r + s) + (τ x + r + s)(σ(x -1) + s)
If we add the first, second, third and fifth equation and substract the fourth and sixth, we get 0 on the left-hand side, whereas the right-hand side simplifies to (ρ 2 + σ 2 + τ 2 + 2ρσ -2ρτ -2στ )x(x -1). Thus (ρ + σ -τ ) 2 x(x -1) = 0, which implies x = 0 or x = 1, since for a binding commitment key (a non-linear triple), we have ρ + σ = τ . Witness Indistinguishability. If the commitment key is witness hiding, i.e., (U 1 , U 2 , g) is linear w.r.t. (g 1 , g 2 , g 3 ), then C is linear, be it computed for x = 0 or x = 1. Moreover, we show that the two cases entail the same proof.

Let

U 1 = g ρ 1 , U 2 = g σ 2 , g = g ρ+σ 3 .
Let the commitment and proof be produced for x = 0, i.e., C = (g r 1 , g s 2 , g r+s 3 ) and

π 1,1 = U -r 1 g r 2 1 π 1,2 = U -r 2 g t+rs 2 π 1,3 = g r g -t-(r+s)r 3 π 2,1 = U -s 1 g -t+rs 1 π 2,2 = U -s 2 g s 2 2 π 2,3 = g s g t-(r+s)s 3 (1)
However, C could also be the result of "committing" to 1 and using randomness (r

′ = r -ρ, s ′ = s -σ), since C = (g r 1 , g s 2 , g r+s 3 ) = (U 1 g r ′ 1 , U 2 g s ′ 1 , gg r ′ +s ′ 3
). We show that using witness x = 1 and (r ′ , s ′ ), and randomness t ′ := t + ρs -σr for the proof generates the same proofs as in (1):

π ′ 1,1 = U r ′ 1 g (r ′ ) 2 1 = g ρ(r-ρ)+(r 2 -2ρr+ρ 2 ) 1 = g -ρr+r 2 1 = U -r 1 g r 2 1 = π 1,1 π ′ 1,2 = U r ′ 2 g t ′ +r ′ s ′ 2 = g σ(r-ρ)+(t+ρs-σr)+(rs-ρs-σr+ρσ) 2 = g -σr+t+rs 2 = U -r 2 g t+rs 2 = π 1,2 π ′ 1,3 = g -r ′ g -t ′ -(r ′ +s ′ )r ′ 3 = g -(ρ+σ)(r-ρ)-(t+ρs-σr)-(r+s-ρ-σ)(r-ρ) 3 = g -t-r 2 -sr+σr+ρr 3 = π 1,3 π ′ 2,1 = U s ′ 1 g -t ′ +r ′ s ′ 1 = g ρ(s-σ)-(t+ρs-σr)+(rs-ρs-σr+ρσ) 1 = g -t+rs-ρs 1 = π 2,1 π ′ 2,2 = U s ′ 2 g (s ′ ) 2 2 = g σ(s-σ)+(s 2 -2σs+σ 2 ) 2 = g σs+s 2 2 = π 2,2 π ′ 2,3 = g -s ′ g t ′ -(r ′ +s ′ )s ′ 3 = g -(ρ+σ)(s-σ)+(t+ρs-σr)-(r+s-ρ-σ)(s-σ) 3 = g t-rs-s 2 +ρsσs 3 = π 2,3

Simulation-Sound NIZK Arguments for Relations of Ciphertexts and Commitments

We construct two simulation-sound NIZK argument systems implementing the proof SSNIZKEq. Given two ciphertexts, the first proves that the encrypted messages m 1 and m 2 are in CDH w.r.t. some fixed basis (c, d), i.e., m 1 = c µ and m 2 = d µ for some µ. The second SSNIZK proves that for a given linear commitment to x and a linear encryption of g y it holds that x = y. We follow the overall approach by Groth [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] to obtain simulation soundness, but using the Groth-Sahai proof system [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] we get an efficient result: the proofs themselves are efficient, and we need not encrypt some of the witnesses in order to guarantee extractability, as the employed Groth-Sahai proofs are witness extractable.

Overview.

We start with some intuition on how [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] constructs simulation-sound proofs for satisfiability of a set of pairing product equations (PPEs) {E k } K E k=1 (and later show how to express the statements we want to prove this way). Let Σ ot be a strong one-time signature scheme1 and let Σ cma be a signature scheme that is existentially unforgeable under chosen message attack (EUF-CMA), and whose signatures σ on a message M are verified by checking a set of PPEs over a verification key vk and M , denoted {V k (vk, M, σ)} K V k=1 . The common reference string (CRS) of our argument system will contain a verification key vk for Σ cma (whose corresponding signing key serves as simulation trapdoor). When making an argument, one first chooses a key pair (vk ot , sk ot ) for Σ ot , proves a statement and, at the end, adds a signature under vk ot on the instance and the proof. The statement one actually proves is the following: to either know a witness satisfying Equations {E k } or to know a signature on vk ot valid under vk. Groth [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] shows how to construct a new set of equations which is satisfiable iff {E k } or {V k (vk, vk ot , •)} are satisfiable. Moreover, knowing witnesses for either of them, one can compute witnesses of the new set of equations. Using the techniques of [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], one then commits to the witnesses and proves that the committed values satisfy the new PPEs in a witness-indistinguishable (WI) way.

To simulate an argument, after choosing a pair (vk ot , sk ot ), one uses the trapdoor to produce a signature σ on vk ot valid under vk and uses σ as a witness for {V k (vk, vk ot , •)}. (It follows from WI of the Groth-Sahai proof that this is indistinguishable from using a witness for {E k }.) Even after seeing many proofs of this kind, no adversary is able to produce one for a new false statement: Since it has to sign the instance and the argument at the end, it must choose a new pair (vk * ot , sk * ot ) (by one-time security of Σ ot ). Soundness of Groth-Sahai proofs imposes that to prove a false statement (meaning that the first clause of the disjunction is not satisfiable), it must use a witness for the second clause, thus know a signature on vk ot . This however is infeasible by EUF-CMA of Σ cma (since we can extract the witnesses and thus a forged signature). We start by instantiating the mentioned building blocks. Building Blocks. The main motivation for our choices of instantiations of these blocks is that their security is implied by DLin only. We insist that by admitting more exotic assumptions, the efficiency of our proof system could be improved.

The Strong One-Time Signature Scheme Σ ot . We pick the scheme described in [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] (but any other would equally do), since its security follows from the discrete-log assumption which is implied by DLin.

The Waters Signature Scheme. The signature scheme from [START_REF] Waters | Efficient identity-based encryption without random oracles[END_REF] suits our purposes, it requires no additional assumption and-more importantly-signatures are verified by checking PPEs. Setup. In a bilinear group (p, G, G T , e, g), define parameters f ← G * and h := (h 0 , h 1 , . . . , h ℓ ) ← G ℓ+1 .

A secret key x ← Z p defines a public key X := g x . For ease of notation, define W(M ) := h 0 ℓ i=1 h M i i . Signing. To sign a message M ∈ {0, 1} ℓ , choose r ← Z p and define a signature as σ := (f x W(M ) r , g -r ).

Verification. A signature σ = (σ 1 , σ 2 ) is accepted for message M iff e(σ 1 , g) e(W(M ), σ 2 ) = e(f, X) (2)
Security. EUF-CMA follows from the computational Diffie-Hellman assumption which is implied by DLin.

The Groth-Sahai Proof System. Consider a set of pairing product equations

{E k } K E k=1 on variables {X i } n i=1 in G of the form n i=1 e(A k,i , X i ) n i=1 n j=1 e(X i , X j ) γ k,i,j = T k (E k ) for given A k,i ∈ G, γ k,i,j ∈ Z p , and T k ∈ G T .
Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] build a non-interactive witnessindistinguishable proof of satisfiability of {E k } from which-given a trapdoor-can be extracted the witnesses X i (we will use their instantiation with DLin): the common reference string is a (binding) key for linear commitments to group elements. The proof consists of commitments to each X i and 9 elements of G per equation proving that it is satisfied by the committed values. By DLin, replacing the CRS by a hiding commitment key is indistinguishable. In this setting now every witness {X i } n i=1 satisfying the equations generates the same distribution of proofs, which implies witness-indistinguishability of the proofs.

Moreover, we assume a collision-resistant hash function H that maps strings of elements of G to elements in Z p which we identify with their bit-representation in {0, 1} ⌈log p⌉ . Thus, when we say we sign a vector of group elements, we actually mean that we sign their hash values. Equations for Proof of Plaintexts Being in CDH. Let c, d ∈ G be fixed and let (g 1 , g 2 , g 3 ) be a linear encryption key. Given two ciphertexts C = (g r 1 , g s 2 , m 1 g r+s 3 ) and D = (g t 1 , g u 2 , m 2 g t+u 3 ), we give a set of PPEs that are satisfiable by a witness a if and only if there exists µ ∈ Z p such that m 1 = c µ and

m 2 = d µ . e(C 1 , g 3 ) = e(g 1 , a 1 ) e(C 2 , g 3 ) = e(g 2 , a 2 ) (3) e(D 1 , g 3 ) = e(g 1 , a 3 ) e(D 2 , g 3 ) = e(g 2 , a 4 ) e(C 3 a -1 1 a -1 2 , d) = e(c, D 3 a -1 3 a -1 4 )
The witness satisfying them is a := (g r 3 , g s 3 , g t 3 , g u 3 ). The first four equations prove that the logarithms of the a i 's are those of C 1 , C 2 , D 1 , D 2 w.r.t. their respective bases. Thus,

C 3 a -1 1 a -1 2 = m 1 and D 3 a -1 3 a -1 4 = m 2 and the last equation shows that (m 1 , m 2 ) is in CDH w.r.t. (c, d).

Disjunction of Equations.

Following [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] (and optimizing since the pairings have variables in common), we define a set of equations which we can prove satisfiable if we have witnesses for either (3) or (2), i.e., if we either know a satisfying (3) or σ satisfying (2). We first introduce the following new variables:

χ 1 , χ 2 φ 1 , φ 2 , φ 3 , φ 4 , φ 5 ψ 1 , ψ 2 , ψ 3
We define the following 15 equations expressing a disjunction of ( 3) and ( 2), therefore termed "(3 ∨ 2)". Equation for Disjunction:

e(g -1 χ 1 χ 2 , g) = 1 From (2): e(χ 2 , ψ -1 1 σ 1 ) = 1 e(χ 2 , ψ -1 2 W(M )) = 1 e(χ 2 , ψ -1 3 f ) = 1 e(ψ 1 , g) e(ψ 2 , σ 2 ) e(ψ 3 , X) -1 = 1 From (3): e(χ 1 , φ -1 1 g 1 ) = 1 e(χ 1 , φ -1 2 g 2 ) = 1 e(χ 1 , φ -1 3 g 3 ) = 1 e(χ 1 , φ -1 4 c) = 1 e(χ 1 , φ -1 5 d) = 1 e(C 1 , φ 3 ) e(φ 1 , a 1 ) -1 = 1 e(C 2 , φ 3 ) e(φ 2 , a 2 ) = 1 e(D 1 , φ 3 ) e(φ 1 , a 3 ) -1 = 1 e(D 2 , φ 3 ) e(φ 2 , a 4 ) = 1 e(C 3 a -1 1 a -1 2 , φ 5 ) e(φ 4 , D 3 a -1 3 a -1 4 ) = 1 Completeness.
To produce a proof we proceed as follows: If we have an assignment a for (3), we choose χ 1 := g, χ 2 := 1, satisfying thus the first equation. Moreover, set φ 1 := g 1 , φ 2 := g 2 , φ 3 := g 3 , φ 4 := c, φ 5 := d. Thus the equations of the block for (3) are satisfied, because a is a witness for (3). Since χ 2 = 1, we can set ψ i := 1 (for all i) as well, which satisfies the block for [START_REF] Barak | Secure computation without authentication[END_REF], no matter what value we set σ.

On the other hand, if we know a signature σ satisfying (2), we choose χ 1 := φ i := 1 (for all i) and χ 2 := g, ψ 1 := σ 1 , ψ 2 := W(M ), ψ 3 := f and get a satisfying assignment for any choice of a.

Soundness. We show that if (3 ∨ 2) is satisfied then either a satisfies (3) or σ satisfies (2): From the first equation we have that either χ 1 or χ 2 must be non-trivial, which either confines the values of the φ i 's to (g 1 , g 2 , g 3 , c, d) or those of the ψ i 's to (σ 1 , W(M ), f ). Now this imposes that either a satisfies (3) (by the last five equations of the block for (3)) or σ satisfies (2) (by the last equation of the block for (2)). Equations for Proof of Commitment and Ciphertext Containing the Same Value. Let (g 1 , g 2 , g 3 ) be a key for linear encryption, and let (U 1 , U 2 , g) be an associated commitment key. Let

A The UC Framework

The aim of the UC security model is to ensure that UC-secure protocols will continue to behave in the ideal way even if executed in arbitrary environments. This model relies on the indistinguishability between two worlds, the ideal world and the real world. In the ideal world, the security is provided by an ideal functionality F.

One can think of it as a trusted party in the context of multi-party computation: this functionality interacts with n users having to compute a function f . These users give their inputs to F, which gives them back their outputs. We stress that there is no communication between the users. F ensures that the computation is correct and that the users learn nothing more than their own inputs and outputs. Security is then guaranteed since an adversary A can only learn and thus modify the data of corrupted users.

In order to prove that a protocol Π emulates F, one considers an environment Z that provides inputs to the users and acts as a distinguisher between the real world (with actual users and a real adversary that can control some of them and also the communication among them) and the ideal world (with dummy users interacting only with the ideal functionality F, and a simulated adversary also interacting with F). We then say that the protocol Π realizes F if for all polynomial adversaries A, there exists a polynomial simulator S such that no polynomial environment Z can distinguish between the two worlds (one with F and S, the other with Π and A) with a significant advantage.

Since there are several copies of a functionality F running in parallel, each one has a unique session identifier sid. All the messages must contain the SID of the copy they are intended for. As in [START_REF] Canetti | Universally composable password-based key exchange[END_REF], we assume for simplicity that each protocol realizing F has inputs containing its SID. We also assume that each user starts a session by specifying the SID of F, its identity P i , its password pw i , and the identities of the other users P id.

A shortcoming of the UC theorem is that is says nothing about protocols sharing state and randomness (it ensures the security of a single unit only). Here, since we need a common reference string for all instances of the protocol, we need a stronger result, provided by Canetti and Rabin in [START_REF] Canetti | Universal composition with joint state[END_REF] and called universal composability with joint state. Informally, they define the multi-session extension F of F, which basically runs multiple instances of F, where each of them is identified by a sub-session identifier ssid. F has to be executed with sid and ssid. When it receives a message m containing ssid, it hands m to the copy of F having the SSID ssid (or invokes a new one if such copy does not exist).

For the sake of generality, we shall describe all the functionalities in the context of adaptive adversaries, that are allowed to corrupt users whenever they like to. For simplicity, however, we shall only prove the security of our constructions in presence of static adversaries, that have to choose which users to corrupt before the beginning of the execution of the protocol, either implicitly in the key generation protocol (when the adversary starts playing as one of the parties, choosing by himself the password), or explicitly in the decryption protocol (asking a corruption before a new decryption session).

In the UC model, a corruption implies a complete access to the internal memory of the users (which here means the password and the internal state); in addition, the adversary takes the entire control of the corrupted user, and can modify its behavior for the remaining of the protocol.

B Proof of the Security Theorems

In this section we give the proof that the protocols described on Figures 1 and2 (in Section 4) respectively realize the functionalities F pwDistPublicKeyGen and F pwDistPrivateComp . These ideal functionalities have been described in Section 2 and can be found in Figures 3 and4. The split functionality is given in Figure 5.

The functionality F pwDistPublicKeyGen is parametrized by a security parameter k and an efficiently computable function PublicKeyGen : (pw 1 , pw 2 , . . . , pw n ) → pk that derives a public key pk from a set of passwords. Denote by role either player or leader. The functionality interacts with an adversary S and a set of parties P1,. . . ,Pn via the following queries: Initialization. Upon receiving a query (newSession, sid, P id, Pi, pw i , role) from user Pi for the first time, where P id is a set of at least two distinct identities containing Pi, ignore it if role = leader and if there is already a record of the form (sid, P id, * , * , leader). Record (sid, P id, Pi, pw i , role) and send (sid, P id, Pi, role) to S. Ignore any subsequent query (newSession, sid, P id ′ , * , * , * ) where P id ′ = P id. If there are already |P id| -1 recorded tuples (sid, P id, Pj, pw j ) for Pj ∈ P id \ {Pi}, and exactly one of them such that role = leader, then while recording the |P id|-th tuple, also record (sid, P id, ready) and send this to S. Otherwise, record (sid, P id, error) and send (sid, P id, error) to S. Key Computation. Upon receiving a message (compute, sid, P id) from the adversary S where there is a recorded tuple (sid, P id, ready), then compute pk = PublicKeyGen(pw 1 , . . . , pw n ) and record (sid, P id, pk). Leader Key Delivery. Upon receiving a message (leaderDeliver, sid, P id, b) from the adversary S for the first time, where there is a recorded tuple (sid, P id, pk) and a record (sid, P id, Pi, pwi, leader), send (sid, P id, pk) to Pi and to S if b = 1, or (sid, P id, error) otherwise. Record (sid, P id, sent) and send this to S. Player Key Delivery. Upon receiving a message (playerDeliver, sid, P id, b, Pi) from S where there are recorded tuples (sid, P id, pk), (sid, P id, Pi, pwi, player) and (sid, P id, sent), send (sid, P id, pk) to Pi if b = 1, or (sid, P id, error) otherwise. User Corruption. If S corrupts Pi ∈ P id where there is a recorded tuple (sid, P id, Pi, pw i ), then reveal pw i to S. If there also is a recorded tuple (sid, P id, pk) and if (sid, P id, pk) has not yet been sent to Pi, send (sid, P id, pk) to S.

Fig. 3. The Distributed Key Generation Functionality FpwDistPublicKeyGen

The proof of the distributed key generation protocol is similar to that of the distributed private computation given below, with the added simplification that there is no verification step and the difference that all the users receive the result in the end (which corresponds exactly to what happens in the private computation protocol at the end of the verification step, where everyone also receives the result). Thus, we refer to the proof of the private computation protocol for the workings of the simulation. The additional simplification implied by the adversary receiving the result in the end will be given in remarks. The structure of the proof is similar to that of Abdalla et al. in [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF].

B.1 Methodology of the Proof

The objective of the proof is to construct, from a real-world adversary A, an ideal-world simulator S, so that the behavior of A in the real world and that of S in the ideal world are indistinguishable to

The functionality F pwDistPrivateComp is parametrized by a security parameter k and three functions. PublicKeyVer is a boolean function defined by PublicKeyVer : (pw 1 , pw 2 , . . . , pw n , pk) → b, where b = 1 if the passwords and the public key are compatible, b = 0 otherwise. SecretKeyGen is a function SecretKeyGen : (pw 1 , pw 2 , . . . , pw n ) → sk, where sk is the secret key obtained from the passwords. Finally, PrivateComp is a private-key function PrivateComp : (sk, c) → m, where sk is the secret key, c is the function input (e.g., a ciphertext) and m the private result of the computation (e.g., the decrypted message). Denote by role either player or leader. The functionality interacts with an adversary S and a set of parties P1,. . . ,Pn via the following queries:

-Initialization. Upon receiving a query (newSession, sid, P id, Pi, pk, c, pw i , role) from user Pi for the first time, where P id is a set of at least two distinct identities containing Pi, ignore it if role = leader and if there is already a record of the form (sid, P id, * , * , * , * , leader). Record (sid, P id, Pi, pk, c, pw i , role), mark it fresh, and send (sid, P id, Pi, pk, c, role) to S. Ignore any subsequent query (newSession, sid, P id ′ , * , * , * , * , * ) where P id ′ = P id.

If there are already |P id| -1 recorded tuples (sid, P id, Pi, pk, c, pw i , role), and exactly one of them such that role = leader, then after recording the |P id|-th tuple, verify that the values of c and pk are the same for all the users. If the tuples do not fulfill all of these conditions, report (sid, P id, error) to S and stop. Otherwise, record (sid, P id, pk, c, ready) and send it to S. -Private Computation. Upon receiving a message (compute, sid, P id) from S where there is a recorded tuple (sid, P id, pk, c, ready), then

• If all records are fresh and PublicKeyVer(pw 1 , . . . , pw n , pk) = 1, then compute sk = SecretKeyGen(pw 1 , . . . , pw n ) and m = PrivateComp(sk, c), and store (sid, P id, m).

Next, for all Pi ∈ P id mark the record (sid, P id, Pi, pk, c, pw i , role) as complete. any environment Z. The ideal functionality is specified in Figure 4 and described in Section 2. Since we use the joint state version of the UC theorem, we implicitly consider the multi-session extension of this functionality, and thus replace all sid by (sid, ssid). Note that the passwords of the users depend on the sub-session considered. For sake of simplicity, we denote them by pw i , but one should implicitly understand pw i,ssid .

B.2 Details of the Proof

In this proof, we incrementally define a sequence of games starting from the one describing a real execution of the protocol and ending up with game G 10 which we prove to be indistinguishable with respect to the ideal experiment.

The simulator S is incrementally defined in the games, ending up to be completely defined in G 10 (though we do not rewrite him entirely in this game since his behavior was described in the previous games). This final game will then be proven to be indistinguishable to the ideal world, showing that we indeed have constructed an ideal simulator to the real-world adversary A.

In the first games, the simulator has actually access to all the information given to the users by the environment, in particular their passwords. In the last game, we nearly are in the ideal game so that the users do not exist anymore: S has only access to the information transmitted by his queries to the functionality (not to the passwords, for instance) and he has to simulate the users entirely by himself. Between these two situations, the simulator lives in a world which is not really real, not really ideal.

Following [START_REF] Abdalla | Distributed public-key cryptography from weak secrets[END_REF], in order to formally model this situation, we chose to consider two hybrid queries that S can ask to the functionality all along the games. The CompatiblePwd query checks whether the passwords of the users are compatible with the passwords of the other users and the public key of the group leader. And the Delivery query gives the result to the group leader-and to the adversary if the former is corrupted.

Note that since in the first games, the simulator has access to the users' inputs, he knows their passwords. In such a case a CompatiblePwd or Delivery query can be easily implemented by letting the simulator look at the passwords owned by the users. When the users are entirely simulated, without the knowledge of their passwords, S will replace the queries above with the real Private Computation and Leader Computation Delivery queries to the functionality.

We say that a flow is oracle-generated if it was sent by an honest user and arrives without any alteration to the user it was meant to. We say it is non-oracle-generated otherwise, that is either if it was sent by an honest user and modified by the adversary, or if it was sent by a corrupted user or a user impersonated by the adversary (more generally denoted by attacked user, that is, a user whose password is known to the adversary).

Game G 0 :

Real game. In the real game, we know that the protocol cannot continue past the two initial commitment rounds if there is any inconsistency between the passwords pw i used in all the commitments. Any inconsistency will violate the SSNIZK language, and because the proof system with honest setup is assumed to be sound, it is not feasible for anyone to prove a false statement. Similarly, the copies of pk and c held by all the users and the commitments received in the first round are assumed to be the same for all users, thanks to the one-time signatures. Finally, the two rounds of blinding and unblinding serve to verify the consistency of pk with the pw i 's, and to compute the final output c sk , respectively. To be precise, the security of these rounds follows from our assumptions: cheating in the computation of the blinding/unblinding rounds without getting caught is impossible since the CDH are publicly verifiable. Finally note that the players are not granted the right to check that the group leader uses the correct exponents when it publishes ζ ′ n+1 . This could only be a sensible issue when the group leader is corrupted, but we will show that it cannot get any additional information.

Game G 1 : Simulation of the SSNIZK proofs. This game modifies how the zero-knowledge proofs are performed. Specifically, instead of using the honest-prover strategy, all the proofs Π 1 j and Π 2 j in which the prover is an honest user are simulated using the zero-knowledge simulator (also note that the common reference string γ is also simulated once and for all). Since the proofs are concurrent zero-knowledge, the environment cannot distinguish between the two games G 1 and G 0 . That is, if an environment could distinguish between these hybrids (ie become aware that the two commitments possibly commit to/encrypt different passwords when the simulator claim the passwords are the same), of the SSNIZK proofs. If the adversary has not generated the first commitments, he will not be able to construct valid proofs, with unknown witnesses.

The simulator first asks a Computation query along with a Delivery query to the functionality, which gives him either complete or error. In the second case, S continues the simulation as in the former game, and we allow him to use the passwords of the users (we show in G 7 how to get rid of the use of the passwords).

We now consider the first case and sum up briefly the circumstances which led us here: The users are honest, they have the same c and pk, and their passwords are compatible with the public key. Then, S keeps on using the passwords pw 2 , . . . , pw n for the n -1 last users, and he is able to set g f pw ′ 1 (without knowing pw ′ 1 ) such that all the passwords are compatible with the value g sk , using the equation:

g f pw ′
1 g f pw 2 . . . g f pw n = g sk = pk But he still uses c f pw 1 for the last commitment, since he does not know c sk . Notice that he will give once again a proof for a false statement. The simulator then continues honestly the game, by choosing random values α i and β i and executing the four rings as described in the protocol. Note that S sends a random value for ζ ′ n+1 = c skβx on behalf of the (honest) group leader. This means that the simulator does not know x, but such an x exists to be consistant with the actual (but unknown) values of β and sk. The following is then perfectly indistinguishable since the blinding factor x will never be publicly removed. Then, no information about x leaks. In the Delivery query, the bit b is chosen as described in G 5 . Finally note that the simulator never needed the knowledge of the passwords of the users.

Due to the non-malleability of the commitments, along with their hiding property, this game is indistinguishable from G 5 .

Remark.

Note that for the distributed key generation protocol, things would have been simpler. In this case, the simulator not only receives complete or error, but the exact value of pk = g sk . He is thus able to modify pw 1 such that the passwords are compatible with the public key. This is similar to what the simulator will do in G 8 for c sk when the group leader is corrupted. Indeed, in this case, the simulator will learn the exact value of c sk from the functionality (as he does for g sk here).

Game G 7 :

Simulation of honest users with incompatible passwords. This game starts exactly as in G 6 . If there are attacked users, the simulator is granted the right to use the passwords of all the users, and continues as in G 5 .

If all the users are honest, he continues as in G 6 , by asking a CompatiblePwd query. We showed in G 6 how to deal with the case where the functionality returns correct (that is, when the passwords are compatible with the public key) without using the passwords of the users. We now consider the other case and show how to treat it. Thus, we suppose that the CompatiblePwd query returns an error, meaning that the passwords are incompatible with the public key.

The simulator then computes commitments of the values g f pw i and c f pw i for all the users (there is no need that their passwords should be compatible). He sends them along with the corresponding proofs to the other users. The simulator then continues honestly the game, by choosing random values α i and β i and executing the two first rings as described in the protocol. Note that the real passwords of the users are not needed anymore. Since the protocol will fail at the verification step, the simulator will set the bit b to 0 in the Delivery query.

Since the commitments are hiding, this game is indistinguishable from G 6 .

Game G 8 : Simulation in case of compatible passwords in presence of an adversary. This game starts exactly as in G 5 . The case where all the users are honest has been dealt with in the games G 6 and G 7 . We now consider the case in which the adversary controls a set of users. Recall that we denote by n h the number of honest users. Note that choosing g 1 , g 2 and g 3 allows S to know the discrete logarithm of g 1 and g 2 in base g 3 . Since the commitments are linear ciphertexts, knowledge of these discrete logarithms will allow the simulator to decrypt the ciphertexts and then extract the passwords used by A in the first-round commitments.

(The actual extraction requires taking discrete logarithms, but this can be done efficiently using generic methods, because the discrete logarithms to extract are bits. And the small size is enforced by a WIProofBit.)

After this first round, the simulator thus extracts the passwords used by the adversary in the commitments he sent. Note that the honest users are not supposed to have received the same values from the adversary: We only know that these values are non-oracle-generated, but not necessarily equal. Thus, the simulator chooses at random one of the commitments received from an attacked user to extract and recover its password. One could argue that there is a problem here, but note that the signature given with the second commitment will not be accepted if the value H is not the same for all users (recall that we have assumed a collision-resistant hash function for the computation of H).

Once S has recovered all the passwords of the attacked users, he asks a CompatiblePwd query. If this query returns incorrect, we continue the simulation as in G 5 (we show in G 9 how to deal with this case without using the passwords of the users).

We now suppose that the query returns correct. This provides the following equation: Recall that the passwords of the honest users were chosen at random, so there is no chance that they should be compatible with the (common) public key. S thus keeps its n h -1 first passwords and computes a replacement value g f pw ′ in h thanks to the above equation. Remark that he does not know the corresponding password pw ′ in h . In the second round, the simulator must produce commitments that are compatible with the public key. To do so, he makes commitments on the same random passwords as before for the n h -1 first honest users, and for the last one creates a commitment as a linear encryption of g f pw ′ in h . He sends them all out. In the same round, the simulator must also produce another series of password commitments, this time as linear encryptions of c pw i and not g pw i .

We now have to consider two cases. First, suppose that the group leader is attacked. The simulator computes the commitments normally for the first n h -1 honest players using the simulated passwords. For the last player P in h , he asks a Delivery query in order to recover c sk , and computes the missing commitment as a linear encryption of c Otherwise, if the group leader is not attacked, the simulator will not recover c sk . We thus proceed as in G 6 , using incorrect values c f pw i j for the honest players, not compatible with c sk . S sends out the commitments along with the proofs of consistency. Note that in the second case he will prove a false statement for the group leader.

The simulator then continues the game honestly, by choosing random values α i and β i and executing the four rings as described in the protocol. Everything is simulated perfectly if the group leader is attacked (with incorrect passwords, though, but compatible with c sk ). If the group leader tries to cheat in the value ζ ′ n+1 , the unblinding ring will still use the values β i that it does not know, and S can simulate this unblinding ring correctly. The simulation of the honest players is done independently of the group leader (whether it plays honestly or not), so that it cannot learn anything more than the simulator already knows, that is c sk .

Otherwise, the last step fails, without any bad consequence on the protocol since the group leader ends the ring (as in G 6 ). The bit b of the Delivery query is chosen as described in G 5 : if something goes wrong and the protocol halts, then b = 0, otherwise b = 1.

Since the commitments are computationally hiding under the DLin assumption, the adversary cannot become aware that the passwords are not the good ones, or that the password for the user P in h changed between the two rounds of commitments. This game is indistinguishable from G 7 .

Game G 9 :

Simulation in case of incompatible passwords in presence of an adversary. This game starts exactly as in G 8 . We now suppose that the CompatiblePwd query returns incorrect. Since the verification step will fail, S can keep all the values pw i 1 , . . . , pw in h for the second round of commitments (in base g as in base c). He then sends these commitments along with the corresponding proofs.

He then continues honestly the protocol (without knowing the real passwords of the users) until it fails, at the verification step. The simulator then asks a CompatiblePwd query, and a Delivery query with bit b = 0. For the same reasons than in the former game, G 9 is indistinguishable from G 8 .

Game G 10 : Indistinguishability with the ideal world. We have shown that S is able in any case to simulate the whole protocol without using the passwords of the users. Thus, we can now suppose that he does not know these passwords.

The only difference between G 9 and G 10 is that the CompatiblePwd query is replaced by a Private Computation query to the functionality, and the Delivery by a Leader Computation Delivery query. If a session aborts or terminates, S reports it to A. If a session terminates with a message m, then S makes a Delivery call to the functionality, specifying a bit b = 1. If the protocol fails, he gives a bit b = 0.

We now show that this last game G 10 is indistinguishable from the ideal-world experiment IWE. More precisely, we have to show that the group leader receives a correct message in G 10 if and only if it receives a correct message in the ideal world.

First, if the users share compatible passwords, the same public key, the same ciphertext, and all the flows are oracle-generated until the end of the game, then the group leader will obtain a correct message, both in G 10 (from G 6 ) and the ideal world. More precisely, the protocol will end on a random value in G 6 , but nobody will be able to distinguish it from the real value. And the leader will obtain the correct value from the Delivery query. Second, if they share compatible passwords, the same public key, the same ciphertext, and if the group leader is corrupted, then the group leader will also receive a correct message (from G 8 ). Third, if they do not share compatible passwords or if some received flows differ from one user to an other, then the group leader will get an error (from G 7 and G 9 in the first case, and due to the bit b otherwise).

This establishes that, given any adversary A that attacks the protocol Π in the real world, we can build a simulator S that interacts with the functionality F in the ideal world, in such a way that the environment cannot distinguish which world it is in.

Fig. 1 .

 1 Fig. 1. Individual steps of the distributed key generation protocol

Fig. 2 .

 2 Fig. 2. Individual steps of the distributed decryption protocol

Fig. 5 .

 5 Fig. 5. Split Functionality sF

•

  In any other case, store (sid, P id, error). When the computation result is set, report the outcome (either error or complete) to S.-Leader Computation Delivery. Upon receiving a message of the form (leaderDeliver, sid, P id, b) from the adversary S, where both there is a recorded tuple (sid, P id, m) such that m ∈ {well-formed messages}∪{error}, and there exists a record (sid, P id, Pi, pk, c, pw i , leader), send (sid, P id, m) to Pi if b is equal to 1, or send (sid, P id, error) if b is equal to 0. If the group leader Pi is corrupted, then send (sid, P id, m) to S as well (note that S gets m automatically if Pj is corrupted). -User Corruption. If S corrupts Pi ∈ P id where there is a recorded tuple (sid, P id, Pi, pk, c, pw i , role), then reveal pw i to S. If role = leader, if there also is a recorded tuple (sid, P id, m), and if (sid, P id, m) has not yet been sent to Pi, then also send (sid, P id, m) to S. Upon receiving (Init, sid) from party Pi, send (Init, sid, Pi) to the adversary. -Upon receiving a message (Init, sid, Pi, H, sidH ) from A, where H is a set of party identities, check that Pi has already sent (Init, sid) and that for all recorded (H ′ , sid H ′ ), either H = H ′ and sidH = sid H ′ or H and H ′ are disjoint and sidH = sid H ′ . If so, record the pair (H, sidH ), send (Init, sid, sidH ) to Pi, and invoke a new functionality (F , sidH ) denoted as FH and with set of honest parties H. Computation: -Upon receiving (Input, sid, m) from party Pi, find the set H such that Pi ∈ H and forward m to FH . -Upon receiving (Input, sid, Pj, H, m) from A, such that Pj / ∈ H, forward m to FH as if coming from Pj. -When FH generates an output m for party Pi ∈ H, send m to Pi. If the output is for Pj / ∈ H or for the adversary, send m to the adversary.

	Fig. 4. The Distributed Private Computation Functionality FpwDistPrivateComp
	Given a functionality F, the split functionality sF proceeds as follows:
	Initialization:
	-

c Springer-Verlag, 2010.

A signature scheme is strong one-time if no adversary, after getting a signature σ on one message m of his choice, can produce a valid pair (m * , σ * ) = (m, σ).

Acknowledgments

This work was supported in part by the European Commission through the ICT Program under Contract ICT-2007-216676 ECRYPT II and by the French ANR-07-SESU-008-01 PAMPA Project.

C = (U x 1 g r 1 , U x 2 g s 2 , g x g r+s 3 ) be a commitment to x and D = (g v 1 , g w 2 , g y g v+w

3

) be an encryption of g y . We prove that x = y: the witness is (a 1 = U x 1 , a 2 = U x 2 , a 3 = g x , a 4 = g r 3 , a 5 = g v 3 ) satisfying e(a1, U2) = e(U1, a2) e(C1a -1 1 , g3) = e(g1, a4) e(D1, g3) = e(g1, a5) e(a1, g) = e(U1, a3) e(C2a -1 2 , g3) = e(g2, C3a -1 3 a -1 4 ) e(D2, g3) = e(g2, D3a -1 3 a -1 5 )

The equations in the first column show that a 1 = U z 1 , a 2 = U z 2 , a 3 = g z for some z, the second column proves that

) is linear (i.e., C commits to z) and the third that D is an encryption of a 3 = g z .

Transformation. Transforming Equations ( 4) and (2) to a set (4∨2) analogously to the construction of (3∨2), we get a set of 16 equations we can prove satisfiable adding 10 new witnesses if either we have a witness for C being a commitment to some x and D an encryption of g x , or we know a signature. (Associate the φ i 's to U 1 , a 1 , g 1 , g 2 and g 3 .) Assembling the Pieces. We describe the SSNIZK proof system for "plaintexts in CDH". The one for "commitment and ciphertext contain the same value" is obtained by replacing (3 ∨ 2) by (4 ∨ 2).

Common Reference String. Generate a key pair (vk, sk) for Waters' signature scheme, and a CRS crs GS for the Groth-Sahai proof system. Let crs := (vk, crs GS ) and let the simulation trapdoor be sk. Proof. Let (C, D) ∈ G 6 be an instance and a a witness satisfying [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF]. Generate a key pair (vk ot , sk ot ) for Σ ot ; using witness a, make a Groth-Sahai proof π GS w.r.t. crs GS of satisfiability of (3 ∨ 2) with M := vk ot ; produce a signature σ ot on (C, D, vk ot , π GS ) using sk ot . The proof is π := (vk ot , π GS , σ ot ) Verification. Given π, verify σ ot on (C, D, vk ot , π GS ) under vk ot , and π GS on the respective equations. Simulation. Proceed as in Proof, but using sk produce σ on vk ot and use that as a witness for

Theorem 3 Under the DLin assumption, the above is a simulation-sound NIZK argument for the encryptions of two linear ciphertexts forming a CDH-pair.

Using the ideas given in the overview, the proof is analogous to that in [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] except that we do not require perfect soundness and that we use the extraction key for crs GS to extract a forged signature on vk ot directly rather than adding encryptions to the proof. one could construct an adversary that breaks the zero-knowledge property of the proof protocol. We assume that he still knows the passwords of the players so that everything else is done correctly.

Game G 2 : Use of a linear basis (U 1 , U 2 , U 3 ). In this game, the simulator is allowed to swap the basis (U 1 , U 2 , U 3 ) for a linear one used for C i . This will allow him to simulate properly, and in particular to be able to extract the password committed in the values C i 's. The adversary cannot become aware of this change thanks to the DLin assumption. The adversary still knows the passwords of the players and computes everything honestly. Furthermore, the soundness of the SSNIZK proofs still holds thanks to the indistiguishability of the 3-tuples (relying on the DLin assumption). Thus, this game is indistinguishable from the previous one.

Game G 3 : Simulation of the first round of commitments. The passwords are still known to the simulator, but he uses dummy passwords for the first round of commitments. He then uses the real ones for the second rounds of commitments (C ′ i and A i ). Thanks to the simulation-soundness of the proofs, the adversary cannot become aware that the simulator is proving a wrong statement in (1b). Furthermore, thanks to the witness indistinguishability of the first proof (since the basis is linear), the environment cannot become aware that we are using dummy passwords in C i . This game is thus indistinguishable from the previous one.

Game G 4 : Use of a non-linear basis. Everything works as before except that the simulator comes back with a non-linear basis in the first step. The simulator is then allowed to program (once and for all) the totality of the common reference string. This is indistinguishable from the previous game due to the DLin assumption.

Game G 5 : Simulation of the first round of commitments. From this game on, S simulates the first rounds of commitments in the following way. We suppose that he still knows the passwords of the players. Let n h be the number of honest users, i.e. the users S has to simulate. S chooses at random n h dummy passwords pw i 1 , . . . , pw in h on behalf of each one of these users. Once all these values are set, S computes the first-round commitments and send them to everybody.

S then learns from the functionality whether the users all share the same c and pk or not. In the second case, S aborts the game. In the first case, S goes on the execution of the protocol in a honest way, using the real passwords of the users. Note that he will have to prove false statements, which is not a problem since the proofs are simulated since the former games. In the end, if the execution succeeds, he asks a Computation query, and he finally sets the bit b to 1 in the Delivery query. Otherwise, if the execution fails, he also asks a Computation query but sets the bit b to 0 for the delivery.

Since the first-round commitment is hiding, the adversary cannot become aware of the transformation of the pw i 's into pw i 's: this game is indistinguishable from G 4 .

Game G 6 : Simulation of honest users with compatible passwords. From this game on, we show how to simulate the users without using their passwords. More precisely, the simulator is still supposed to know the passwords of the users, but little by little we are going to show that he actually never needs them in the simulation. This will ensure in the end that the simulator does not need the knowledge of the passwords in order to perform the simulation honestly.

Note that from this game on, we can suppose that all the c and the pk are identical, since the case of different values has been dealt with in the former game (and the simulator aborts the protocol in this case). The first round of commitments is simulated as in G 5 . We now face two cases.

First, if there are attacked users among the group, the simulation continues as in the former game, S being allowed to use the passwords of all the users. (We show in G 8 and G 9 how to simulate in this case without using the passwords.)

Second, if all users are honest, we show how to continue the simulation without the help of the passwords. Note that if at some point some flows are non-oracle-generated, the protocol will abort: In this case, the simulator will set the bit b to 0 in the Delivery query. This comes from the non-malleability