Chloé Hébant

Duong Hieu Phan

David Pointcheval

Linearly-Homomorphic Signatures and Scalable Mix-Nets

Keywords: Anonymity, random shuffling, linearly-homomorphic signatures

Anonymity is a primary ingredient for our digital life. Several tools have been designed to address it such as, for authentication, blind signatures, group signatures or anonymous credentials and, for confidentiality, randomizable encryption or mix-nets. When it comes to complex electronic voting schemes, random shuffling of authenticated ciphertexts with mix-nets is the only known tool. However, it requires huge and complex zero-knowledge proofs to guarantee the actual permutation of the initial ciphertexts in a privacy-preserving way. In this paper, we propose a new approach for proving correct shuffling of signed ElGamal ciphertexts: the mix-servers can simply randomize individual ballots, which means the ciphertexts, the signatures, and the verification keys, with an additional global proof of constant size, and the output will be publicly verifiable. The security proof is in the generic bilinear group model. The computational complexity for the each mix-server is linear in the number of ballots. Verification is also linear in the number of ballots, but independent of the number of rounds of mixing. This leads to a new highly scalable technique. Our construction makes use of linearly-homomorphic signatures, with new features, that are of independent interest.

Introduction

A shuffle of ciphertexts is a set of ciphertexts of the same plaintexts but in a permuted order such that it is not possible to trace back the senders after decryption. It can be used as a building block to anonymously send messages: if several servers perform a shuffle successively, nobody can trace the messages. More precisely, one honest mix-server suffices to mask the order of the ciphertexts even if all the other ones are dishonest. Moreover increasing the number of mix-servers leads to a safer protocol but also increases its cost. The succession of shuffles constitutes the notion of a mix-net protocol introduced by Chaum [Cha81], with applications to anonymous emails, anonymous routing, but also e-voting.

State of the Art

Usually, a shuffle of ciphertexts is a permutation applied to randomized ciphertexts. Randomization of the ciphertexts provides the privacy guarantee, but one additionally needs to prove the permutation property. This last step requires huge and complex zero-knowledge proofs. In the main two techniques, Furukawa and Sako [FS01] make proofs of permutation matrices and Neff [Nef01] considers polynomials which remain identical with a permutation of the roots. While the latter approach produces the most efficient schemes, they need to be interactive. Groth and Ishai [GI08] exploited this interactive approach and proposed the first zero-knowledge argument for the correctness of a shuffle with sub-linear communication complexity, but computational complexity is super-linear which was then improved by Bayer and Groth [BG12]. As this is a public random coin interactive Zero-Knowledge protocol, the Fiat-Shamir heuristic [FS87] can be applied to make it non-interactive in the random oracle model. However, with multiple mixing steps, which are required if one wants to guarantee anonymity even if some mix-servers are malicious, the final proof is linear in this number of steps, and the verification cost becomes prohibitive.

The former approach with proof of permutation matrix is more classical, with many candidates. Groth and Lu [GL07] proposed the first non-interactive zero-knowledge (NIZK) proof of shuffle without random oracles, using Groth-Sahai proofs with pairings [GS08], but under nonstandard computational assumptions that hold in the generic bilinear group model. Even with that, computations are still very expansive because the overhead proof is linear in N n, where n is the number of ciphertexts and N the number of mixing rounds. In addition, they needed a Common Reference String (CRS) linear in n. More recently,Fauzi et al. [FLSZ17] proposed a new pairing-based NIZK shuffle argument to improve the computation for both the prover and the verifier, and improved the soundness of the protocol. But they still had a CRS linear in the number of ciphertexts, and the soundness holds in the generic bilinear group model.

We propose a totally new approach that handles each ciphertext in an independent way, with just a constant-size overhead in the final proof. The overhead after each shuffle can indeed be updated to keep it constant-size. From our knowledge, this is the most scalable solution. It relies on Groth-Sahai proofs with pairings [GS08] and a new computational assumption that holds in the generic bilinear group model. As a consequence, assumptions are quite similar to [GL07], but we have a constant-size CRS and a constant-size overhead proof.

Compared to the most efficient schemes to date, namely the Fauzi et al.'s scheme [FLSZ17], our scheme is also proven in the generic bilinear group model, but the CRS is shorter: just 8 group elements in contrast to a CRS with a number of group elements linear in the number of ballots. Moreover, in our scheme, the proof is constant-size, independently of the number of mixing rounds, while the proof of Fauzi et al.'s scheme grows linearly in the number of rounds. Hence, from 2 rounds, our scheme has a better verifier's computation cost and for 3 rounds the proof sizes are almost the same with the two schemes. With more rounds, our construction gets much better compared to the Fauzi et al.'s scheme, and the input ballots already contain signatures by their senders, which makes it quite attractive for electronic voting.

Our Approach

In our shuffle, each ciphertext C i (encrypted vote in the ballot, in the context of electronic voting) is signed by its sender and the mix-server randomizes the ciphertexts {C i } and permutes them into the set {C i } in a provable way. The goal of the proof is to show the existence of a permutation Π from {C i } to {C i } such that for every i, C Π(i) is a randomization of C i . Then, the output ciphertexts can be mixed again by another mix-server.

Our approach avoids the proof of an explicit permutation Π on all the ciphertexts (per mixing step) but still guarantees the appropriate properties deeply using the linearly-homomorphic signature schemes:

each user is associated to a signing/verification key-pair for a linearly-homomorphic signature scheme [BFKW09], and uses it to sign his ciphertext and a way to randomize it. This guarantees that the mix-server will only be able to generate new signatures on randomized ciphertexts, which are unlinkable to the original ciphertexts, due to the new random coins. However, unchanged verification keys would still allow linkability; each verification key of the users is thus also certified with a linearly-homomorphic signature scheme, that allows randomization too as well as adaptation of the above signature on the ciphertext, and provides unlinkability.

When talking about linearly-homomorphic signature schemes, we consider signatures that are malleable and that allow to sign any linear combination of the already signed vectors [BFKW09].

In order to be able to use this property on the latter scheme that signs the verification keys of the former scheme, it will additionally require some homomorphic property on the keys. However, whereas ciphertexts are signed under different keys, which excludes combinations, the verification keys are all signed under the authority's key. Furthermore, a linearlyhomomorphic signature scheme not only allows multiplication by a constant, but also linear combinations, which would allow combinations of keys and thus, possibly, of ballots. In order to avoid such combinations, we require a tag-based signature, that allows only linear combinations between signatures using the same tag. As such signatures allow to derive a signature of any message in the sub-vector space spanned by the initially signed messages, when there is no tag, only one sub-vector space can be considered, whereas tags allow to deal with multiple sub-vector space. In the latter case, one thus talks about Linearly-Homomorphic Signature (LH-Sign), whereas the former case is named One-Time Linearly-Homomorphic Signature (OT-LH-Sign).

In the Appendix C, we provide a generic conversion from OT-LH-Sign to LH-Sign, using Square Diffie-Hellman tuples (g, g w i , g w 2 i ) for the tags. So, starting from an efficient OT-LH-Sign, one can derive all the tools needed for our mix-net application. However, in the body of the paper, we also provide a more efficient LH-Sign version, and we thus focus on it in the following.

Unforgeability of the signature schemes will essentially provide the soundness of the proof of correct mixing: only permutations of ballots are possible. Eventually, unlinkability (a.k.a. zeroknowledge property) will be satisfied thanks to the randomizations that are indistinguishable for various users, under some DDH-like assumptions, and the final random permutation of all the ciphertexts. With the above linear homomorphisms of the signatures, we can indeed guarantee that the output C j is a randomization of an input C i , and the verification keys are unlinkable.

More precisely, the signature unforgeability will guarantee that all the ballots in the output ballot-box come from legitimate signers: we will also have to make sure that there is no duplicates, nor new ballots, and the same numbers of ballots in the input ballot-box and output ballot-box for the formal proof of permutation.

This technique of randomizing ciphertexts and verification keys, and adapting signatures, can be seen as an extension of signatures on randomizable ciphertexts [BFPV11] which however did not allow updates of the verification keys. This previous approach excluded anonymity because of the invariant verification keys. Our new approach can find more applications where anonymity and privacy are crucial properties.

Organization

In the next section, we recall some usual assumptions in pairing-based groups, and we introduce a new unlinkability assumption that will be one of the core assumptions of our applications. Note that it holds in the generic bilinear group model. In Section 3, we recall the notion of linearly-homomorphic signatures, with a construction of a one-time linearly-homomorphic signature scheme and its security analysis in the generic bilinear group model. Then we extend it to handle multiple sub-vector spaces. We then apply these constructions to mix-networks in Section 4, followed by a detailed security analysis in Section 5. Eventually, we conclude with some applications in Section 6.

Computational Assumptions

In this section, we will first recall some classical computational assumptions and introduce a new one, of independent interest, as it can find many use cases for privacy-preserving protocols.

Classical Assumptions

All our assumptions will be in the Diffie-Hellman vein, in the pairing setting. We will thus consider an algorithm that, on a security parameter κ, generates param = (G 1 , G 2 , G T , p, g, g, e) ← G(κ), an asymmetric pairing setting, with three groups G 1 , G 2 , G T of prime order p (with 2κ bit-length), g is a generator of G 1 and g is a generator of G 2 . In addition, the application e : G 1 × G 2 → G T is a non-degenerated bilinear map, hence e(g, g) is also a generator of G T . For the sake of clarity, in all the paper, elements of G 2 will be in Fraktur font.

Definition 1 (Discrete Logarithm (DL) Assumption).

In a group G of prime order p, it states that for any generator g, given y = g x , it is computationally hard to recover x.

Definition 2 (Symmetric External Discrete Logarithm(SEDL)Assumption). In groups G 1 and G 2 of prime order p, it states that for any generators g and g of G 1 and G 2 respectively, given f = g x and f = g x , it is computationally hard to recover x.

Definition 3 (Decisional Diffie-Hellman (DDH) Assumption). In a group G of prime order p, it states that for any generator g, the two following distributions are computationally indistinguishable:

D dh (g) = {(g, g x , h, h x ); h $ ← G, x, $ ← Z p } D 4 $ (g) = {(g, g x , h, h y ); h $ ← G, x, y, $ ← Z p }.
This is well-know, using an hybrid argument, or the random-self-reducibility, that this assumption implies the Decisional Multi Diffie-Hellman (DMDH) Assumption, which claims the indistinguishability, for any constant n ∈ N, of the distributions:

D n mdh (g) = {(g, (g x i ) i , h, (h x i ) i ); h $ ← G, (x i ) i $ ← Z n p } D 2n+2 $ (g) = {(g, (g x i ) i , h, (h y i ) i ); h $ ← G, (x i ) i , (y i ) i $ ← Z n p }.

Unlinkability Assumption

For anonymity properties, we will use some kind of credential, that can be defined as follows for a scalar u and a basis g ∈ G 1 , with g ∈ G 2 , r, t ∈ Z p :

Cred(u, g; g, r, t) = g, g t , g r , g tr+u , g, g t , g u Definition 4 (Unlinkability Assumption). In groups G 1 and G 2 of prime order p, for any g ∈ G 1 and g ∈ G 2 , with the definition below, it states that the distributions D g,g (u, u) and D g,g (u, v) are computationally indistinguishable, for any u, v ∈ Z p :

D g,g (u, v) = (Cred(u, g; g, r, t), Cred(v, g; g , r , t )); g $ ← G 2 , r, t, r , t $ ← Z p
Intuitively, as we can write the credential as, where × stands for the element-wise product,

Cred(u, g; g, r, t) = g g , g g t , g g t r × 1 g u , g u
the third component is an ElGamal ciphertext of the g u , which hides it, and makes indistinguishable another encryption g u from an encryption of g v while, given (g, g u ) and (g , g v ), one cannot guess whether u = v, under the DDH assumption in G 2 . However the pairing relation allows to check consistency:

e(g rt+u , g) = e(g r , g t ) • e(g, g u ) = e(g r , g t ) • e(g, g) u e(g r t +v , g ) = e(g r , g t ) • e(g, g v ) = e(g r , g t ) • e(g, g ) v
Because of the independent group elements g and g = g s in the two credentials, this assumption clearly holds in the generic bilinear group model, as one would either need to compare u = v or equivalently rt = r t , whereas combinations only lead to e(g, g) to the relevant powers rt, sr t , as well as u and sv, for an unknown s.

Thanks to this unlinkability assumption, and the randomizability of the above credential, proving knowledge of u can lead to anonymous credentials. However, our main application will be for our anonymous shuffles presented in Section 4.

Linearly-Homomorphic Signatures

The notion of homomorphic signatures dates back to [JMSW02], with notions in [ABC + 12], but the linearly-homomorphic signatures, that allow to sign vector sub-spaces, were introduced in [BFKW09], with several follow-up by Boneh and Freeman [BF11b,BF11a] and formal security definitions in [Fre12]. In another direction, Abe et al. [AFG + 10] proposed the notion of structurepreserving signature, where keys, messages and signatures all belong in the same group. Later Libert et al. [LPJY13] combined both notions and proposed a linearly-homomorphic signature scheme, that is furthermore structure-preserving. Our work is inspired from this construction, but in the asymmetric-pairing setting, and keys do not belong to the same group as the message and signatures. The structure-preserving property is then relaxed but fits our needs, as we will use two layers of linearly-homomorphic signature schemes, with swapped groups for the keys and the messages.

Definition and Security

In this first part, we begin with the formal definition of linearly-homomorphic signature scheme, and the security requirement, the so-called unforgeability in case of signatures. Then, we will introduce a new property for linearly-homomorphic signature scheme: the randomizable tag. It will be the key element to obtain the privacy in our mix-net. Our definition is inspired from [LPJY13], but with a possible private key associated to a tag.

Definition 5 (Linearly-Homomorphic Signature Scheme (LH-Sign)). A linearly-homomorphic signature scheme with messages in M ∈ G n , for a cyclic group (G, ×) of prime order p, some n ∈ poly(κ), and some tag set T , consists of the seven algorithms (Setup, Keygen, NewTag, VerifTag, Sign, DerivSign, Verif):

Setup(1 κ ): Given a security parameter κ, it outputs the global parameter param, which includes the tag space T ; Keygen(param, n): Given a public parameter param and an integer n, it outputs a key pair (sk, vk). We will assume that vk implicitly contains param and sk implicitly contains vk; NewTag(sk): Given a signing key sk, it outputs a tag τ and its associated secret key τ ; VerifTag(vk, τ ): Given a verification key vk and a tag τ , it outputs 1 if the tag is valid and 0 otherwise; Sign(sk, τ , M ): Given a signing key, a secret key tag τ and a vector-message M = (M i ) i ∈ G n , it outputs the signature σ under the tag τ ; DerivSign(vk, τ, (ω i , M i , σ i ) i=1 ): Given a public key vk, a tag τ and tuples of weights ω i ∈ Z p and signed messages M i in σ i , it outputs a signature σ on the vector M = i=1 M ω i i under the tag τ ; Verif(vk, τ, M , σ): Given a verification key vk, a tag τ , a vector-message M and a signature σ, it outputs 1 if VerifTag(vk, τ ) = 1 and σ is also valid relative to vk and τ , and 0 otherwise.

The tag in DerivSign allows linear combinations of signatures under the same tag but excludes any operation between signatures under different tags. The latter exclusion will be formalized by the unforgeability. However, the former property is the correctness: for any keys (sk, vk) ← Keygen(param, n), for any tags (τ, τ ) ← NewTag(sk), if σ i = Sign(sk, τ , M i ) are valid signatures for i = 1, . . . , and σ = DerivSign(vk, τ, {ω i , M i , σ i } i=1 ) from some scalars ω i , then both

VerifTag(vk, τ ) = 1 Verif(vk, τ, M , σ) = 1.
Our definition includes, but is more relaxed than, [LPJY13] as we allow a secret key associated to the tag, hence the NewTag algorithm: in such a case, the signer can only sign a message on a tag he generated himself. When there is no secret associated to the tag, actually one can consider that τ = τ is enough to generate the signature (in addition to sk). Whereas the DerivSign algorithm generates a signature under the same tag, we do not enforce to keep the same tag in the unforgeability notion below, this will allow our tag randomizability. However, we expect only signatures on linear combinations of messages already signed under a same tag, as we formalize in the following security notion.

Unforgeability. Whereas linear combinations are possible under the same tag, other combinations (non-linear or under different tags) should not be possible. This is the unforgeability notion (note that we talk about linear combinations component-wise in the exponents, as we consider a multiplicative group G).

Definition 6 (Unforgeability for LH-Sign). For a LH-Sign scheme with messages in G n , for any adversary A that, given tags and signatures on messages ( M i ) i under tags (τ i ) i both of its choice (for Chosen-Message Attacks), outputs a valid tuple (vk, τ, M , σ) with τ ∈ T , there must exist (ω i ) i∈I τ , where I τ is the set of messages already signed under some tag τ ∈ {τ i } i , such that M = i∈I τ M ω i i with overwhelming probability. Again, because of our relaxed version compared to [LPJY13], we do not exclude the adversary to be able to generate valid signatures under new tags. The linear-homomorphism for signatures, also known as signatures on vector-spaces, requires that the adversary cannot generate a valid signature on a message outside the vector spaces spanned by the already signed messages. Tags are just a way to keep together vectors that define vector spaces. The adversary can rename a vector space with another tag, this is not a security issue. On the opposite, we will exploit this feature for unlinkability with the additional randomizability property on tags (see below).

However, as in [LPJY13], we will also consider a weaker notion of linearly-homomorphic signature: a one-time linearly-homomorphic signature (OT-LH-Sign), where the set of tags is a singleton T = { }. Then we can drop the algorithms NewTag and VerifTag, as well as the τ and τ .

Our One-Time Linearly-Homomorphic Signature

Libert et al. [LPJY13] proposed a construction whose security relies on the Simultaneous Double

Pairing assumption, which is implied by the linear assumption in the symmetric case. In our use case we will need two LH-Sign schemes. While the first one can simply be one-time and thus possibly in the standard model, the second one needs randomizable tags and we do not know how to build it in the standard model. Thus, we will consider a variant of Libert et al. [LPJY13] that can only be proven in the generic bilinear group model [Sho97,BBG05,Boy08].

Setup(1 κ ): Given a security parameter κ, let (G 1 , G 2 , G T , p, g, g, e) be an asymmetric bilinear setting, where g and g are random generators of G 1 and G 2 respectively. We set param = (G 1 , G 2 , G T , p, g, g, e); Keygen(param, n): Given the public parameters param, one randomly chooses sk i = s i $ ← Z p , for i = 1, . . . , n, which defines the signing key sk = (sk i ) n i=1 , and the verification key vk = (g i ) n i=0 for g i = g s i and g 0 = g; Sign(sk, M = (M i ) i ): Given a signing key sk = (s i ) i and a vector-message

M = (M i ) i ∈ G n 1 , one sets σ = n i=1 M s i i ∈ G 1 ; DerivSign(vk, (ω i , M i , σ i ) i=1
): Given a verification key and tuples of weights ω i ∈ Z p and signed messages M i in σ i , it outputs σ = σ ω i i ; Verif(vk, M = (M i ) i , σ): Given a verification key vk, a vector-message M , and a signature σ, one checks whether the equality e(σ, g 0 ) = n i=1 e(M i , g i ) holds or not.

From this description, the derivation of signatures is trivial as the signature of the product of messages is the product of the signatures. But we also have additional properties with the keys:

Property 7 (Message Homomorphism). Given several vector-messages with their signatures, it is possible to generate the signature of any linear combination of the vector-messages, applying the operation on the signatures.

When the messages are the same, one can ask for similar property on the key:

Property 8 (Key Homomorphism). Given a vector-message with signatures under several keys, it is possible to generate the signature of this vector-message under any linear combination of the keys.

DerivSignKey( M , (ω i , vk i , σ i ) i=1 ): Given a message M and tuples of weights ω i ∈ Z p and signatures σ i of M under vk i , it outputs a signature σ of M under the verification key vk = i=1 vk ω i i .

In our case, if a message-signature is valid for a verification key vk, then it is also valid for the verification key vk = vk α , for any α, as e(σ,

g 0 ) = n i=1 e(M i , g i ) implies e(σ, g α 0 ) = n i=1 e(M i , g α i )
. However, for two different verification keys vk and vk , and signatures σ and σ of M : n i=1 e(M i ,

g α i • g i β ) = n i=1 e(M i , g i ) α • e(M i , g i ) β = e(σ, g α 0 ) • e(σ , g 0 β ), so σ = σ α σ β is a valid signature of M under vk = vk α vk β if g 0 = g 0 .
Property 9 (Weak Key Homomorphism). Given a vector-message with signatures under several keys (with a specific restriction, as a common g 0 in our case), it is possible to generate the signature of this vector-message under any linear combination of the keys.

Eventually, one needs to prove the unforgeability:

Theorem 10 (Unforgeability). Let us consider an adversary A in the generic bilinear group model. Given valid pairs ( M j , σ j ) j under a verification key vk ( M i 's possibly of adversary's choice, for Chosen-Message Attacks), when A produces a new valid pair ( M , σ) under the same verification key vk, there exist (α j ) j such that M = j M α j j .

Proof. The adversary A is given ( M j = (M j,i ) i , σ j ) j which contains group elements in G 1 , as well as the verification key vk = (g k ) k in G 2 . Note that in the generic bilinear group model, programmability of the encoding allows to simulate the signatures for chosen messages, which provides the security against Chosen-Message Attacks.

For any combination query, the simulator will consider the input elements as independent variables X j,i , V j , and S k to formally represent the discrete logarithms of M j,i and σ i in basis g, and g k in basis g 0 = g. As usual, any new element can be seen as a multivariate polynomial in these variables, of degree maximal 2 (when there is a mix between G 1 and G 2 group elements). If two elements correspond to the same polynomial, they are definitely equal, and the simulator will provide the same representation. If two elements correspond to different polynomials, the simulator will provide random independent representations. The view of the adversary remains unchanged unless the actual instantiations would make the representations equal: they would be equal with probability at most 2/p, when the variables are set to random values. After N combination queries, we have at most N 2 /2 pairs of different polynomials that might lead to a collision for a random setting with probability less than N 2 /p. Excluding such collisions, we can thus consider the polynomial representations only, denoted ∼. Then, for the output

( M = (M k ) k , σ), one knows α k,j,i , β k,j , γ i,j , δ j , such that: M k ∼ j,i α k,j,i X j,i + j β k,j V j σ ∼ j,i γ j,i X j,i + j δ j V j .
As ((M j,i ) i , σ j ) j and ((M k ) k , σ), are valid input and output pairs, we have the following relations between polynomials:

V j = i X j,i S i j,i γ j,i X j,i + j δ j V j = k   j,i α k,j,i X j,i + j β k,j V j   S k = k,j,i α k,j,i X j,i S k + k,j β k,j V j S k
Hence, the two polynomials are equal:

j,i γ j,i X j,i + j,i (δ j -α i,j,i )X j,i S i = k =i,j,i α k,j,i X j,i S k + k,j β k,j V j S k
which leads, for all i, j, to γ j,i = 0 and δ j = α i,j,i , and for k = i, α k,j,i = 0 and β k,j = 0. Hence,

M k ∼ j δ j X j,k and σ ∼ j δ j V j , which means that we have (δ j ) j such that M k = j M δ j j,k
and σ = j σ δ j j .

Notations and Constraints

We recall that linear combinations are seen in the exponents. Since we will mainly work on subvector spaces of dimension 2 (in a larger vector space), we will denote σ = Sign(sk, ( M , M )), with the verification check Verif(vk, σ, ( M , M )) = 1, a signature that allows to derive a valid σ for any linear combinations of M and M . In general, σ can be the concatenation of σ 1 = Sign(sk, M ) and σ 2 = Sign(sk, M ), but some joint random coins may be needed, and some common elements can be merged (the tag), as it will be shown in the full instantiation. We will also be interested in signing affine spaces: given a signature on M and N , one wants to limit signatures on M × N α and 1 × N β . This is possible by expanding the messages with one more component: for M = (g, M ) and N = (1, N ), linear combinations are of the form (g α , M α N β ). By imposing the first component to be g, one limits to α = 1, and thus to

(g, M N β ) = M × N β
, while by imposing the first component to be 1, one limits to α = 0, and

thus to (1, N β ) = N β .

FSH Linearly-Homomorphic Signature Scheme

In [LPJY13], they proposed a full-fledged LH-Sign by adding a public tag during the signature. In our mix-net construction, tags will be related to the identities of the users, and so some kind of randomizability will be required for anonymity, which is not possible with their scheme. Instead, we will consider the scheme proposed in [FHS19], which is a full-fledged LH-Sign version of our previous scheme. We can describe it as follows, using our notations: p,g,g,e) be an asymmetric bilinear setting, where g and g are random generators of G 1 and G 2 respectively. The set of tags is

Setup(1 κ ): Given a security parameter κ, let (G 1 , G 2 , G T ,
T = G 1 × G 2 . We then define param = (G 1 , G 2 , G T , p, g, g, e;
T ); Keygen(param, n): Given the public parameters param, one randomly chooses sk i = s i $ ← Z p , for i = 1, . . . , n, which defines the signing key sk = (sk i ) i , and the verification key vk = (g i ) n i=0 for g i = g s i and g 0 = g; NewTag(sk):

It chooses a random scalar R $ ← Z p and sets τ = (τ 1 = g 1/R , τ 2 = g 1/R
0 ) and τ = R; VerifTag(vk, τ ): Given a verification key vk = (g i ) n i=0 and a tag τ = (τ 1 , τ 2 ), it checks whether e(τ 1 , g 0 ) = e(g, τ 2 ) holds or not; Sign(sk, τ , M = (M i ) i ): Given a signing key sk = (s i ) i and a vector-message

M = (M i ) i ∈ G n
1 , together with some secret tag τ , one sets σ = ( i M s i i ) τ ;

DerivSign(vk, τ, (ω i , M i , σ i ) i=1 ): Given a verification key vk, a tag τ and tuples of weights

ω i ∈ Z p and signed messages M i in σ i , it outputs σ = σ ω i i ; Verif(vk, τ, M = (M i ) i , σ): Given a verification key vk = (g i ) i , a vector-message M = (M i ) i , and
a signature σ under the tag τ = (τ 1 , τ 2 ), one checks if the equalities e(σ, τ 2 ) = n i=1 e(M i , g i ) and e(τ 1 , g 0 ) = e(g, τ 2 ) hold or not.

When the secret keys for tags are all privately and randomly chosen, independently for each signature, unforgeability has been proven in [FHS19], under Chosen-Message Attacks, in the generic bilinear group model. The intuition is the following: first, under the Knowledge of Exponent Assumption [Dam92, HT98, Gro10], from a new pair (τ 1 , τ 2 ), on the input of either (g, g) or any other honestly generated pair (g, g 0 ), one can extract the common exponent 1/R in the two components. Then, one can see σ as the signature with the secret key (Rs i ) i , with the generator g 1/R 0 , instead of g 0 in the previous construction. However, if one knows two signatures σ and σ on M and M respectively, under the same tag τ = (τ 1 , τ 2 ) with private key τ , and the same key vk, then σ α σ β is a valid signature of M α M β , still under the same tag τ and the same key vk: this is thus a LH-Sign, where one can control the families of messages that can be combined. In addition, one can define a tag randomizable property:

Property 11 (Tag Randomizability). Given a valid tuple (vk, τ, M , σ), one can derive a new valid tuple (vk, τ , M , σ ), for a tag τ unlinkable to τ .

Our LH-Sign has the tag randomizability property, with the algorithm RandTag defined by: RandTag(vk, τ, M , σ): Given a verification key vk, a tag τ = (τ 1 , τ 2 ) and a signature σ on a vector-message

M = (M i ) i ∈ G n 1 , it chooses µ ∈ Z * p and outputs τ = (τ 1/µ 1 , τ 1/µ
2 ) and adapts σ = σ µ . Indeed, from a signature σ on M under the tag τ = (τ 1 , τ 2 ) for the key vk, σ = σ µ is a new signature on M for the same key vk under the tag τ = (τ

1/µ 1 , τ 1/µ
2 ), perfectly unlinkable to τ , as this is a new random Diffie-Hellman tuple in basis (g, g 0 ) with τ = µτ , for g 0 in vk.

As already explained above, we will essentially work on sub-vector spaces of dimension 2: we will thus denote σ = (σ 1 , σ 2 ) = Sign(sk, τ , ( M , M )), under the tag τ = (τ 1 , τ 2 ), where σ 1 = Sign(sk, τ , M ) and σ 2 = Sign(sk, τ , M ), for a common private key R = τ which led to τ = (τ 1 , τ 2 ).

Note that in the following, the use of this LH-Sign signature scheme will swap G 1 and G 2 , as the messages to be signed will be the verification keys of the previous OT-LH-Sign signature scheme, and thus in G 2 . Then the verification keys of this LH-Sign scheme will be in G 1 .

Mix-Networks

A mix-net is a network of mix-servers [Cha81] that allows to shuffle ciphertexts so that all the input ciphertexts are in the output set, but cannot be linked together. Whereas it is easy for a server to apply a random permutation on ciphertexts and randomize them, it is not that easy to provide a proof of correctness that is publicly verifiable, and compact. In this section we present our mix-net where the proof of correctness will be implicit thanks to the properties of the (linearly-homomorphic) signatures and two proofs of Diffie-Hellman tuples.

In a first step, we provide a high-level description of our construction to give the intuitions of our new method. However, this high-level presentation suffers several issues, which are then presented in the second step, while the third step details the solutions, with the full scheme. At this point, the global proof of mixing, after several mix-servers, is linear (and verification thus has a linear cost) in the number of mix-servers. In the fourth and last step, we explain how to obtain a constant-time overhead for the proof to publish, and thus for the verification.

General Description

We first provide a high-level description of our mix-net in Figure 1. As said above, the goal of this presentation is just for the intuition: there are still many problems, that will be highlighted and addressed in the next sections. We need two signature schemes:

any OT-LH-Sign scheme (Setup,Keygen,Sign,DerivSign,Verif), with additional DerivSignKey, that will be used to sign ElGamal ciphertexts in G 1 : the ciphertexts C i and the signatures σ i belong to G 1 and are verified with the user' verification keys vk i = (g k ) k in G 2 ; and any LH-Sign with randomizable tag scheme (Setup * , Keygen * , NewTag * , RandTag * , VerifTag * , Sign * , DerivSign * , Verif * ) that will be used to sign users' verification keys vk i in G 2 : the signatures Σ i also belong to G 2 and are verified with Certification Authority's verification key

VK = (g k ) k in G 1 .
Each user U i generates a pair (sk i , vk i ) ← Keygen() to sign vectors in G 1 . U i first encrypts his message M i under an ElGamal encryption scheme, with encryption key EK and signs it to obtain the signed-encrypted ballot (C i , σ i,1 ) under vk i . Obviously, some guarantees are needed.

In order to be sure that a ballot is legitimate, all the verification keys must be certified by the system (certification authority CA) that signs vk i under SK, where (SK, VK) ← Keygen * (), into Σ i . Then, anyone can verify the certified keys (vk i , Σ i ) i are valid under the system verification key VK. Since we want to avoid combinations between verification keys, we use LH-Sign with randomizable tags to sign the verification keys with a tag τ i per user U i .

Because of encryption, M i is protected, but this is not enough as it will be decrypted in the end. One also needs to guarantee unlinkability between the input and output ballots to guarantee anonymity of users. As the ballot boxes contain the ciphertexts, as well as the verification keys, the ballots must be transformed in an unlinkable way, then they can be output in a permuted way.

To have C i unlinkable to C i , C i must be a randomization of C i . With an ElGamal encryption, it is possible to randomize a ciphertext by multiplying by an encryption of 1. Thus, anyone can compute an encryption C 0 of 1, and as we use an OT-LH-Sign scheme, from a signature σ i,0 of C 0 CA = Certificate Authority, Ui = Useri, Sj = Mix-Serverj Keys CA's keys:

(SK, VK) ← Keygen * () Authority LH-Sign signing key (EK, DK) ← EKeygen() Authority homomorphic encryption key Ui's keys:

(ski, vki) ← Keygen() User OT-LH-Sign signing key CA signs vki:

(τi, τi) ← NewTag * (SK) Σi ← Sign * (SK, τi, vki) Ciphertext for randomization: C0 ← Encrypt(EK, 1) Initial ballots (for i = 1, . . . , n) Ui generates: Ci ← Encrypt(EK, Mi) User's ballot encryption σi,0 ← Sign(ski, C0)
User's signature on randomization σi,1 ← Sign(ski, Ci)

User's ballot signature BBox (0) = (Ci, σi,0, σi,1, vki, Σi, τi)i Mix (j-th mix-server, for i = 1, . . . , n) From BBox (j-1) = (Ci, σi,0, σi,1, vki, Σi, τi)i, Sj makes, for all i: Randomization of the ballot: under the user's key, one can adapt σ i,1 by using the message homomorphism (Property 7) with DerivSign to obtain σ * i,1 . In the same way, vk i and τ i must be randomizations of respectively vk i and τ i . If vk i = vk α i , its signature must be derived from Σ i with DerivSign * and τ i is obtained with the randomizable tag (Property 11) with RandTag * . Eventually, as we change the verification key, σ i,0 and σ i,1 must be adapted, which is possible thanks to the weak key homomorphism (Property 9) with DerivSignKey.

C i = Ci • C0 γ j,i σ * i,1 = DerivSign(vki, {(1, C0, σi,0), (γj,i, Ci, σi,1)}) Randomization of the keys: vk i = (vki) α j Σ * i = DerivSign * (VK, τi, (αj, vki, Σi)) (VK, τ i , vki, Σ i ) = RandTag * (VK, τi, vki, Σ * i ) Adaptation of the signatures: σ i,0 = DerivSignKey(C0, (αj, vki, σi,0)) σ i,1 = DerivSignKey(C 1 , (αj, vki, σ * i,1 )) BBox (j) = (C Π(i) , σ Π(i),0 , σ Π(i),1 , vk Π(i) , Σ Π(i) , τ Π(i) )i
Then one generates a random permutation Π to output a new ballot-box with permuted randomized ballots (vk

Π(i) , Σ Π(i) , C Π(i) , σ Π(i),0 , σ Π(i),1 ) i .

Difficulties

The above high-level scheme gives intuitions of our main approach. However, to get the required security, we still face a few issues that will be explained below and which motivate the full scheme described in the next section.

Expanded Vectors. From the signatures σ i,0 and σ i,1 with an OT-LH-Sign scheme, anyone can compute σ = DerivSign(vk i , {(α, C 0 , σ i,0 ), (β, C i , σ i,1 )}) for any α, β. As explained in Section 3.3, we can impose β = 1 and the right format of C i .

Non-Trivial Transformation. The weak key homomorphism allows to randomize vk i into vk i = vk α i but, with our scheme, Verif(vk α i , C i , σ i,1 ) is valid for any α = 0 if and only if Verif(vk i , C i , σ i,1 ) is valid. This provides a link between vk i and vk i . To solve this issue, we introduce a randomizer vk 0 , as for the ciphertext. This is a special vector also signed by CA to randomize vk i in a non-trivial way:

vk i = (vk i • vk δ i 0 ) α .
We will thus also have the signature Σ i,0 of vk 0 and the signature Σ i,1 (instead of Σ i ) of vk i , both under the same tag τ i to allow combinations.

Legitimate Ballots. Whereas all the ballots must be signed, nothing prevents a mix-server to delete a ballot or to add a ballot signed by a legitimate user (that owns a valid key vk i ). If one first checks that the number of ballots is kept unchanged, it is still possible that a ballot was replaced by a new legitimate ballot. Since we will consider honest and corrupted users (and so honest and corrupted ballots), four cases are possible: one replaces an honest or corrupted ballot by another honest or corrupted one. Our scheme will not provide guarantees against the replacement of a corrupted ballot by another corrupted ballot. Nonetheless, by adding a zeroknowledge proof of Diffie-Hellman tuple between the products of the verification keys before and after the mix, we can avoid all the other cases involving honest users.

Multiple Servers. After the last round, one gets a proof that the output ballot-box contains a permutation of randomized ciphertexts from the input ballot-box. However, the last mixserver could start from the initial ballot-box instead of the previous one, and then know the permutation. This would break anonymity, as soon as the last mix-server is dishonest. We will ask the mix-servers to sign their contributions to prove the multiple and independent permutations: each mix-server j generates the Diffie-Hellman proofs from BBox (j-1) to BBox (j) , and signs them. We will then detail this solution in the next section, which will provide a proof linear in the number of ballots and in the number of mix-servers (because of the multiple signature). Thereafter, with specific multi-signature, one can become independent of the number of mix-servers.

Our Scheme

With all the previous remarks and explanations, we can now provide the full description of our scheme which is given in Figure 2. σi, vki, Σi, τi).

CA = Certificate Authority, Ui = Useri, Sj = Mix-Serverj MixSetup(1 κ ): Let param = (G1, G2, GT , p, g, g, e) ← Setup(1 κ ) and param = {param, T = G2 × G1}; Let NIZK DH -param ← NIZK DH -Setup(1 κ ) and Sparam ← SSetup(1 κ ); Let (DK = d, EK = h = g d ) ← EKeygen(1 κ ) and C0 = (1, , g, h) for $ ← G1; It outputs Mix-param = (param , NIZK DH -param, Sparam, EK, ). MixKeygen(Mix-param): CA: SK= (S1, S2, S3, S4, S5) $ ← Z 5 p , VK = (g, g S 1 , g S 2 , g S 3 , g S 4 , g S 5 ) and for each user Ui, τi = Ri $ ← Zp, τi = (τi,1 = g 1/R i , τi,2 = g 1/R i ) vk0 = (1, 1, g0 = g, 1, 1) Sj: { (SKj, VKj) ← SKeygen() Ui: ski= (ui, vi, xi, yi) $ ← Z 4 p , vki = (g0 = g, fi = g u i 0 , li = g v i 0 , gi = g x i 0 , hi = g y i 0 ) Σi= Σi,0 = g S 3 τi , Σi,1 = (g S 1 0 f S 2 i l S 3 i g S 4 i h S 5 i ) τi MixInit(ski, Mi, vki, Σi, τi): Ui chooses ri $ ← Zp and i $ ← G1 and computes Ci = (ai = g r i , bi = h r i Mi) Ci = (g, i, ai, bi) σi = (σi,0 = v i g x i h y i , σi,1 = g u i v i i a x i i b y i i ) It outputs Bi = (Ci, i,
BBox (0) = (Bi) N i=1
Mix(SKj, BBox (j-1) , (proof (k) , sig (k) ) j-1 k=1 , Πj): From BBox (j-1) = (Ci, i, σi, vki, Σi, τi)i, (proof (k) , sig (k) ) j-1 k=1 , Sj chooses α $ ← Zp and for each ballot i, γi, δi, µi $ ← Zp and computes

a i = ai • g γ i b i = bi • h γ i i = i • γ i σ i,1 = σi,1 • σ γ i i,0 • i δ i σ i,0 = σi,0 • δ i g 0 = g α 0 f i = f α i l i = (li • g δ i 0 ) α g i = g α i h i = h α i Σ i,1 = (Σi,1 • Σi,0 δ i ) αµ i Σ i,0 = Σ αµ i i,0 τ i,1 = τ 1/µ i i,1 τ i,2 = τ 1/µ i i,2 proof (j) = NIZK DH -Proof((g0, g 0 , fi, f i ) and (g, h, a i / ai, b i / bi)) sig (j) = SSign(SKj, proof (j) ) Sj outputs BBox (j) = (C Π j (i) , Π j (i) , σ Π j (i) , vk Π j (i) , Σ Π j (i) , τ Π j (i) )i,(proof (k) , sig (k) ) j k=1

Figure 2. Detailed Shuffling of ElGamal Ciphertexts

Keys. As we will sign expanded ciphertexts of dimension 4 (see below), each user needs a secret-verification key pair (sk i , vk i ) ← Keygen(param, 4) in Z 4 p × G 5 2 . With our OT-LH-Sign, the first element of vk i is common for all the users and initialized to g 0 = g. Then, one also needs a signature Σ i = (Σ i,0 , Σ i,1 ) with our LH-Sign from the certification authority of the pair (vk 0 , vk i ) where vk 0 = (1, 1, g 0 , 1, 1) is used to make the non-trivial transformation on vk i during the mixes. This signature is signed by the authority possessing (SK, VK) ← Keygen * (param , 5) in Z 5 p × G 6 1 with a specific tag τ i per user. Eventually, each mix-server has a pair of (standard) signature scheme (SK j , VK j ) ← SKeygen() just to sign with SSign its mixing contribution. The keys VK and (VK j ) j , as well as EK = h = g d ∈ G 1 and the random $ ← G 1 , are assumed to be known to everybody.

As we are using ciphertexts with ElGamal, the ciphertext for randomization is C 0 = (g, h), the trivial encryption of 1 = g 0 , with random coin equal to 1.

Initial ballots. Each user encrypts his message M

i under EK to obtain C i = (a i , b i ).
With the remarks we already made, one needs to expand , g, h). The addition of the first element is due to the affine space we want in the signature σ i (see Section 3.3) and the second element is because we randomize the third position of vk i with vk 0 = (1, 1, g 0 , 1, 1) and because the first position of vk i is used for the verification but not to sign (the last four elements of vk i are used to sign). Finally, σ i = (σ i,0 , σ i,1 ) is simply the OT-LH-Sign of (C 0 , C i ) under the signing key sk i .

C i into C i = (g, i , a i , b i ) and C 0 into C 0 = (1,
Mix. To make a mix, the j-th mix-server computes the randomized verification keys

vk i = (vk i • vk δ i 0 ) α , the randomized ciphertexts C i = C i • C γ i
0 and the randomized tags

τ i = τ 1/µ i i
, and

MixVerif(BBox (0) , BBox (N ) , (proof (k) , sig (k) ) N k=1 ) : After N mixes, the input of the verifier is:

BBox (0) = (Ci, σi,1, vki, Σi,1, τi,1) n i=1 BBox (N ) = (C i , σ i,1 , vk i , Σ i,1 , τ i,1 ) n i=1 , (proof (k) , sig (k) ) N k=1 It outputs 1 if: n = n , the (vki)i are all distinct ∀k, NIZK DH -Verif(proof (k)) ) = 1 SVerif(VK k , proof (k)) , sig (k) ) = 1 and ∀i, Verif(vki, Ci, σi,1) = 1 = Verif * (VK, τi, vki, Σi,1) Verif(vk i , C i , σ i,1 ) = 1 = Verif * (VK, τ i , vk i , Σ i,1 )
Figure 3. Detailed Verification of Shuffling updates the signatures σ i and Σ i , thanks to the properties of the signatures. The random scalar α is common to all the ballots, but γ i , δ i , µ i are independent random scalars for each ballot.

Then, the mix-server chooses a permutation Π and sets the j-th ballot-box BBox (j) with all the randomized and permuted ballots (C

Π(i) , Π(i) , σ Π(i) , vk Π(i) , Σ Π(i) , τ Π(i) ) i .
As already explained, the mix-server also needs to make a proof proof (j) from BBox (j-1) to BBox (j) , to guarantee the proper relations between the products of the verification keys and the products of the messages, and signs it in sig (j) . Finally, the output of the mix contains BBox (j) and (proof (k) , sig (k) ) j k=1 the set of proofs and mix-server signatures of the previous mixes until the j-th mix.

Proofs. Let us denote

F = f i = g u i 0
and F = f i = g 0 u i the product of the second element of the user's verification key on all the input ballots and output ballots. If the input and output ballot-boxes contain the same ballots (with the same secret u i ), then F = F α , with g 0 = g α 0 . Hence one adds a proof of Diffie-Hellman tuple for (g 0 , g 0 , F, F ). Together with the verification that there is the same number of ballots in the input and output of the mix, we will show that the same (honest) users are represented in the two ballot-boxes. Since we cannot allow multiple ballots from the same user, we have the guarantee that the same messages from all the honest users are represented in the two ballot-boxes.

The additional proof of Diffie-Hellman tuple for (g, h, a i / a i , b i / b i ) will limit the exchange of ballots for corrupted users, as the products of the plaintexts must remain the same:

M i = M i . Since we already know these products will be the same for honest users, this products must be the same from corrupted users. This will limit the impact of the attack of Cortier- Smyth [CS13].

With these two Diffie-Hellman proofs, the output ballots are a permutation of the input ones. We could use any non-interactive zero-knowledge proofs of Diffie-Hellman tuples (NIZK DH -Setup, NIZK DH -Proof, NIZK DH -Verif) and any signature (SSetup, SSign, SVerif) to sign the proofs but the next section will provide interesting choices, from the length point of view.

Verification. The complete verification process, after N mix-servers, is presented in Figure 3. After all the mixes are done, it just requires the input ballot-box BBox (0) , the output ballot-box BBox (N ) , and the signed proofs (proof (k) , sig (k) ), for k = 1, . . . , N without the elements that were useful for randomization only. The verifier checks the number of input ballots is the same as the number of output ballots, the verification keys (the f i 's) in input ballots are all distinct, the signatures σ i,1 , σ i,1 , Σ i,1 and Σ i,1 are valid on individual input and output tuples (equations recalled in the Appendix B.1) and all the proofs proof (k) with the signatures sig (k) are valid with NIZK DH -Verif and SVerif respectively. For that, we suppose that the statement is included in each zero-knowledge proof. Thus, even if the intermediate ballot-boxes are not given to the verifier, it is still possible to perform the verification.

Constant-Size Proof

From Figure 3, one can note that our mix-net provides a quite compact proof, as it just requires BBox (0) and BBox (N ) , and the signed proofs (proof (k) , sig (k) ), for k = 1, . . . , N . The size is thus linear in n and N . This is the same for the verification complexity.

Whereas the linear complexity in n cannot be avoided, as the ballot-box must be transferred, the part linear in N could be avoided. Indeed, each proof proof (j) ensures the relations from the j -1-th ballot-box to the j-th ballot-box. The global chain of proofs ensures the relations from the initial ballot-box to the last ballot-box. From the soundness point on view, a compact global proof would be enough. But for privacy, one wants to be sure that multiple mix-servers contributed, to get unlinkability as soon as one server is honest.

To avoid the dependence in N , one can use Groth-Sahai proofs [GS08] (see the Appendix A.1 for details) to combine together the proofs into a unique one as already used in Chase et al. [CKLM12]. However, to be sure that all the mix-servers contributed: each mix-server does as above, but also receives a partial proof proof (j-1) from the initial ballot-box to the j -1-th ballot-box and, thanks to the homomorphic properties of the Groth-Sahai proof, updates it into proof (j) , to prove the relation from the initial ballot-box and the j-th ballot-box, as shown in the Appendix A.1 for the Diffie-Hellman proof between the products of the keys (the proof is similar for the product of the ciphertexts but with G 1 and G 2 swapped). At the end of the mixing steps, one has the same elements as above, plus the global proof proof (N ) . All the mix-servers can now verify the proofs and the contributions of all the servers. Only this global proof can be kept, but signed by all the servers: using the multi-signature of Boneh-Drijvers-Neven [BDN18], that is recalled in the Appendix A.2, the size of the signature msig keeps constant, whatever the number of mix-servers. Hence, after multiple mixing steps, the size of the mixing proof (with the input and output ballot-boxes) remains constant.

Efficiency

We consider VK and (VK j ) j are long-term keys known to everybody, as well as EK and .

However, for fair comparison, we do not consider vk i as long-term keys, and consider them as part of the input of the verifier. But we insist that the f i 's in the input ballot-box must be all distinct.

Size of Verifier's Input: The verifier receives:

(C i , σ i,1 , vk i , Σ i,1 , τ i ) n i=1 (C i , σ i,1 , vk i , Σ i,1 , τ i ) n i=1 (proof (N ) , msig (N ) )
As the first element g 0 of vk i is common to all the users (as well as g 0 of vk i ), the set of all the users' verification keys is represented by 4 × n + 1 elements of G 2 . Then, all input or output ballots contains 2 × 5n elements from G 1 and 2 × (6n + 1) elements from G 2 . The global proof proof (N ) is just 4 elements of G 1 and 4 elements of G 2 and msig one element in G 2 . Hence, the full verifier's input contains: 10n + 4 elements of G 1 , 12n + 6 elements of G 2 , whatever the number of mix-servers.

Verifier's Computation. Using batch verification [CHP07, BFI + 10, HHK + 17], the verifier only needs to make 8n + 7 pairing evaluations to verify together all the signatures σ i,1 , σ i,1 , Σ i,1 , Σ i,1 , τ i , τ i , 6 pairing evaluations to verify proof (N ) and 2 pairing evaluations to verify msig.

With some specific choices of the bases for the batch verification, as presented in the Appendix B.1, one can improve to 8n + 14 pairing evaluations for the global verification. This has to be compared to the 4n + 1 pairing evaluations that have anyway to be performed to verify the signatures in the initial ballot-box.

Security Analysis

Let us now formally prove the two security properties: the soundness means the output ballotbox contains a permutation of randomizations of the input ballot-box and privacy means one cannot link an input ciphertext to an output ciphertext, as soon as one mix-server is honest.

We stress that we are in a particular case where users have private signing keys, and ballots are signed. Unfortunately these keys allow to trace the ballots: with sk i = (u i , v i , x i , y i ) and g 0 , one can recover vk i , which contradicts privacy for this ballot. They might also allow to exchange some ballots, which contradicts soundness for these ballots. As a consequence, we do not provide any guarantee to corrupted users, whose keys have been given to the adversary (or even possibly generated by the adversary), but we expect honest users to be protected:

soundness for honest users means that all the plaintexts of the honest users in the input ballot-box are in the output ballot-box; privacy for honest users means that ballots of honest users are unlinkable from the input ballot-box to the output ballot-box.

Proof of Soundness

As just explained, we first study the soundness of our protocol, but for honest users only, in the certified key setting, where all the users must prove the knowledge of their private keys before getting their verification keys vk i certified by the Certification Authority in Σ i .

Definition 12 (Soundness for Honest Users).

A mix-net M is said sound for honest users in the certified key setting, if any PPT adversary A has a negligible success probability in the following security game:

1. The challenger generates the certification keys (SK, VK) and the encryption keys (DK, EK); 2. The adversary A then decides on the corrupted users I * and generates itself their keys (vk i ) i∈I * ; proves its knowledge of the secrete keys to get the certifications Σ i on vk i , for i ∈ I * ; decides on the set I of the (honest and corrupted) users that will generate a ballot; generates the ballots (B i ) i∈I * for the corrupted users but provides the messages (M i ) i∈I\I * for the honest users; 3. The challenger generates the keys of the honest users (sk i , vk i ) i∈I\I * and their ballots (B i ) i∈I\I * . The initial ballot-box is thus defined by BBox = (B i ) i∈I ; 4. The adversary mixes BBox in a provable way into (BBox , proof).

The adversary wins if MixVerif(BBox, BBox , proof) = 1 but {Decrypt * (BBox)} = {Decrypt * (BBox )}, where Decrypt * extracts the plaintexts (using the decryption key DK), but ignores ballots of non-honest users (using the private keys of honest users) and sets of plaintexts can have repetitions.

One can note that this security game does not depend on the mixing steps, but just considers the global mixing, from the input ballot-box BBox to the output ballot-box BBox . The proof proof contains all the elements for proving the honest behavior. In our case, this is just the two Diffie-Hellman proofs.

Theorem 13 (Soundness for Honest Users of Our Mix-Net). Our mix-net protocol is sound for honest users, in the certified key setting, assuming the unforgeability against Chosen-Message Attacks of the LH-Sign and OT-LH-Sign signature schemes and the SEDL assumption.

Proof. For proving this theorem, we will assume the verification is successful (MixVerif(BBox, BBox , proof) = 1) and show that for all the honest ballots, in the input and output ballot-boxes, there is a permutation from the input ones to the outputs ones. And we do it in two steps: first, honest keys vk i in the output ballot-box are permuted randomizations of the honest keys vk i in the input ballot-box; then we prove it for the plaintexts.

Permutation of Honest Keys. We first modify the security game by using the unforgeability against Chosen-Message Attacks of the LH-Sign signature scheme: we are given VK, and ask the Tag-oracle and the Signing-oracle to obtain Σ i on all the verification keys vk i and vk 0 . The rest remains unchanged. Note that because of the proof of knowledge of the private keys sk i before getting vk i certified, one can also extract them. Actually, one just needs to extract u i for all the corrupted users. Then one knows all the legitimate u i 's (for honest and corrupted users).

Under the unforgeability of the signature scheme (Setup * , Keygen * , NewTag * , RandTag * , VerifTag * , Sign * , DerivSign * , Verif * ), for any output ballot with verification key vk j there exists a related legitimate verification key vk i such that vk j = vk α i i × vk z i 0 , for some scalars z i , and α i . Since in our construction vk i = (g 0 , f i , l i , g i , h i ) and vk 0 = (1, 1, g 0 , 1, 1), and vk j = (g 0 , f j , l j , g j , h j ) and vk 0 = (1, 1, g 0 , 1, 1) with a common g 0 for all the keys, α i is a common scalar α: vk j = (vk i × vk δ i 0 ) α and vk 0 = vk α 0 . As a consequence, all the keys in the output ballot-box are derived in a similar way from legitimate keys (signed by the Certification Authority): u j = u i remains unchanged. However this does not means they were all in the input ballot-box: the adversary could insert a ballot with a legitimate verification key vk i , which was not in the initial ballot-box.

The verification process also includes a Diffie-Hellman proof for the tuple (g 0 , g 0 , i f i , j f j ). This means that i u i are the same on the input ballots and the output ballots. As one additionally checks the numbers of input ballots and output ballots are the same, the adversary can just replace an input ballot by a new one: if N is the set of new ballots and D the set of deleted ballots, the sums must compensate:

D u i = N u i .
The second game uses the SEDL assumption and the simulation-soundness of the proof of knowledge of sk i (in the certified key setting): Let us be given a tuple (g, f = g u , g, f = g u ), as input of a SEDL challenge in G 2 and G 1 : the simulator will guess an honest user i * that will be deleted, and implicitly sets u i * = u, with f i * , which allows it to use f = g u i * in the signature of C i * on the first component g, while all the other scalars are chosen by the simulator (v i * , x i * , y i * ), as well as all the other honest user' keys, the authority signing keys, and, for all the corrupted users, the secret element u i can be extracted at the certification time (using the extractor from the zero-knowledge proof of knowledge) while the zero-knowledge simulator is used for i * , thanks to the simulation-soundness.

If some honest user is deleted in the output ballot-box, with probability greater than 1/n, this is i * : as shown above, D u i = N u i , so u i * = N u i -D\{i * } u i , which breaks the symmetric external discrete logarithm assumption.

Permutation of Honest Ballots. The last game uses the unforgeability of the OT-LH-Sign signature scheme under Chosen-Message Attacks: the simulator receives one verification key vk, that will be assigned at a random honest user i * , whereas all the other keys are honestly generated. The simulator also generates (SK, VK) and (DK, EK), as well as all signatures Σ i and the honest ballots (with a signing query for σ i * ). Then, the adversary outputs a proven mix of the ballot-box. We have just proven that there exists a bijection Π from I into J such that vk Π(i) = (vk i × vk δ i 0 ) α for some scalar δ i , for all the honest users i among the input users in I. From the signature verification on the output tuples,

C Π(i) is signed under vk Π(i) in σ Π(i),1 , for every i: e(σ Π(i),1 , g 0 ) = e(g, f α i ) • e( Π(i) , l α i g αδ i 0 ) • e(a Π(i) , g α i ) • e(b Π(i) , h α i )
, and since the same α appears in g 0 = g α 0 , then for every i, we have

e(σ Π(i) , g 0 ) = e(g, f i ) • e( Π(i) , l i g δ i 0 ) • e(a Π(i) , g i ) • e(b Π(i) , h i ) = e(g, f i ) • e( Π(i) , l i ) • e(a Π(i) , g i ) • e(b Π(i) , h i ) • e( δ i Π(i) , g 0 ) and so σ Π(i) / δ i Π(i) is a signature of C Π(i) = (g, Π(i) , a Π(i) , b Π(i)
) under vk i : under the unforgeability assumption of the signature scheme, C Π(i * ) is necessarily a linear combination of the al-ready signed vectors under vk i * , which are C i * and C 0 , with some coefficients u, v: a

Π(i * ) = a u i * g v , b Π(i * ) = b u i * h v ,
and g = g u 1 v . Hence, u = 1, which means that C Π(i * ) is a randomization of C i * . We stress that for this property to hold, each key vk i must appear at most once in the ballots, otherwise some combinations would be possible. Hence the test that all the f i 's are distinct in the input ballot-box.

We stress that this proposition only guarantees permutation of ciphertexts for honest users. There is indeed no formal guarantee for corrupted users whose signing keys are under the control of a mix-server. The latter could indeed replace the ciphertexts of some corrupted users, by some other ciphertexts under the same identity or even under the identity of another corrupted user. One can note that replacing ciphertexts (and plaintexts) even for corrupted users is not that easy because of the additional Diffie-Hellman proof on the ciphertexts, which implies M i = M i where the first product is over all the messages M i in BBox and the second product is over all the messages M i in BBox . However, this property is more for the privacy, as we will see below. As a consequence, our result that guarantees a permutation on the honest ballots is optimal. We cannot guarantee anything for the users that share their keys with the mix-servers.

Proof of Privacy: Unlinkability

After proving the soundness, we have to prove the anonymity (a.k.a. unlinkability), which can also be seen as zero-knowledge property. More precisely, as for the soundness, privacy will only be guaranteed for honest users.

Definition 14 (Privacy for Honest Users).

A mix-net M is said to provide privacy for honest users in the certified key setting, if any PPT adversary A has a negligible advantage in guessing b in the following security game:

1. The challenger generates the certification keys (SK, VK) and the encryption keys (DK, EK); 2. The adversary A then decides on the corrupted users I * and generates itself their keys (vk i ) i∈I * ; proves its knowledge of the secret keys to get the certifications Σ i on vk i , for i ∈ I * ; decides on the corrupted mix-servers J * and generates itself their keys (VK j ) j∈J * ; decides on the set J of the (honest and corrupted) mix-servers that will make mixes; decides on the set I of the (honest and corrupted) users that will generate a ballot; generates the ballots (B i ) i∈I * for the corrupted users but provides the messages (M i ) i∈I\I * for the honest users; 3. The challenger generates the keys of the honest mix-servers (SK j ,VK j ) j∈J \J * the keys of the honest users (sk i , vk i ) i∈I\I * and their ballots (B i ) i∈I\I * .

The initial ballot-box is thus defined by BBox = (B i ) i∈I . The challenger randomly chooses a bit b $ ← {0, 1} and then enters into a loop for j ∈ J with the attacker:

let I * j-1 be the set of indices of the ballots of the corrupted users in the input ballot-box BBox (j-1) ; if j ∈ J * , A builds itself the new ballot-box BBox (j) with the proof proof (j) ; if j ∈ J * , A provides two permutations Π j,0 and Π j,1 of its choice, with the restriction they must be identical on I * j-1 , then the challenger runs the mixing with Π j,b , and provides the output (BBox (j) , proof (j) );

In the end, the adversary outputs its guess b for b. The experiment outputs 1 if b = b and 0 otherwise.

Contrarily to the soundness security game, the adversary can see the outputs of all the mixing steps to make its decision, hence the index j for the mix-servers. In addition, some can be honest, some can be corrupted. We will assume at least one is honest.

Theorem 15. Our Mix-Net protocol provides privacy for honest users, in the certified key setting, if (at least) one mix-server is honest, under our unlinkability assumption (see Definition 4), and the DDH assumptions in both G 1 and G 2 .

Proof. This proof will follow a series of games (G i ) i , where we study the advantage Adv i of the adversary in guessing b. We start from the real security game and conclude with a game where all the ballots are random, independently from the permutations. Hence, the advantage will be trivially 0.

Game G 0 : This is the real game, where the challenger (our simulator) generates SK and VK for the certification authority signature, and randomly chooses d $ ← Z p to generate the encryption public key EK = h = g d . One also sets vk 0 = (1, 1, g 0 = g A , 1, 1) and

C 0 = Encrypt EK (1) = (g, h) expanded into C 0 = (1, , C 0 ) with the noise parameter $
← G 1 . Actually, A = 1 in the initial step, when the user encrypts his message M i , but since the shuffling may happens after several other shuffling iterations, we have the successive exponentiations to multiple α (in A) for vk 0 . The attacker A chooses the set of the initial indices of the corrupted users I * and the set of the initial indices of the corrupted mix-servers J * , provides their verification keys ((vk i ) i∈I * , (VK j ) j∈J * ) together with an extractable zeroknowledge proof of knowledge of sk i . From I and J , one generates the signing keys for the honest mix-servers j ∈ J \J * , and set J to the index of the last honest mix-server. For each i ∈ I, one chooses

τ i = R i $ ← Z p and sets τ i = (τ i,1 = g 1/R i , τ i,2 = g 1/R i ). For each honest user i ∈ I\I * , one randomly chooses u i , v i , x i , y i , r i , ρ i $ ← Z p to generate vk i = (g 0 = g, f i = g u i 0 , l i = g v i 0 , g i = g x i 0 , h i = g y i 0
), and eventually generates all the signatures Σ i of (vk i , vk 0 ) under SK with respect to the tag τ i (using SK and (τ i ) i ). For the corrupted users, the simulator directly receives the ballots (B i = (C i , σ i , vk i , Σ i , τ i )) i∈I * while for the honest users, it receives (M i ) i∈I\I * and computes

C i = Encrypt EK (M i ) = (a i = g r i , b i = h r i M i ), C i = (g, i = ρ i , C i )
and the signature σ i of (C i , C 0 ) under sk i . The input ballot-box is then BBox (0) = {(B i ) i∈I } including the ballots of the honest and corrupted users. Let I * 0 = I * be the set of the initial indices of the corrupted users. The simulator randomly chooses b $ ← {0, 1} and now begins the loop of the mixes: depending if the mix-server j is corrupted or not, the simulator directly receives (BBox (j) , proof (j) ) from the adversary or receives (Π j,0 , Π j,1 ). In the latter case, one first checks if Π j,0

I * j-1 = Π j,1 I * j-1
using the honest secret keys to determine I * j-1 . Then, the simulator randomly chooses global α $ ← Z p and individual γ i , δ i , µ i $ ← Z p for all the users, as an honest mixserver would do, to compute

vk i = (g 0 = g α 0 , f i = f α i , l i = (l i • g δ i 0 ) α , g i = g α i , h i = h α i ) = (vk i • vk δ i 0 ) α vk 0 = (1, 1, g 0 , 1, 1) = vk α 0 C i = (g, i = i • γ i 0 , a i = a i • g γ i 0 , b i = b i • h γ i 0 ) = C i • C 0 γ i σ i = (σ i,0 = σ i,0 • 0 δ i , σ i,1 = σ i,1 • σ γ i i,0 • i δ i ) Σ i = (Σ i,0 = Σ αµ i i,0 , Σ i,1 = (Σ i,1 • Σ δ i i,0 ) αµ i ) τ i = (τ i,1 = τ 1/µ i i,1 , τ i,2 = τ 1/µ i i,2 )
and sets BBox (j) = (B Π j,b (i) ) i . Eventually, the simulator computes the proof proof (j) for (g 0 , g 0 , f i , f i ) and (g, h, a i / a i , b i / b i ), and signs it using SK j . After the full loop on all the mix-servers, the adversary outputs its guess b :

Adv G 0 = Pr G 0 [b = b].
One important remark is that under the previous soundness result, which has exactly the same setup, the input ballot-box for the last honest mix-server necessarily contains a randomization of the initial honest ballots (the adversary against the soundness is the above adversary together with the honest simulator up to its last honest round, that does not need any secret). Only the behavior of this last honest mix-server will be modified below. Game G 1 : We first switch the Diffie-Hellman proofs for (g 0 , g 0 , f i , f i ) to the zero-knowledge setting: if the input ballot-box for the last honest mix-server is not a randomization of the initial honest ballots, that can be tested using the decryption key, one has built a distinguisher between the settings of the zero-knowledge proofs. In this new setting, one can use the zero-knowledge simulator that does not use α. Under the zero-knowledge property,

Adv G 0 < Adv G 1 + negl(). Game G 2 :
We also switch the proofs for (g, h, a i / a i , b i / b i ) to the zero-knowledge setting: as above, the distance remains negligible. In this new setting, one can use the zeroknowledge simulator that does not use i γ i . Under the zero-knowledge property, Adv G 1 < Adv G 2 + negl(). Game G 3 : In this game, we do not know anymore the decryption key, and use the indistinguishability of the encryption scheme (which relies on the Decisional Diffie-Hellman assumption): in an hybrid way, we replace the ciphertexts C i of the honest users by an encryption of 1:

C i = Encrypt EK (1). Under the DDH assumption in G 1 , Adv G 2 < Adv G 3 + negl(). Game G 4 : This corresponds to C i = (a i = g r i , b i = h r i )
. But now we can know d, but is random: under the DDH assumption, we can replace the random value i = ρ i by i = r i . Ultimately, we set

C i = (g, i = r i , a i = g r i , b i = h r i ) for r i $ ← Z p ,
for all the honest users, in the initial ballot-box. Under the DDH assumption in G 1 , Adv G 3 < Adv G 4 + negl(). Game G 5 : In this game, one can first extract the keys of the corrupted users during the certification phase. Then, all the honest mix-servers generate random signing keys sk i , random tags τ i , and random encryptions C i of 1, for all the honest users (the one who do not correspond to the extracted keys), and generate the signatures using the signing keys SK and sk i , but still behave honestly for the ballots of the corrupted users. Then, they apply the permutations Π j,b on the randomized ballots.

Lemma 16 (Random Ballots for Honest Users). Under the Unlinkability Assumption (see Definition 4) and DDH assumption in G 2 , the view is computationally indistinguishable:

Adv G 4 < Adv G 5 + negl().
In this last game, the i-th honest user is simulated with initial and output (after each honest mix-server) ciphertexts that are random encryptions of 1, and initial and output signing keys (and thus verification keys vk i and vk i ) independently random. As a consequence, permutations Π j,b are applied on random ballots, which is perfectly indistinguishable from applying Π j,1-b (as we have restricted the two permutations to be identical on ballots of corrupted users):

Adv G 5 = 0. Which leads to Adv 0 ≤ negl().
Proof of Lemma 16. In the above sequences of games, from G 0 to G 4 , we could have checked whether the honest vk i 's in the successive ballot-boxes are permutations of randomized honest initial keys, just using the secret keys of the honest users. So, we can assume in the next hybrid games, from G 0 (j) to G 8 (j), for j = N, . . . , 1 that the input ballots in BBox (j-1) contain proper permutations of randomized honest initial keys, as nothing is modified before the generation of this ballot-box. In the following series of hybrid games, for index j, the honest mix-servers up to the j -1-th round play as in G 4 and from the j + 1-th round, they play as in G 5 . Only the behavior of the j-th mix-server is modified: starting from an honest behavior. Hence, G 0 (N ) = G 4 .

Game G 0 (j): In this hybrid game, we assume that the initial ballot-box has been correctly generated (with

C i = (g, i = r i , a i = g r i , b i = h r i ) for r i $ ← Z p ,
for all the honest users), and mixing steps up to BBox (j) have been honestly generated (excepted the zero-knowledge proofs that have been simulated). The next rounds are generated at random by honest mixservers: random signing keys sk i and random ciphertexts C i = (g, i = r i , a i = g r i , b i = h r i ), with random r i , and then correct signatures, using SK and sk i . The following sequence of games will modify the randomization of BBox (j-1) into BBox (j) if the j-th mix-server is honest. Game G 1 (j): We now start modifying the randomization of the ballots by the j-th mix-server, for the corrupted users. As we assumed the signatures Σ i provided by the certification authority from a proof of knowledge of sk i , our simulator has access to sk i = (u i , v i , x i , z i ) for all the corrupted users. The mixing step consists in updating the ciphertexts, the keys and the signatures, and we show how to do it without using α such that g 0 = g α 0 but, instead, just g 0 , sk i , C 0 = (1, , g, h) and the individual random coins γ i , δ i : from B i a received ballot of a corrupted user, one can compute vk i = (g 0 , g 0 u i , g 0 v i +δ i , g 0 x i , g 0 y i ) and

C i = C i • C γ i
0 , and then the signatures σ i and Σ i using the signing keys, and choosing τ i $ ← Z p . This simulation is perfect for the corrupted users: Adv G 1 (j) = Adv G 0 (j) . Game G 2 (j): We now modify the simulation of the honest ballots. In this game, we choose random d, e $ ← Z p for h = g d and = g e . Then we have simulated

C i = (g, i = r i , a i = g r i , b i = h r i ) the ciphertext in BBox (0) and we can set C i = (g, i = r i , a i = g r i , b i = h r i )
the ciphertext in BBox (j) for known random scalars r i , r i $ ← Z p , where r i is actually r i + γ i : γ i is the accumulation of all the noises. All the signatures are still simulated using the signing keys (and τ i = R i $ ← Z p ), with g 0 = g α 0 for a random scalar α. This simulation is perfectly the same as above:

Adv G 2 (j) = Adv G 1 (j) .
Before continuing, we study the format of the initial and randomized ballots: by denoting σ i the initial signature in BBox (0) and σ i the signature to generate in BBox (j) , we have the following relations:

e(σ i,0 , g 0 ) = e(g, g i h i d l i e ) e(σ i,1 , g 0 ) = e(g, f i (g i h i d l i e ) r i )
e(σ i,0 , g 0 ) = e(g, g i h i d l i e ) e(σ i,1 , g 0 ) = e(g, f i (g i h i d l i e ) r i ) If we formally denote σ i,0 = g t i and σ i,1 = g s i , then we have

g 0 t i = g i h i d l i e and g 0 s i = f i (g i h i d l i e ) r i = f i g 0 t i r i which implies s i = u i + t i r i .
Similarly, if we formally denote σ i,0 = g t i and σ i,1 = g s i , and set α as the product of all the α's and δ i as aggregation of all the δ i 's (with α's) in the previous rounds plus this round, from

g 0 αt i = g 0 t i = g i h i d l i e = g i α h i αd (l i g δ i 0 ) αe g 0 αs i = g 0 s i = f i (g i h i d l i e ) r i = f α i (g α i h α i d (l i g δ i 0 ) αe ) r i
we also have g 0 t i = (g i h i d l e i )g δ i e 0 and g 0

s i = f i (g i h d i l e i ) r i g eδ i r i 0
which implies s i = u i + t i r i . As consequence:

σ i,1 = g u i • (g r i ) t i = g u i • a i t i and σ i,1 = g u i • (g r i ) t i = g u i • a i t i
Game G 3 (j): Let us randomly choose scalars u i , r i , r i , t i , t i and α, then, from (g, g 0 ), we can set

g 0 ← g α 0 , a i ← g r i , σ i,1 ← a t i i g u i , f i ← g u i 0 , as well as a i ← g r i , σ i,1 ← a i t i g u i , f i ← g 0 u i .
Then, one additionally chooses x i , y i $ ← Z p and sets

g i ← g x i 0 h i ← g y i 0 l i ← (g t i 0 /(g i h d i )) 1/e C i ← (g, a e i , a i , a d i ) g i ← g 0 x i h i ← g 0 y i l i ← (g 0 t i /(g i h i d )) 1/e C i ← (g, a i e , a i , a i d )
By construction:

g t i 0 = g i h d i l e i , g 0 t i = g i h i d l i e , and
σ i,1 = a t i i g u i = g t i r i × g u i σ i,1 = a i t i g u i = g t i r i × g u i 21
With σ i,0 ← g t i and σ i,0 ← g t i , σ i and σ i are valid signatures of (C i , C 0 ) and (C i , C 0 ) respectively. Then, the verification keys vk i = (g 0 , f i , l i , g i , h i ) and vk i = (g 0 , f i , l i , g i , h i ) are correctly related for the secret keys (u i , v i , x i , y i ). From l i = (g t i 0 /(g i h d i )) 1/e = g (t i -x i -dy i )/e 0 : we have v i = (t i -x i -dy i )/e. From l i = (g 0 t i /(g i h i d )) 1/e = g 0 (t i -x i -dy i )/e : we have v i = (t i -x i -dy i )/e = (t i -t i )/e + v i , which means that δ i = (t i -t i )/e. Using the signing key SK, we can complete and sign vk i (with random R i ) and vk i (with random R i , which implicitly defines µ i ). As shown above, this perfectly simulates the view of the adversary for the honest ballots in the initial ballot-box BBox (0) , with B i = (C i , σ i , vk i , Σ i , τ i ) and a randomized version in the updated ballot-box BBox (j) , with

B i = (C i , σ i , vk i , Σ i , τ i ): Adv G 3 (j) = Adv G 2 (j)
. Game G 4 (j): Let us be given Cred(u i , g; g 0 , r i , t i ) and Cred(u i , g; g 0 , r i , t i ), for random u i $ ← Z p , which provide all the required inputs from the first part of the simulation in the previous game (before choosing x i , y i ). They all follow the distribution D g,g 0 (u i , u i ). As we do not need to know α to randomize ballots for corrupted users, we can thus continue the simulation as above, in a perfectly indistinguishable way: Adv G 4 (j) = Adv G 3 (j) . Game G 5 (j): Let us be given two credentials of u i and u i , Cred(u i , g; g 0 , r i , t i ) and Cred(u i , g; g 0 , r i , t i ), for random u i , u i $ ← Z p . Inputs follow the distribution D g,g 0 (u i , u i ) and we do as above. Under the Unlinkability Assumption (see Definition 4) the view is computationally indistinguishable: Adv G 4 (j) < Adv G 5 (j) + negl(). Game G 6 (j): We receive a Multi Diffie-Hellman tuple (g 0 , g i , h i , g 0 , g i , h i ) $ ← D 6 mdh (g 0 ). So we know all the scalars, except x i , y i and α, which are implicitly defined by the input challenge. Then, by choosing t i , t i $ ← Z p , we can define l i , l i as in the previous game, and the ciphertexts and signatures are generated honestly with random scalars r i , r i

$ ← Z p : Adv G 6 (j) = Adv G 5 (j) . Game G 7 (j): We now receive (g 0 , g i , h i , g 0 , g i , h i ) $ ← D 6 $ (g 0 ).
We do the simulation as above. The view of the adversary is indistinguishable under the DDH assumption in G 2 : Adv G 6 (j) < Adv G 7 (j) + negl().

In this game, vk

i = (g 0 , f i = g 0 u i , l i = g 0 v i , g i = g 0 x i , h i = g 0 y i ), with x i , y i $ ← Z p because of the random tuple, v i = v i + (t i -t i )/e,
for random t i and t i , it is thus also random, and u i is chosen at random. Game G 8 (j): We now choose at random the signing keys sk i = (u i , v i , x i , y i ) and sk i = (u i , v i , x i , y i ) in order to sign the ciphertexts:

Adv G 8 (j) = Adv G 7 (j) .
With this last game, one can see that G 8 (1) = G 5 . Furthermore, for each round j = N, . . . , 1, we have Adv G 0 (j) ≤ Adv G 8 (j) + negl(), while G 0 (j -1) = G 8 (j):

Adv G 4 = Adv G 0 (N ) ≤ Adv G 8 (1) + negl() = Adv G 5 + negl().

Applications

We now discuss use-cases of mix-nets: electronic voting and anonymous routing. In both cases, a mix-server can, on the fly, perform individual verifications and randomization of ballots, as well as the product of the f i 's and the ciphertexts adaptively until the ballots are all sent. Eventually, at the closing time for a vote or at the end of a time lapse for routing, one just has to do and sign global proof of Diffie-Hellman tuples, and then output the ballots in a permuted order.

Electronic Voting

Our mix-net fits well the case of e-voting because after the multiple mixing steps, all the mixservers can perform a second round to sign in a compact way the constant-size proof, certifying each of their contributions. The input size as well as the computation cost of the verifier are both independent on the number of mixing steps. To our knowledge it is the first scheme with this very nice property. About security, as explained, soundness and privacy are guaranteed for the honest users only: honest users are sure that their votes are randomized in the output ballot-box, and their input-output ballots are unlinkable. This is of course the most important requirements. However, since the u i 's are used to guarantee that no ballots are deleted or inserted, this is important those values to be unknown to the mix-server.

In the Appendix C, we propose a second construction that uses Square Diffie-Hellman tuples (g r , A i = g w i r , B i = A w i i ) as tags to add in any one-time linearly homomorphic signature to obtain a linearly homomorphic signature with randomizable tags. Then, one can use A j = ( A i ) α instead of f j and ( f i ) α , in the Diffie-Hellman tuple, to guarantee the permutation of the verification keys. Only the privacy of the w i 's is required to guarantee the soundness.

The proof that M i = M i is actually never used in the previous security proofs, as it counts for privacy in e-voting only. Indeed, in our privacy security game we let the adversary choose the messages of the honest users. In a voting scheme, the adversary could not choose them and would like to learn the vote of a target voter. The first mix-server could take the vote (ciphertext) of this voter and ask several corrupted voters to duplicate this vote. The bias in the tally would reveal the vote of the target voter: the proof on the products of the plaintexts avoids this modification during the mixing. This does not exclude the attack of Cortier-Smyth [CS13] if the votes are publicly sent, as the corrupted voters could simply use the ciphertext for their own ballots.

Message Routing

Another important use case of mix-nets is in routing protocols where the mix-servers are proxy servers guaranteeing that no one can trace a request of a message. In this scenario, it is not possible to perform a second round on the mix-servers to obtain the multi-signature and the efficiency is thus linear in the number of mixing steps. It is still an open problem to avoid the second round while maintaining the independence in the number of mix-servers.

A Some Primitives

A.1 Groth-Sahai Proofs

In this section, we recall the Groth-Sahai methodology [GS08] to prove a Diffie-Hellman tuple, how the proof can be verified, but also how one can update the proof.

Let (G 1 , G 2 , G T , p, g, g, e) ← G(κ) be an asymmetric pairing setting and we want to prove Diffie-Hellman tuples in G 2 , we set a tuple

(v 1,1 , v 1,2 , v 2,1 , v 2,2 ) ∈ G 4 1 , such that (v 1,1 , v 1,2 , v 2,1 , g× v 2,2 ) is not a Diffie-Hellman tuple.
Given a Diffie-Hellman tuple (g, g , A, A ) in G 2 , knowing the witness α ∈ Z p such that A = g α and A = g α , one first commits α:

Com = (c = v α 2,1 v µ 1,1 , d = v α 2,2 g α v µ 1,2
), for a random µ $ ← Z p , and one sets Θ = g µ and Ψ = A µ , which satisfy

e(c, g) = e(v 2,1 , g ) • e(v 1,1 , Θ) e(d, g) = e(v 2,2 • g, g ) • e(v 1,2 , Θ) e(c, A) = e(v 2,1 , A ) • e(v 1,1 , Ψ ) e(d, A) = e(v 2,2 • g, A ) • e(v 1,2 , Ψ )
The proof proof = (Com, Θ, Ψ ), when it satisfies the above relations, guarantees that (g, g , A, A ) is a Diffie-Hellman tuple. This proof is furthermore zero-knowledge, under the DDH assumption in G 1 : by switching (v 1,1 , v 1,2 , v 2,1 , g × v 2,2 ) into a Diffie-Hellman tuple, one can simulate the proof, as the commitment is perfectly hiding.

To verify the proof, instead of checking the four equations independently, one can apply a batch verification [BFI + 10], and pack them in a unique one with random scalars

x 1,1 , x 1,2 , x 2,1 , x 2,2 $ ← Z p : e(c x 1,1 d x 1,2 , g x 2,1 A x 2,2 ) = e(v x 1,1 2,1 (v 2,2 • g) x 1,2 , g x 2,1 A x 2,2 ) × e(v x 1,1 1,1 v x 1,2 1,2 , Θ x 2,1 Ψ x 2,2 )
One thus just has 3 pairing evaluations.

The interesting property of Groth-Sahai proofs is that it is possible from a Diffie-Hellman proof for (g, g , A, A ) to generate the Diffie-Hellman proof for (g, g = g α , A, A = A α ) is a Diffie-Hellman tuple, just knowing the incremental witness α , whereas the new witness shoud be αα , but is unknown to the prover: from the Diffie-Hellman proof proof = (Com, Θ, Ψ ) for (g, g , A, A ) where

Com = (c = v α 2,1 v µ 1,1 , d = v α 2,2 v µ 1,2 g α ) Θ = g µ Ψ = A µ
one can compute the proof proof for (g, g = g α , A, A = A α ), with µ $ ← Z p and:

Com = (c α • v µ 1,1 , d α • v µ 1,2 ) Θ = Θ α • g µ Ψ = Ψ α • A µ
One implicitly updates α into αα and µ into α µ + µ .

A.2 Multi-Signature

We now recall the signature of Boneh-Drijvers-Neven [BDN18] that provides a constant-size signature for an aggregation of multiple messages signed by multiple users. But the verification is also constant-time when the same message is signed by all the users (multi-signature). Since this is this latter case that is of interest for us, we focus in it. Let MSparam = (G 1 , G 2 , G T , p, g, g, e) ← G(κ) be an asymmetric pairing setting and let H 0 : {0, 1} * → G 2 and H 1 : {0, 1} * → Z p be two full-domain hash functions. Since the aggregated verification key can be precomputed, verification just consists of two pairing evaluations.

B Complementary Material of our Mixnet

B.1 Verification Cost

For the reader convenience, we develop the equations to verify for all the signatures and the proofs:

σ i,0
1 = e(σ -1 i,0 , g 0 ) e(g, g i ) e(h, h i ) e( , l i ) σ i,0 1 = e(σ -1 i,0 , g 0 ) e(g, g i ) e(h, h i ) e( , l i ) Σ i,0 e(τ i,2 , Σ i,0 ) = e(g 3 , g 0 ) Σ i,0 e(τ i,2 , Σ i,0 ) = e(g 3 , g 0 ) σ i,1 e(σ i,1 , g 0 ) = e(g, f i ) e(a i , g i ) e(b i , h i ) e( i , l i ) 3n +2 σ i,1 e(σ i,1 , g 0 ) = e(g, f i ) e(a i , g i ) e(b i , h i ) e( i , l i ) +3n +1 τ i e(τ i,2 , g) = e(g, τ i,1 ) +0 τ i e(τ i,2 , g) = e(g, τ i,1 ) +0 Σ i,1 e(g 1 , g 0 ) e(τ i,2 , Σ i,1 ) = e(g 2 , f i ) e(g 3 , l i ) e(g 4 , g i ) e(g 5 , h i ) +n +4 Σ i,1 e(τ i,2 , Σ i,1 ) e(g -1 1 , g 0 ) = e(g 2 , f i ) e(g 3 , l i ) e(g 4 , g i ) e(g 5 , h i ) +n msig e(H 0 (proof (N ) ), avk) = e(g, msig) +1 proof (N ) with F = i f i ,F = i f i , A = i a i / a i and B = i b i / b i : e(c x 1,1 d x 1,2 , g x 2,1 F x 2,2 ) = e(v

x 1,1 2,1 (v 2,2 • g) x 1,2 , g x 2,1 F x 2,2 )e(v x 1,1 1,1 v x 1,2 1,2 , Θ x 2,1 Ψ x 2,2 ) +3 e(g x 2,1 A x 2,2 , c x 1,1 d x 1,2 ) = e(g x 2,1 B x 2,2 , v x 1,1 2,1 (v 2,2 • g) x 1,2 )e(θ x 2,1 ψ x 2,2 , v x 1,1 1,1 v x 1,2 1,2 ) +3 = 8n +14
One can remark that several pairings have common bases g, g 1 , g 2 , g 3 , g 4 , g 5 and g 0 = g, which can be combined together in order to decrease the number of pairings to be computed for the verification.

B.2 Correctness

We also show the correctness of our mix-net: if the input ballot box is correct and the mix-servers follow the protocol then the verifier outputs 1.

If the initial ballot-box BBox (0) = (C i , σ i,1 , vk i,1 , Σ i,1 , τ i,1 ) n i=1 is correct, then Verif(vk i , C i , σ i,1 ) = 1 and Verif * (VK, τ i , vk i , Σ i,1 ) = 1. The final ballot-box is BBox (N ) = (C i , σ i,1 , vk i,1 , Σ i,1 , τ i,1 ) n i=1 and the proof of each mix-servers are (proof (k) , σ (k) ) N k=1 . If all the mix-servers follow the protocol then n = n and ∀k, NIZK DH -Verif(proof (k) ) = 1 and SVerif(VK j , proof (k) , σ (k) ) = 1. Let α k be the witness of the proof proof (k) and α = N k=1 α k . One needs to verify if Verif(vk i , C i , σ i,1 ) = 1 and Verif * (VK, τ i , vk i , Σ i,1 ) = 1: First one can remark that Verif(vk i , C 0 , σ i,0 ) = 1 because e(σ i,0 , g 0 ) = e(σ i,0 • δ i , g 0 ) α = e(σ i,0 , g 0 ) α • e( δ i , g 0 ) α = e(1, f i ) α e( , l i ) α e(g, g i ) α e(h, h i ) α • e( δ i , g 0 ) α = e(1, f i )e(g, g i )e(h, h i ) • e( , l i ) α e( , g δ i 0 ) α = e(1, f i )e(g, g i )e(h, h i ) • e( , l α i • g δ i α 0 ) = e(1, f i )e(g, g i )e(h, h i )e( , l i ) Now, one can check Verif(vk i , C i , σ i,1 ) = 1 with the help of the previous computation: e(σ i,1 , g 0 ) = e(σ i,1 , g α 0 ) = e(σ i,1 • σ γ i i,0 • i δ i , g α 0 ) = e(σ i,1 , g 0 ) α • e(σ γ i i,0 , g α 0 ) • e( i δ i , g α 0 ) = e(g, f i ) α e( i , l i ) α e(a i , g i ) α e(b i , h i ) α • e(σ γ i i,0 , g α 0 ) • e( i δ i , g α 0 ) = e(g, f i )e( i , l α i )e(a i , g i )e(b i , h i ) • e(σ γ i i,0 , g α 0 ) • e( i δ i , g α 0 ) = e(g, f i )e(a i , g i )e(b i , h i ) • e(σ γ i i,0 , g α 0 ) • e( i , l α i )e( δ i i • γ i δ i , g α 0 ) = e(g, f i )e(a i , g i )e(b i , h i ) • e(σ γ i i,0 , g α 0 ) • e( i , l α i )e( δ i i , g α 0 )e( γ i δ i , g α 0 ) = e(g, f i )e(a i , g i )e(b i , h i ) • e(σ γ i i,0 , g α 0 ) • e( i , l α i • g αδ i 0 )e( i • γ i δ i , g α 0 ) = e(g, f i )e(a i , g i )e(b i , h i ) • e(σ γ i i,0 , g α 0 ) • e( i , l i )e( γ i δ i , g α 0 ) = e(g, f i )e( i , l i )e(a i , g i )e(b i , h i ) • e(σ γ i i,0 , g α 0 ) • e( γ i δ i , g α 0 ) = e(g, f i )e( i , l i )e(a i , g i )e(b i , h i ) • e((σ i,0 δ i ) γ i , g α 0 ) = e(g, f i )e( i , l i )e(a i , g i )e(b i , h i ) • e(σ i,0 , g α 0 ) γ i = e(g, f i )e( i , l i )e(a i , g i )e(b i , h i ) • e(1, f i ) γ i e( , l i ) γ i e(g, g i ) γ i e(h, h i ) γ i = e(g, f i )e( i , l i )e(a i , g i )e(b i , h i ) • e(1 γ i , f i )e( γ i , l i )e(g γ i , g i )e(h γ i , h i ) = e(g, f i )e( i • γ i , l i )e(a i • g γ i , g i )e(b i • h γ i , h i ) = e(g, f i )e( i , l i )e(a i , g i )e(b i , h i ) About the tags, one can see e(g, τ i,1 ) = e(g, τ 1/µ i i,1 ) = e(g, τ i,1 ) 1/µ i = e(τ i,2 , g) 1/µ i = e(τ 1/µ i i,2 , g) = e(τ i,2 , g).

For the certification, setting VK = (g i ) 6

i and τi = R i , one has τ i = R i µ i and:

e(τ i,2 , Σ i,1 ) = e(g 1/(R i µ i ) , (Σ i,1 • Σ i,0 δ i ) αµ i ) = e(g, Σ 1/R i i,1 ) α • e(g, Σ 1/R i i,0 ) δ i α = e(g 1 , g 0 ) α e(g 2 , f i ) α e(g 3 , l i ) α e(g 4 , g i ) α e(g 5 , h i ) α • e(g, Σ 1/R i i,0 ) δ i α = e(g 1 , g 0 )e(g 2 , f i )e(g 4 , g i )e(g 5 , h i ) • e(g 3 , l α i )e(g, Σ 1/R i i,0 ) δ i α = e(g 1 , g 0 )e(g 2 , f i )e(g 4 , g i )e(g 5 , h i ) • e(g 3 , l α i )e(g 3 , g δ i α 0 ) = e(g 1 , g 0 )e(g 2 , f i )e(g 4 , g i )e(g 5 , h i ) • e(g 3 , l α i g δ i α 0 ) = e(g 1 , g 0 )e(g 2 , f i )e(g 3 , l i )e(g 4 , g i )e(g 5 , h i ) can be combined with any message. Such a tag (1, 1, 1, π), which was not in T , is a universal tag. Indeed, multiplied to any Square Diffie-Hellman tuple, this is still a Square Diffie-Hellman tuple. This does not contradict the Theorems 19 and 20, as they only deal with non-trivial Square Diffie-Hellman triples. We can exploit this universal tag to optimize our construction of mix-net. Indeed, instead of having Σ i,0 the LH-Sign of vk 0 for each user, it is possible to have Σ 0 = Sign * (SK, w, vk 0 ) and still be able to randomize vk i and adapt its signature Σ i,1 keeping the tag τ i per user.

Figure 1 .

 1 Figure 1. High-Level Description (Insecure Scheme)

  MSKeygen(MSparam): It chooses sk $ ← Z p and outputs (sk, vk = g sk ); MSKeyAgg({vk 1 , . . . , vk N }):It outputs avk = N i=1 vk H 1 (vk i ,{vk 1 ,...,vk N }) i ; MSSign({vk 1 , . . . , vk N }, sk i , m): It outputs s i = H 0 (m) sk i .From all the individual signatures s i , any combiner (who can be one of the signers) computes the multi-signature msig = N j=1 sH 1 (vk i ,{vk 1 ,...,vk N }) j; MSVerif(avk, m, msig): It outputs 1 if and only if e(g, msig) = e(H 0 (m), avk).

© IACR 2020.

Acknowledgments

This work was supported in part by the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 -CryptoCloud) and the French ANR ALAMBIC Project (ANR16-CE39-0006).

B.3 Randomization

In this part, we prove that a randomized ballot is a correct randomization of a ballot. A ballot B i for a user U i can be parametrized by (sk i , M i ) the secret key of the user and his message: B i (sk i , M i ) = (C i , σ i , vk i , Σ i , τ i ). The three elements (C i , vk i , τ i ) need to be proved indistinguishable from fresh ones but (σ i , Σ i ) are two deterministic signatures depending on the three previous elements.

A fresh ciphertext C i is of the form (g, i , g r i , h r i M i ) with i random in G 1 and r i random in Z p . The outputted ciphertext is C i = C i • C γ j,i 0 = (g, i , g r i , h r i M i ) with i = i • γ j,i and r i = r i + γ j,i . Thus, C i is perfectly indistinguishable from a fresh ciphertext.

For the tag, τ i = (g 1/R i , g 1/R i ) and τ i = τ 1/µ i i thus we have τ i = (g 1/R i , g 1/R i ) with R i = R i µ i which also corresponds to a fresh tag in a perfectly indistinguishable way.

About the verification key, vk i = (g 0 , g u i 0 , g v i 0 , g x i 0 , g y i 0 ) for sk i = (u i , v i , x i , y i ), vk 0 = (1, 1, g 0 , 1, 1) and vk i = (vk i • vk δ i 0 ) α thus, vk i = (g 0 , g 0 u i , g 0 v i , g 0 x i , g 0 y i ) with g 0 = g α 0 and v i = v i + δ i which is indistinguishable from a fresh verification key under the DDH in G 2 .

C LH-Sign From OT-LH-Sign with Square Diffie-Hellman Tuples

In this appendix, we propose a generic method to convert OT-LH-Sign into LH-Sign, using square Diffie-Hellman tuples. This requires the extractability assumption, in the generic bilinear group model.

C.1 Assumptions

Definition 17 (Square Discrete Logarithm (SDL) Assumption). In a group G of prime order p, it states that for any generator g, given y = g x and z = g x 2 , it is computationally hard to recover x.

Definition 18 (Decisional Square Diffie-Hellman (DSDH) Assumption). In a group G of prime order p, it states that for any generator g, the two following distributions are computationally indistinguishable:

It is worth noticing that the DSDH Assumption implies the SDL Assumption: if one can break SDL, from g, g x , g x 2 , one can compute x and thus break DSDH.

C.2 Restricted Combinations of Vectors

When one wants to avoid any combination, and just allow to convert a signature of M into a signature of M α , while they are all of the same format, one can use expanded vectors (as in Section 3.3), by concatenating a vector that satisfies this restriction: from multiple distinct (nontrivial) Square Diffie-Hellman tuples (g i , g w i i , g

), a linear combination that is also a Square Diffie-Hellman tuple cannot use more than one input tuple. We prove it in two different cases: with random and independent bases g i , but possibly public w i 's, or with a common basis g i = g, but secret w i 's. More precisely, we can state the following theorems, which proofs can be found below.

We stress that in the first theorem, the w i 's are random and public (assumed distinct), but the bases g i 's are truly randomly and independently generated.

Theorem 19. Given n valid Square Diffie-Hellman tuples

) is a valid Square Diffie-Hellman, with at least two non-zero coefficients α i , is computationally hard under the DL assumption.

In the second scenario, the basis is common (for all i, g i = g), but the w i 's are secret, still random and thus assumed distinct.

Theorem 20. Given n valid Square Diffie-Hellman tuples (g,

) is a valid Square Diffie-Hellman, with at least two non-zero coefficients α i , is computationally hard under the SDL assumption.

For the proofs below, we need to explicitly extract the linear combinations, hence the additional assumption that holds in the generic bilinear group model: Definition 21 (Extractability Assumption). The extractability assumption states that given n vectors ( M j = (M j,i ) i ) j , for any adversary that produces a new vector M = (M i ) i such that M = j M α j j , there exists an extractor that outputs (α j ) j .

C.3 Proof of Theorem 19

Up to a guess, which is correct with probability greater than 1/n 2 , we can assume that α 1 , α 2 = 0. We are given a discrete logarithm challenge Z, in basis g. We will embed it in either g 1 or g 2 , by randomly choosing a bit b:

with either u or v unknown, and randomly choose

for some unknown w. We thus have the following relations:

i , that can be computed, we deduce that:

which can be determined by checking whether the equality below holds or not:

One can note that case (1) and case (2) are independent of the bit b.

-If the case (1) happens, but b = 0, one aborts. If b = 1 (which holds with probability 1/2 independently of the case) then we can compute

2 )) mod p which is the discrete logarithm of Z in the basis g. -Otherwise, the case (2) appears. If b = 1 one aborts. If b = 0 (which holds with probability 1/2 independently of the case), v is known and we have α

29

C.4 Proof of Theorem 20

Lemma 22. Given any fixed value α ∈ Z p and n valid Square Diffie-Hellman tuples (g, a i = g w i , b i = a w i i ), for any g ∈ G and random w i ∈ Z p , outputting (α i ) i=1,...,n such that α = n i=1 α i w i , with at least one non-zero coefficient α i , is computationally hard under the SDL assumption.

Proof. Up to a guess, which is correct with probability greater than 1/n, we can assume that α 1 = 0. We are given a square discrete logarithm challenge (g,

We then output (g, a i , b i ), i = 1, . . . , n, to the adversary which outputs (α i ) i=1,...,n and α such that α 1 z + n i=2 α i w i = α. At this stage, we solve the square discrete logarithm problem by returning z = (αn i=2 α i w i )/α 1 mod p.

We now come back to the proof of the theorem. Again, up to a guess, which is correct with probability greater than 1/n, we can assume that α 1 = 0. We are given a square discrete logarithm challenge (g,

for some unknown w. We thus have the following relations:

If we denote T = n i=2 α i w i , U = n i=2 α i , and V = n i=2 α i w 2 i , that can be computed from above scalars, we have (α 1 z + T ) 2 = (α 1 + U ) • (α 1 z 2 + V ), and thus

Using Lemma 22 on the n -1 tuples (g, a i , b i ), for i = 2, . . . , n, the probability that T = n i=2 α i w i = 0 is negligible, unless one can break the SDL Assumption. So we have T = 0, with two cases:

1. If U = 0 then, because computing square roots in Z p is easy, one can solve the above quadratic equation for z that admits solutions, and obtain two solutions for z. By testing which one satisfies g z = Z 1 , one can find out the correct z and thus solve the SDL problem. 2. If U = 0, one can compute z = (α 1 V -T 2 )/(2T α 1 ) mod p and thus solve the SDL problem.

C.5 A First Generic Conversion from OT-LH-Sign to LH-Sign

Let Σ = (Setup, Keygen, Sign, DerivSign, Verif) be a OT-LH-Sign, we complete it into Σ = (Setup , Keygen , NewTag , VerifTag , Sign , DerivSign , Verif ) as follows:

Setup Sign (sk, τ = (w, h), M ): It extends M into M with the three additional components (h, h w , h w 2 ), and signs it as σ = Sign(sk, M ); DerivSign (vk, τ, {ω i , M i , σ i } i=1 ): It simply computes σ = i σ ω i i and τ = (w, h = i h ω i ); Verif (vk, τ = (w, h), M , σ): It first extends M into M with the Square Diffie-Hellman tuple (h, h w , h w 2 ) and checks whether Verif(vk, M , σ) = 1 or not.

One can note that the DerivSign provides a signature under a new tag τ , but this is still consistent with the definition of the LH-Sign. However, randomizability of the tag is not possible.

Theorem 23. If Σ is OT-LH-Sign then Σ is LH-Sign under the DL assumption.

Proof. Since the tags are fully public, any NewTag -query is answered by a random pair (w i , g i ), and a Sign -query is answered by simply forwarding a Sign-query to the Σ security game.

Receiving the forgery (vk, τ = (w, G), M , σ), one first generates M from M and τ and checks the validity, which means, according to the unforgeability of Σ, that there exist (α i ) i such that M = M i α i . The above extractability assumption provides these coefficients (α i ) i . If we just keep the 3 last components of each extended messages and the tags, we have square Diffie-Hellman triples (g i , a i = g w i i , b i = a w i i ) i , for random g i and w i (but possibly equal when the same tag is used several times), and the triple (G = g

extracted from the forgery. By combining the identical tags together, and so by summing in β j the α i 's that correspond to the same triples (g i , a i , b i ), we have (G = g

, for random and distinct triples (g j , a j , b j ) j . From Theorem 19, under the DL assumption, at most one coefficient is non-zero: none or β J , and so at most one tag is represented: none or (g J , a J , b J ). Hence M is either (1, . . . , 1) or

C.6 A Second Generic Conversion from OT-LH-Sign to LH-Sign

Let Σ = (Setup, Keygen, Sign, DerivSign, Verif) be a OT-LH-Sign, we complete it into Σ = (Setup , Keygen , NewTag , VerifTag , Sign , DerivSign , Verif ) as follows:

Setup (1 κ ): It runs Setup(1 κ ) to obtain param and adds the tag space param = (param, G 3 ×Π).

Note that we need the group G to be extended to a bilinear setting (G, G 2 , G T , p, g, g, e) for the proofs; Keygen (param , n): It runs Keygen(param, n + 3); NewTag (sk): It chooses a random scalar w $ ← Z * p and sets τ = w and τ = (g, g w , g w 2 , π), where π is a zero-knowledge proof of valid square Diffie-Hellman tuple for (g, g w , g w 2 ); VerifTag (vk, τ ): It checks the proof π on (g, g w , g w 2 ); Sign (sk, τ = w, M ): It extends M into M with the three additional components (g, g w , g w 2 ), and signs it as σ = Sign(sk, M );

) with π the updated proof of valid square Diffie-Hellman tuple; Verif (vk, τ = (τ 1 , τ 2 , τ 3 , π), M , σ): It first checks whether VerifTag (vk, τ ) = 1 or not, if the tag is valid, it extends M into M with τ and checks whether Verif(vk, M , σ) = 1 or not.

Note that for the DerivSign to be possible, one needs an homomorphic zero-knowledge proof of valid square Diffie-Hellman tuple, as the Groth-Sahai techniques [GS08] allow in a bilinear setting: let (v 1,1 , v 1,2 , v 2,1 , v 2,2 ) ∈ G 4 2 be a Diffie-Hellman tuple, for a Square Diffie-Hellman tuple (g, A = g w , B = A w ) ∈ G 3 one can generate a commitment of w,

, and the proofs proof = (Θ = g µ , Ψ = A µ ) ∈ G 2 . The proof π thus consists of the pair (Com, proof), and is homomorphic. It is well-known to be perfectly-sound, and for the zero-knowledge property, one just has to switch from the Diffie-Hellman tuple

) because they are computationally indistinguishable under the DDH assumption in G 2 , or statistically indistinguishable in the generic group model. The latter assumption will be required for the security analysis below.

Theorem 24. If Σ is OT-LH-Sign then Σ is LH-Sign, in the generic group model.

Proof. Let us consider an adversary that asks several tags (τ i ) i and signatures (σ i ) i on messages ( M i ) i and tags of its choice, and eventually produces a forgery (τ, M , σ) with probability ε. A forgery means that the tag is valid, and so the proof π is accepted; the signature is valid; -M is not in the spans of the messages signed under the same tag.

First, as the signature Σ is based on the OT-LH-Sign Σ thanks to the concatenation of the message and (τ 1 , τ 2 , τ 3 ) in the tags, we know that necessarily M (the completion of M with the triple in the tag) is a linear combination of the extended messages involved in the signing queries, unless one has broken the unforgeability of Σ, which can just happen with negligible probability.

As a consequence, the triple (τ 1 , τ 2 , τ 3 ) in the tag of the forgery is a linear combination of the Square Diffie-Hellman triples in the signing queries, with probability ε = ε -negl():

either (τ 1 , τ 2 , τ 3 ) is not a Square Diffie-Hellman tuple; or (τ 1 , τ 2 , τ 3 ) is a Square Diffie-Hellman tuple.

In the former case, where (τ 1 , τ 2 , τ 3 ) is not a Square Diffie-Hellman tuple, then we break the perfect soundness of Groth-Sahai proofs, as all the proofs for the honest tags have been generated honestly. Hence, the latter case should happen with probability greater than ε" = ε -negl(): (τ 1 , τ 2 , τ 3 ) is both a linear combination of the input triples but still a Square Diffie-Hellman tuple, with probability greater than ε . Then, the Theorem 20 shows that (τ 1 , τ 2 , τ 3 ) is one of the input triples to a power α (or possibly (1, 1, 1)). However, to apply this theorem, we are given random Square Diffie-Hellman tuples as input and we should be able to generate the proofs of validity. To this aim, we switch the Groth-Sahai proofs in perfectly hiding mode: we replace a Non Diffie-Hellman tuple by a Diffie-Hellman tuple in the CRS, which is statistically indistinguishable to a generic adversary, as its probability to make the difference is N/p 2 , where N is the number of group operations. So after this switch, from a list of Square Diffie-Hellman tuples, we simulate the proofs, and the adversary outputs a tuple (τ 1 , τ 2 , τ 3 ) that is both a linear combination of the input triples but still a Square Diffie-Hellman tuple, with probability greater than ε -N/p 2 . As we are considering a forgery, several tags should be involved, which is excluded by the Theorem 20: ε is negligible, and so ε is negligible too.

C.7 Randomizable Tags

As in the Definition 11, we can randomize the tags together with the messages: but just in a computational way, and not in a statistical way. Indeed, from a message-signature ( M , σ) for a tag τ = (τ 1 , τ 2 , τ 3 , π), one can derive the signature for the message M = M α for the tag τ = (τ α 1 , τ α 2 , τ α 3 , π ), where π can be adapted from π and α. The triple (τ α 1 , τ α 2 , τ α 3 ) in the tag is not uniformy random, as w has not changed, but it is computationally unlinkable to (τ 1 , τ 2 , τ 3 ) under the DDH assumption. This is enough for our mix-net application.

C.8 Universal Tag

Whereas only messages signed under the same tag can be combined, a message signed under the tag τ 0 = (1, 1, 1, π), where π = (1, 1, 1) is a proof for w = 0 with µ = 0 in the commitment Com,