Aurélie Bauer
email: aurelie.bauer@ens.fr

Jean-Sébastien Coron
email: jean-sebastien.coron@uni.lu

David Naccache
email: david.naccache@ens.fr

Mehdi Tibouchi
email: mehdi.tibouchi@ens.fr

⋆⋆ Damien Vergnaud
email: damien.vergnaud@ens.fr

On the Broadcast and Validity-Checking Security of pkcs#1 v1.5 Encryption ⋆

Keywords: pkcs#1 v1.5, Encryption, Broadcast Encryption, Cryptanalysis

This paper describes new attacks on pkcs#1 v1.5, a deprecated but still widely used rsa encryption standard.

The first cryptanalysis is a broadcast attack, allowing the opponent to reveal an identical plaintext sent to different recipients. This is nontrivial because different randomizers are used for different encryptions (in other words, plaintexts coincide only partially).

The second attack predicts, using a single query to a validity checking oracle, which of two chosen plaintexts corresponds to a challenge ciphertext. The attack's success odds are very high.

The two new attacks rely on different mathematical tools and underline the need to accelerate the phase out of pkcs#1 v1.5.

Introduction

pkcs stands for Public-Key Cryptography Standards [START_REF] Kaliski | pkcs#1: rsa Encryption Standard, Version 1[END_REF]. pkcs is a large corpus of specifications covering rsa encryption, Diffie-Hellman key agreement, password-based encryption, syntax (extended-certificates, cryptographic messages, private-key information and certification requests) and selected attributes. pkcs was initially developed by rsa Laboratories, Apple, Digital, Lotus, Microsoft, mit, Northern Telecom, Novell and Sun and regularly updated since. Today, pkcs has become part of several standards and of a wide range of security products including Internet Privacy-Enhanced Mail.

Amongst the pkcs collection, pkcs#1 v1.5 describes a particular encoding method for rsa encryption called rsaEncryption. In essence, the protected data is first encrypted under a randomly chosen key κ using a symmetric block-cipher (e.g. a triple des in cbc mode) then κ is rsaencrypted (wrapped) with the recipient's public key.

In 1998, Bleichenbacher [START_REF] Bleichenbacher | Chosen ciphertext attacks against protocols based on the rsa encryption standard[END_REF] published an adaptive chosen-ciphertext attack against pkcs#1 v1.5 capable of recovering arbitrary plaintexts from about half a million ciphertexts. Although active adversary models are generally regarded as theoretical concerns, Bleichenbacher's attack makes use of an oracle that only detects conformance with respect to the padding format, a real-life assumption that resulted in a practical threat. pkcs#1 v1.5 was subsequently updated (release 2.0 [START_REF] Kaliski | pkcs#1: rsa Encryption Standard, Version 2[END_REF]) and patches were issued to users wishing to continue using the old version of the standard. As we write these lines 3 and despite its vulnerabilities, pkcs#1 v1.5 is still widely used. Millions of (patched) pkcs#1 v1.5 programs remain deployed. Provably secure algorithms such as rsa-oaep [START_REF] Fujisaki | rsa-oaep is secure under the rsa assumption[END_REF] and rsakem are recommended replacements, but not widespread yet [START_REF] Kaliski | rsa Laboratories[END_REF].

Independently, there exist several well-known chosen-plaintext attacks on rsa-based encryption schemes [START_REF] Desmedt | A chosen text attack on the rsa cryptosystem and some discrete logarithm schemes[END_REF][START_REF] Coppersmith | Finding a small root of a univariate modular equation[END_REF]. These typically enable an attacker to decrypt ciphertexts at moderate cost without factoring the public modulus. The most powerful cryptanalytic tool applicable to low exponent rsa is certainly an attack due to Coppersmith [START_REF] Coppersmith | Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities[END_REF]. As a matter of fact, one major reason for adding randomness to encrypted messages 4 is to thwart such attacks.

The last publication concerning pkcs#1 v1.5's security [START_REF] Coron | New attacks on pkcs#1 v1[END_REF] presented a somewhat atypical attack allowing the opponent to retrieve plaintexts ending by enough zero bits. This paper describes two new weaknesses in pkcs#1 v1.5:

-The possibility to predict, using a single decryption query, which of two chosen plaintexts corresponds to a challenge ciphertext. The attack's success odds are very high.

-A broadcast attack allowing to decrypt an identical message sent to several recipients.

From a mathematical perspective, the two techniques are totally different. The authors regard these as a wake-up call to accelerate the phase out of pkcs#1 v1.5.

2 pkcs#1 v1. 5 Encryption We assume that the reader is familiar with the traditional public-key encryption definitions and security model preliminaries. For the sake of completeness we refer the reader to Appendix A.

2.1

The pkcs#1 v1.5 Encoding Function pkcs#1 v1.5 describes a particular encoding method (rsaEncryption) for rsa encryption [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. Consider an rsa modulus N , and let k denote its byte-length (i.e. 2 8(k-1) < N < 2 8k ). Let m be an |m|-byte message with |m| < k -11. The pkcs#1 v1.5 padding µ(m) of m is defined as follows:

1. A randomizer r consisting in k-3-|m| ≥ 8 nonzero bytes is generated uniformly at random; 2. µ(m) = µ(m, r) is the integer converted from the octet-string:

µ(m, r) = 0002 16 ||r||00 16 ||m (1)
(the leading 00 octet guarantees that the encryption block is an integer smaller than N ).

The encryption of a message m of |m| < k -11 bytes is defined as

c = µ(m, r) e mod N
for some randomizer r of k -3 -|m| nonzero bytes.

To decrypt c ∈ Z * N , compute c d mod N , convert the result to a k-byte octet-string and parse it according to equation [START_REF] Baudron | Extended notions of security for multicast public key cryptosystems[END_REF]. If the string cannot be parsed unambiguously or if r is shorter than eight octets, the decryption algorithm D outputs ⊥; otherwise, D outputs the plaintext m.

Previous attacks on pkcs#1 v1.5

In 1998, Bleichenbacher [START_REF] Bleichenbacher | Chosen ciphertext attacks against protocols based on the rsa encryption standard[END_REF] published an attack on pkcs#1 v1.5 capable of recovering arbitrary plaintexts from a large number of ciphertexts validation queries. This attack established that pkcs#1 v1.5 is not ℓ-GOAL-ATTACK for a large 5 ℓ, GOAL ∈ {OW, IND, NM} and ATTACK ∈ {VCA, CCA} (see Appendix A.3 for definitions of these security notions).

In 2000, Coron, Naccache, Joye and Paillier [START_REF] Coron | New attacks on pkcs#1 v1[END_REF] introduced two new CPAs on pkcs#1 v1.5. The first attack can be considered as a IND-CPA when e is small (for plaintext ending by sufficiently many zeroes). The second attack applies to arbitrary e, provided that |m| is large and most message bits are zeroes. Thus pkcs#1 v1.5 is not GOAL-CPA for a small e or a large |m|, for GOAL ∈ {IND, NM}. The previous crytanalytic results are summarized in Figure 1. UBK-CPA is equivalent to Factoring but establishing the UBK-VCA and UBK-CCA security is equivalent to proving (or refuting) the equivalence of the factoring and the RSA Problem (which is a long-standing open question in cryptography). In the rest of the paper, we will study the remaining security notions and prove that pkcs#1 v1.5 is:

-OW-CPA assuming the intractability of the RSA problem ( § 3); -not OW-CCA for ℓ = 2 ( § 3); -not NM-CPA ( § 4.1); -not IND-VCA for ℓ = 1 ( § 4.2); -not OW-CPA in a multi-user setting ( § 5).

On pkcs#1 v1.5's OW-CPA-Security

In this paragraph, we prove the following result: Proposition 1. The OW-CPA security of pkcs#1 v1.5 is equivalent to the RSA Problem.

In [9, Lemma 2], Coron, Joye, Naccache and Paillier proved that for suitable parameters, the existence of an algorithm that on input y ∈ Z * N outputs the k 1 least significant bits of y d mod N is equivalent to the existence of an rsa inverter. Following their approach, we prove the following lemma: Lemma 1. Let A be a OW-CPA-adversary against pkcs#1 v1.5 with success probability ε within time τ , with uniformly distributed messages of (maximum) length k -11. There exists an algorithm B that solves the RSA Problem with success probability ε ′ within time τ ′ , where:

ε ′ ≥ η 2 • ε 2 -2 -k ε τ ′ ≤ 2 • τ + poly(k)
where η is a constant independent of k and η ≥ 5 • 10 -8 .

Proof. Let A be a OW-CPA-adversary against pkcs#1 v1.5 with success probability ε within time τ . We construct an algorithm B that on input y ∈ Z * N outputs y d with success probability ε ′ within time τ ′ : 1. B picks α ∈ Z * N uniformly at random; 2. B sets y 0 = y and y 1 = y • α e 3. Let us denote, for i ∈ {0, 1}: [START_REF] Håstad | Solving simultaneous modular equations of low degree[END_REF]. y i is a valid pkcs#1 v1.5 ciphertext if ω i = 0002||r i ||00 where r i is a 8-(nonzero)-octet string. This happens with probability η ≥ (255/256) 8 • 2 -24 . If this happens, then with probability ε, A will return m i on input y i (for i ∈ {0, 1}). 4. Therefore with probability at least (ηε) 2 , we obtain:

y d i = ω i • 2 β + m i with β = 8(k -
α(ω 0 • 2 β + m 0 ) = ω 1 2 β + m 1 mod N.
Letting c 1 = 2 -β (αm 0 -m 1 ) mod N , we get the equation in (ω 0 , ω 1 ):

ω 1 -α • ω 0 = c 1 mod N (2)
From [9, Lemma 3], there exists an algorithm that given this system will output a solution (ω 0 , ω 1 ) (should such a solution exist) with probability at least 1 -2 -k on the choice of α.

⊓ ⊔

Using the same technique, this can be extended to messages of different length, with a possibly higher constant loss in the reduction.

As a byproduct of the previous proof one immediately gets that: Proposition 2. pkcs#1 v1.5 is not 2-OW-CCA.

Proof. Thanks to rsa's homomorphic properties, an adversary can mask the challenge ciphertext c as c ′ = cr e for some random r and with two decryption oracle queries, compute the e-th root x ′ of c ′ as in the previous proof. Then x = x ′ /r is the e-th root of c from which, the adversary retrieves readily the plaintext.

⊓ ⊔ 4 pkcs#1 v1.5 Malleability and Indistinguishability

We now show that µ is neither NM-CPA-secure nor IND-VCA-secure. The general idea is the following. Let m be some message to be encrypted, and µ(m) a corresponding pkcs#1 v1.5 padded encryption block. If m has Z > 2 trailing zero bits, then µ(m) is divisible by 2 Z , and µ(m)µ(m)/2 Z mod N has a good probability of still being a valid encryption block. This is not usually the case when the Z lsbs of m are not all zero.

Let c = µ(m) e mod N be a ciphertext of some message m. If m has Z > 2 trailing zeroes, c ′ = c • (1 -2 -Z ) e mod N will often be a valid ciphertext of some other message m ′ which can be related to m: this contradicts non-malleability under chosen plaintext attack. Moreover, if one is granted one query to a validity oracle, it is possible to distinguish ciphertexts of plaintexts with trailing zeroes and ciphertexts from plaintexts whose lsbs are not all zero: this contradicts indistinguishability under validity checking attack. Note that if i queries are allowed, the distinguishing success odds can quickly approach one by iterating the test with c ′ i = c • (i -2 -Z ) e mod N for i = 1, 2, . . . We will develop this idea in further detail in the coming sections.

On pkcs#1 v1.5's NM-CPA Security

Let k be the byte-size of N , Z = 4k, and M a positive integer such that M + Z + 1 is a multiple of 8 and (M + Z + 1)/8 < k -11. We consider messages of the following form:

m = m M bits 1 2 0 • • • 0 2 Z zero bits
Let M denote the uniform distribution over messages of this form. Furthermore, we define a relation R over messages of length l = M + Z + 1 as follows: for any l-bit two messages m 1 , m 2 (not necessarily of the previous form), R(m 1 , m 2 ) holds if and only if the M msbs of m 1 and m 2 coincide. In particular, for any given message m 2 , there is exactly one

m 1 ∈ M such that R(m 1 , m 2 ).
Now, consider m ← M. We can write µ(m) • (1 -2 -Z ) as:

0002 16 r 00 16 m 1 2 0 • • • 0 2 - 0002 16 r 00 16 m 1 2 = 0002 16 r 00 16 m 0 2 some digits • • • some digits Hence, µ(m) • (1 -2 -Z ) = µ(m ′ ) for some message m ′ = m such that R(m, m ′ ).
Consider, the NM-CPA adversary A which outputs sampling algorithm M in the setup stage, and transforms a challenge ciphertext

c into c ′ = c • (1 -2 -Z ) e mod N . A's advantage is: Adv NM-CPA A = Pr[R(m, m ′ )] -Pr[m 0 $ ← M; R(m 0 , m ′ )] = 1 -2 -M ≥ 1/2
which is non-negligible. Therefore, pkcs#1 v1.5 encryption is not NM-CPA-secure.

Noted that A's advantage is, in fact ∼ 1. For a 1024-bit modulus and a 128 bit randomizer, we have M = 383, making it exceedingly unlikely that A will ever fail.

On pkcs#1 v1.5's IND-VCA Security

We now show how to contradict ciphertext indistinguishability under validity checking attack using a single oracle query. There are two natural types of validity oracles: one which determines whether a given query is a valid ciphertext associated to a plaintext of any length, and the other which also checks message length. We can always contradict IND-VCAsecurity in the non-length-checking case (which is the one considered in Bleichenbacher's attack [START_REF] Bleichenbacher | Chosen ciphertext attacks against protocols based on the rsa encryption standard[END_REF]) with a single oracle query. Furthermore, if the byte-length of the randomizer is constant, as permitted by the pkcs#1 v1.5 standard, it is also possible to break IND-VCA-security with a single query to a length-checking oracle. Both attacks stem from the following result.

Proposition 3. Let c = µ(m) e mod N be the ciphertext associated to some byte-string message m, ω the byte-length of the randomizer and Proof. Starting with the first assertion, consider a message m such that c ′ is a valid ciphertext. This implies that µ(m) -µ(m) • 2 -4 mod N is a valid encoding string that, in particular, begins with the same 0002 16 pattern as µ(m).

c ′ = c • (1 -2 -4 ) e mod N . 1. If the least significant nibble of m is not 0 16 , then c ′ is never a valid ciphertext. 2.
If, for an integer x, we denote by x the only integer in (-N/2, N/2) such that x ≡ x mod N , it follows that:

|µ(m) • 2 -4 mod N | < 2 8k-16
Consider the set S of residue classes x mod N such that |x| < 2 8k-16 . Clearly, |S| = 2 8k-15 -1. On the other hand, let T + be the set consisting of k-byte strings of the form 000 16 u 0 16 , and T be the union of T + and -T + (where opposites are taken mod N ). We also have |T | = 2 8k-15 -1 and T maps into S under multiplication by 2 -4 mod N . Since multiplication by 2 -4 is a permutation of Z N , we infer that (y • 2 -4 mod N ) ∈ S if and only if y ∈ T .

In particular, if c ′ is a valid ciphertext, we get µ(m) ∈ T . By inspection of its top bits, we see that µ(m) cannot be in -T + , so it has to be in T + . Its least-significant nibble must thus be 0 16 as required.

Turning now to the second assertion, let m be the zero-message of some fixed byte-length. Write the encryption block µ(m) as follows:

µ(m) = 0002 16 r 2ω-1 r 2ω-2 • • • r 1 r 0 00 16 00 • • • 00 16
where r 0 , . . . , r 2ω-1 are randomizer's nibbles. Recall that the randomizer bytes r 2j r 2j+1 are chosen uniformly and independently at random in the range 01 16 , . . . , FF [START_REF] Kaliski | rsa Laboratories[END_REF] .

Assuming that r 2ω-1 is at least 4 (which happens with probability (256 -4 × 16)/255 = 64/85, and which we will henceforth assume), we can write (1 -2 -4 )µ(m) as:

0002 16 r 2ω-1 r 2ω-2 • • • r 1 r 0 00 16 00 • • • 00 16 -0000 16 2 16 r 2ω-1 • • • r 2 r 1 r 0 0 16 00 • • • 00 16 = 0002 16 r ′ 2ω-1 r ′ 2ω-2 • • • r ′ 1 r ′ 0 s 00 • • • 00 16
where r ′ j ≡ r j -r j+1 -κ j mod 16 for some carry bit κ j . Then, µ ′ = (1 -2 -4 )µ(m) is a valid encoding block if and only if the first 8 randomizer bytes, namely r ′ 2ω+1-2j r ′ 2ω-2j , j = 1, . . . , 8, are all nonzero. µ ′ is a valid encoding block for a message of the same length as m (or for short, "strongly valid") if and only if s = 0 and all the padding bytes r ′ 2j+1 r ′ 2j , j = 0, . . . , ω -1, are nonzero. We will find an explicit lower bound for the probability of these events.

Note first that a sufficient condition for r ′ 2j+1 r ′ 2j to be nonzero is that r ′ 2j+1 = 0. This nibble is zero if and only if r 2j+2 ≡ r 2j+1 -κ 2j+1 . Now r 2j+2 is picked independently of r 2j+1 , since they belong to different bytes; it is also independent of κ 2j+1 , which only depends on lower order bytes. Consequently:

Pr[r ′ 2j+1 = 0] = 15 ρ=0 Pr[r 2j+2 = ρ] • Pr[r 2j+1 -κ 2j+1 ≡ ρ mod 16] ≤ max ρ Pr[r 2j+2 = ρ] = 16
255 and this bound still holds conditionally to any assignment of the lower order nibbles r ′ 2i+1 , i < j. Therefore:

Pr[µ ′ is valid] ≥ Pr[r 2ω-1 ≥ 4 ∧ r ′ 2ω-3 = 0 ∧ r ′ 2ω-5 = 0 ∧ • • • ∧ r ′ 2ω-15 = 0] ≥ 64 85 • 1 - 16 255 7 ≥ 0.47 Furthermore: Pr[µ ′ is strongly valid] ≥ Pr[r 2ω-1 ≥ 4 ∧ r ′ 2ω-3 = 0 ∧ • • • ∧ r ′ 1 = 0 ∧ r 0 = 0] ≥ 64 85 • 1 - 16 255 ω-1 • 15 255 = 64 1445 • 239 255 ω-1
The corresponding validity assertions for c ′ follow immediately.

⊓ ⊔

Consider the IND-VCA adversary A defined as follows. In the setup stage, A outputs two equal-length messages m 0 , m 1 with m 1 not zeroterminated (e.g. 00 • • • 0001 16 ) and m 0 consisting of 00 16 bytes only. Then, upon receiving a challenge ciphertext c = µ(m b ) e mod N , A makes a single oracle query and outputs b ′ = 0 or 1 according to whether c ′ = c • (1 -2 -4 ) mod N is a valid ciphertext or not. Its advantage is then: In the non-length-checking case, we can obtain an even better advantage using c ′ = c • (1 -2 -8 ) mod N (shifting by 8 bits instead of 4). The proof works similarly provided that N satisfies N > 2 8k-7 , which is not required by the pkcs#1 v1.5 standard but is usually verified in practice. This yields an advantage of at least: We now examine the security of pkcs#1 v1.5 in a multiple users context. In such a scenario, i.e. when broadcast encryption is performed, the sender wishes to transmit the same message m to ℓ parties P 1 , . . . , P ℓ . As each party has its own key pk i = (e, N i ) (with a common public exponent e), the sender encrypts m using all the pk i 's and sends the resulting ciphertexts c 1 , . . . , c ℓ to the corresponding recipients. It has long been known that textbook rsa encryption should not be used in such a context, since an attacker can easily recover the plaintext using the Chinese Remainder Theorem as long as ℓ ≥ e. Therefore, m has to be padded before applying the rsa function, and the padding has to be different for each recipient.

Adv IND-VCA A = Pr[b ′ = 0|b = 0] -Pr[b ′ = 1|b = 0] = Pr[b ′ = 0|b = 0] -0 ≥ 0.
In 1988, Håstad [START_REF] Håstad | Solving simultaneous modular equations of low degree[END_REF] showed that using different linear paddings µ i (m) for all parties is not enough to guarantee security. Indeed, when e is small, e ciphertexts are again sufficient to efficiently recover m provided that the encoding functions µ i are known to the attacker. To achieve this result, Håstad expressed the attack in terms of finding small roots of a univariate modular polynomial, which he accomplishes using Coppersmith's techniques [START_REF] Coppersmith | Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities[END_REF].

Håstad's attack does not apply to pkcs#1 v1.5, since the padding used for a given recipient is random, and is thus unknown to an attacker. The following sections will overcome this difficulty. Our main result is as follows:

Proposition 4. Let c 1 , . . . , c ℓ be ℓ pkcs#1 v1.5 ciphertexts of the same message m, of byte length |m|. Each c i is encrypted for a receiver having pk i = (e, N i ). All N i are k-byte long. Then there exists a heuristic algorithm which, given c 1 , . . . , c ℓ , outputs m, if:

ℓ > e|m| k -e(k -|m| -3) > 0
Its complexity is polynomial in e, |m| and k but exponential in the number of ciphertexts ℓ.

We describe this algorithm in the coming sections. The core idea is to reduce the problem to finding small modular roots of a multivariate polynomial equation, which can be achieved using a standard generalization of Coppersmith's techniques. As usual, this generalization relies on an assumption concerning independence between polynomials, which makes the algorithm heuristic.

5.1

The Multivariate Polynomial of Broadcast pkcs#1 v1.5

Recall (section 2.1) that to encrypt message m for recipient P i , a pkcs#1 v1.5 sender first generates an |r i |-byte randomizer r i , and then computes the encoding function:

µ(m, r i ) = 0002 16 r i 00 16 m
Numerically, this gives:

µ(m, r i ) = m + 2 8|m|+8 r i + 2 8|m|+8|r i |+9
The ciphertext c i is then computed as c i = µ(m, r i ) e mod N i .

Consider then an adversary A who obtains c 1 , . . . , c ℓ . Since the N i are of the same size, the randomizers r i have a common byte length |r|. Therefore, the ciphertexts collected by A can be written as:

c 1 = (m + Ar 1 + B) e mod N 1 , . . . , c ℓ = (m + Ar ℓ + B) e mod N ℓ
where A = 2 8|m|+8 and B = 2 8|m|+8|r|+9 . Obviously, the N i are pairwise co-prime (otherwise, the factorization of some of the N i could easily be recovered). Thus, the Chinese Remainder Theorem ensures that the previous equations can be rewritten as a single congruence mod

N = N 1 • • • N ℓ : u 1 c 1 + • • • + u ℓ c ℓ = u 1 (m + Ar 1 + B) e + • • • + u ℓ (m + Ar ℓ + B) e mod N
where the constants u 1 , . . . , u ℓ are given by the extended Euclidean algorithm. It follows that the tuple (m, r 1 , . . . , r ℓ ) is a root of the multivariate modular polynomial:

f (x, y 1 , . . . , y ℓ ) = u 1 (x + Ay 1 + B) e + • • • + u ℓ (x + Ay ℓ + B) e -C mod N (3)
where

C = u 1 c 1 + • • • + u ℓ c ℓ .
This root is small in the sense that all of its components are bounded by quantities that are small compared to N : m is smaller than 2 8|m| and each r i is bounded by 2 8|r| . Under suitable conditions on |m| and |r| which will be detailed below, it will thus become feasible to recover this root, and hence m, in polynomial time using Coppersmith's techniques, as recalled in Appendix B.

In particular, we show in section B.3 that the lattice construction of Jochemsz and May [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking rsa variants[END_REF] yields a heuristic polynomial time algorithm for recovering the small root of f under the following condition:

ℓ|r| + |m| < t(ν) s(ν) • ℓk
where ν is a parameter which determines the attack's complexity, and s(ν), t(ν) are defined as:

s(ν) = eν i=0 i eν -i + ℓ ℓ = ℓ + eν -1 ℓ (ℓ + eν)(1 + ℓ + eν) 2 + 3ℓ + ℓ 2 and t(ν) = ν i=1 eν -ie + ℓ + 1 ℓ + 1
We also prove in the same section that t(ν)/s(ν) → 1/e as ν tends to +∞, so that the best achievable bound on |m| and |r| for which the attack applies is: ℓ|r| + |m| < ℓk e Since |r| = k -|m| -3 in pkcs#1 v1.5 we obtain the bound announced in Proposition 4. As usual when using Coppersmith's techniques, the complexity of the attack is polynomial in the dimension of the constructed lattice and in the size of the entries (see Appendix B for details on these parameters).

Given pkcs#1 v1.5's widespread use and the heuristic nature of multivariate Coppersmith-like techniques, it is important to practically assess our attack. We report practical experiment results in Appendix C. Chosen-Ciphertext Attack (CCA) A has access to a decryption oracle.

Conclusion

Whenever oracle access is used A cannot submit to the oracle the challenge ciphertext he has to attack. These definitions are classical and we refer the reader to [START_REF]Provable security for public-key schemes[END_REF] for more details.

We denote security notions positively: e.g. OW-VCA[S] is the problem of contradicting the one-wayness of scheme S under validity-checking attack. This convention permits the easy description of hierarchies between security notions using reductions (see Figure 3). When oracle access is permitted (i.e. either for VCA or CCA), we denote by ℓ-GOAL-ATTACK[S] the problem of contradicting GOAL ∈ {UBK, OW, IND, NM} in less than ℓ oracle queries under an ATTACK ∈ {VCA, CCA}.

UBK-CCA ⇐= UBK-VCA ⇐= UBK-CPA ⇓ ⇓ ⇓ OW-CCA ⇐= OW-VCA ⇐= OW-CPA ⇓ ⇓ ⇓ IND-CCA ⇐= IND-VCA ⇐= IND-CPA ⇓ ⇓ ⇓ NM-CCA ⇐= NM-VCA ⇐= NM-CPA

A.4 rsa Security

Single User rsa Security rsa encryption is UBK-CPA-secure assuming the hardness of factoring. Contradicting rsa's OW-CPA security is known as the RSA Problem and is believed to be intractable. rsa's determinism makes the validity-checking oracle useless and rsa is therefore OW-VCA-secure relative to the RSA problem as well. Unfortunately, because of this determinism, rsa cannot be semantically secure: given the encryption c of either m 0 or m 1 , the adversary simply computes c 0 = m e 0 mod N and checks whether c 0 = c. Many variants of this basic scheme have been proposed with the hope of making them semantically secure through the use of randomized padding schemes. This paper focuses on all the previously mentioned security notions for the padding pkcs#1 v1.5.

Multiple User rsa Security The previous definitions do not capture security in a multicast context. In the early 1990s, attacks against low-exponent rsa highlighted the danger of multi-user security threats left uncaptured by single-user models. In independent works, Baudron, Pointcheval and Stern [START_REF] Baudron | Extended notions of security for multicast public key cryptosystems[END_REF] and Bellare, Boldyreva and Micali [START_REF] Bellare | Public-key encryption in a multi-user setting: Security proofs and improvements[END_REF] proved that for strong security notions (namely IND or NM), schemes with reductionist security in the multi-user setting are exactly those permitting security proofs in the single-user setting. However, encryption one-wayness (OW) in a multi-user setting is not guaranteed only when the plaintexts are somehow correlated.

For rsa encryption, if a common e is used, then e encryptions of a given message under different public keys N 1 , . . . , N e lead to an easy plaintext recovery. Again, several countermeasures have been proposed (e.g. padding the message with random bits) but with an unclear security guarantees. The second part of this paper explores broadcast attacks on pkcs#1 v1.5.

B Finding Small Modular Roots of a Multivariate Polynomial

The problem of solving modular polynomial equations is believed to be difficult in the general case. Nevertheless, when we restrict the problem to finding small roots only, the problem becomes easier to solve. Indeed, in 1996, Coppersmith [START_REF] Coppersmith | Finding a small root of a univariate modular equation[END_REF] introduced a technique, based on lattice reduction, allowing to recover the root of a univariate modular polynomial provided that this root is small enough. This construction was reformulated in simpler terms by Howgrave-Graham [START_REF] Howgrave-Graham | Finding small roots of univariate modular equations revisited[END_REF] and its extensions to more variables found numerous cryptanalytic applications.

B.1 Coppersmith's Technique.

Starting from a polynomial f modulo a known composite integer N , the idea behind Coppersmith's method is to construct a set of polynomials h 1 , . . . , h n sharing the same sought root over the integers. If the number of these generated polynomials is sufficiently large (greater than the number of variables) and under the assumption that all resultant computations lead to non-zero results, then the root can easily be recovered. Note that this assumption makes the method heuristic.

A sufficient condition ensuring that the polynomials h 1 , . . . , h n share a common root in Z was formulated by Howgrave-Graham.

Lemma 2 (Howgrave-Graham [START_REF] Howgrave-Graham | Finding small roots of univariate modular equations revisited[END_REF]). Let h ∈ Z[x 1 , . . . , x n ] be an integer polynomial that consists of at most ω monomials. Suppose that 1. h(x 01 , . . . , x 0n ) ≡ 0 mod N for some

|x 01 | < X 1 ,. . . ,|x 0n | < X n 2. h(x 1 X 1 , . . . , x n X n ) < N √ ω .
Then h(x 01 , . . . , x 0n ) = 0 holds over the integers.

The problem can thus be reduced to finding polynomials h 1 , . . . , h n of small norm having the same modular root as f . This can be achieved by representing polynomials as coefficient vectors (using a suitable ordering on monomials) and using lattice reduction techniques such as lll [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] to search for small vectors in a lattice spanned by polynomials which are known to have the sought modular root.

If L is a lattice of polynomials consisting of at most ω monomials and all having the same modular root as f , then the condition 2 ω(ω-1)

4(ω+1-n) det(L) 1 (ω+1-n) < N √ ω (4)
ensures first n polynomials obtained by applying lll to the lattice L match Howgrave-Graham's bound. In the analysis, we let terms that do not depend on N contribute to an error term ε, and simply use the determinant condition det(L) ≤ N w+1-n .

B.2 Lattice Construction

A variety of methods for constructing the lattice L have been proposed in the literature. In what follows, we choose to rely on the technique introduced by Jochemsz and May in [START_REF] Jochemsz | A strategy for finding roots of multivariate polynomials with new applications in attacking rsa variants[END_REF].

Recall that we have a polynomial f with an unknown root x 0 = (x 01 , . . . , x 0n ) modulo some composite integer N whose factorization is unknown. This root is small in the sense that each of its components is bounded: |x 0i | < X i for i ∈ {1, . . . , n}. We denote by λ the leading monomial of the polynomial f and by M(f ) the set of monomials appearing in f . Of course, λ can be assumed to be monic as otherwise one simply has to multiply f by the modular inverse of its initial coefficient.

Given ε > 0, we fix an integer ν = ν(ε) and without loss of generality we assume that M(f j ) ⊆ M(f ν ) for j ∈ {1, . . . , ν -1}. If k is an integer between 0 and ν + 1, we define the set M k as M(f ν ) ∩ λ k M(f ν-k ) (in particular M 0 = M(f ν ) and M ν+1 = ∅). Next, we define the following shift polynomials:

g i 1 ...in (x 1 , . . . , x n ) = x i 1 1 • • • x in n λ k f k N ν-k
for k ∈ {0, . . . , ν} and

x i 1 1 • • • x in n ∈ M k \ M k+1 .
By definition, all polynomials g have the root (x 01 , . . . , x 0n ) modulo N ν . We can now define L as the lattice generated by the coefficient vectors of all polynomials g i 1 ...in (x 1 X 1 , . . . , x n X n ). If the monomial ordering has been chosen correctly, the matrix corresponding to that lattice is lower triangular and the determinant becomes easy to compute. Indeed, the diagonal elements are those corresponding to the monomial λ k in f k for each row. Therefore, the diagonal terms of the matrix are

X i 1 1 • • • X in n N ν-k for k ∈ {0, . . . , ν} and x i 1 1 . . . x in n ∈ M k \ M k+1
. By doing a simple computation and neglecting low order terms, one can finally reduce the condition (4) to the following new one:

n j=1 X s j j < N s N for s j = x i 1 1 •••x in n ∈M 0 i j (1 ≤ j ≤ n) s N = ν k=1 |M k | (5)
This formula expresses an asymptotic condition on the bounds X 1 , . . . , X n allowing to recover the root in polynomial time.

Remark 1. The method outlined above is what Jochemsz and May called the "basic strategy"; they also proposed an "extended strategy" in which we can use extra shifts of a certain variable and replace M k for instance by

M k = t j=1 x j 1 M(f ν ) ∩ λ k M(f ν-k
) for some well-chosen parameter t.

B.3

The Jochemsz-May Lattice in Broadcast pkcs#1 v1.5

Let us examine what the lattice L looks like in the particular setting of broadcast pkcs#1 v1.5 encryption.

Recall from section 5.1 that recovering m from c 1 , . . . , c ℓ reduces to finding the root (x 0 , y 0,1 , . . . , y 0,ℓ ) = (m, r 1 , . . . , r ℓ ) of the following modular polynomial:

f (x, y 1 , . . . , y ℓ ) = u 1 (x + Ay 1 + B) e + • • • + u ℓ (x + Ay ℓ + B) e -C mod N
We know that this root satisfies the bounds |x 0 | < X and |y 0i | < Y for all i ∈ {1, . . . , ℓ} with X = 2 8|m| and Y = 2 8|r| . We examine how the Jochemsz-May bounds described in the previous section translate into bounds on |m| and |r| allowing the message to be recovered in polynomial time.

Form of the Sets M k . The analysis' first step consists in describing the sets M k . Note first that the set of monomials M(f ) is included in

{x a y b 1 1 • • • y b ℓ ℓ | a + b 1 + • • • + b ℓ ≤ e}.
In other words, the geometrical shape of the polynomial f is included in a "pyramid" of dimension ℓ+1 of monomials with total degree less than e. We choose the deglex monomial order, according to which the leading monomial of f is x e . The sets M k can then be described as follows:

M 0 = {x a y b 1 1 • • • y b ℓ ℓ | a + b 1 + • • • + b ℓ ≤ eν} M 1 = {x a y b 1 1 • • • y b ℓ ℓ | a + b 1 + • • • + b ℓ ≤ eν with a ≥ e} . . . M ν = {x a y b 1 1 • • • y b ℓ ℓ | a + b 1 + • • • + b ℓ ≤ eν with a ≥ eν}
which makes it easy to count the number of monomials in each of them.

Condition on the Bounds. Given the above description, we can evaluate the quantities s j and s N of equation ( 5) as follows. First, by symmetry, s i , s j 1 , . . . s j ℓ are all equal to:

s(ν) = eν i=0 i(eν -i + 1)(eν -i + 2) • • • (eν -i + ℓ) ℓ!
Furthermore, we have:

s N = t(ν) = ν i=1 (eν -ie + 1)(eν -ie + 2) • • • (eν -ie + ℓ + 1) (ℓ + 1)!
Condition (5) can then be rewritten as X s(ν) Y ℓs(ν) < N t(ν) , and since N is of byte size ℓk, this gives:

ℓ|r| + |m| < t(ν) s(ν) • ℓk
Asymptotic Bound. The functions s(ν) and t(ν) are polynomials in ν.

Hence, it suffices to evaluate their leading coefficients to obtain an asymptotic estimate as ν → +∞. Note further that s(ν) and t(ν) are easily expressed in terms of the antidifference operator, which takes a polynomial P (X) to the polynomial σ(P )(X) defined by σ(P )(j) = j i=1 P (i) for j ∈ N. Indeed:

s(ν) = eν i=0 (eν -i)P (i) = eν • σ(P )(eν) -σ(XP )(eν) + eν with P (X) = (X + 1) • • • (X + ℓ) ℓ! t(ν) = ν i=1 Q(i) = σ(Q)(ν) with Q(X) = (eX -e + 1) . . . (eX -e + ℓ + 1) (ℓ + 1)!
Now it is easily seen that if the leading coefficient of P is c d X d , the leading coefficient of σ(P ) is c d X d+1 /(d+1). It follows that, as ν → +∞, we have:

s(ν) ∼ eν • (eν) ℓ+1 ℓ!(ℓ + 1) - (eν) ℓ+2 ℓ!(ℓ + 2) = (eν) ℓ+2 (ℓ + 2)! and t(ν) ∼ e ℓ+1 ν ℓ+2 (ℓ + 2)!
In particular, t(ν)/s(ν) → 1/e when ν → +∞. Thus, the best asymptotic bound on |m| and |r| for which the attack is theoretically possible is:

ℓ|r| + |m| < ℓk e

C Broadcast Attack Experimental Results

Given pkcs#1 v1.5's widespread use and the heuristic nature of Coppersmith's techniques in the multivariate case, it is important to practically assess our attack. In particular, one of the main questions remains to know how many ciphertexts an attacker really needs in practice to recover m. In the particular instance {log 2 N = 1024, e = 3}, the number of required ciphertexts is, in fact, really low.

Corollary 1. If a pkcs#1 v1.5 user encrypts the same message m with 64-bit randomizers to multiple recipients using 1024-bit moduli and e = 3, then there exists a heuristic polynomial time algorithm that recovers m from ℓ = 4 ciphertexts.

Proof. This is a direct consequence of Proposition 4, given that, for 1024bit moduli and 64-bit randomizers, message size is equal to 936 bits.

These parameters, corresponding to optimal message size and encryption speed for 1024-bit moduli, are quite realistic and widely implemented. The practical implications of this result are potentially serious.

C.1 Partial Information.

Consider an attacker who does not collect all the ℓ required ciphertexts. In that specific case, even if m can not be fully recovered, the attacker can nevertheless obtain partial information on m. In particular, in a scenario where m would not be of full size and would have been previously padded with zero bits (e.g. using an aes key), the attack can still be performed.

C.2 Practical Implementations.

To check the applicability of the attack, we investigated three configurations: An attacker having access to two, three and four ciphertexts. Before implementing the attack in each scenario, we first evaluated the dimension of the corresponding lattices (for reasonably small values of the parameter ν) and then expressed the number of bits on m that should be recovered in practice. The results obtained for 1024-bit moduli and e = 3 are shown in the following As we can see, the number of bits of m that we are able to recover increases with ν, and approaches 936 bits for (ℓ, ν) = (4, 10). Unfortunately, the dimensions of the constructed lattices are often quite impractical. In many cases, matrix size turns out to exceed 1000, making lattice reduction unfeasible in practice. As a result, and because we had limited processor time at our disposal, we only ran practical experiments in the small cases, namely ℓ = 2 and ν = 2, 3.

Experiments have been performed on a hepta-processor Intel Xeon clocked at 1.86ghz. Each test was done in the same way: construction of the appropriate lattice, lll-reduction and then extraction of short vectors. Although one only theoretically requires a number of vectors equal to the number of variables, in practice we decided to take as much vectors as possible to increase the attack's success odds. Most cpu time was claimed by the lll-reduction step (approximately 3 hours for (ℓ, ν) = (2, 3)). With 1024-bit moduli and 64-bit randomizers, we managed to recover a 115-bit message (padded with zero msbs).

C.3 Toy example.

To better illustrate the attack process, we present here a toy example for 150-bit moduli and 5-bit message m. Once the polynomial f had been constructed and the lattice generated (the lattice is of dimension 84 in this case), lll-reduction was performed. Here the first 50 vectors corresponded to polynomials having the desired root over the integers. We then took all polynomials and computed a Gröbner basis of the ideal they generated. The results were the following: The Gröbner basis computation does not allow us to directly recover the message m, since the corresponding subvariety is not of dimension zero, as was usually the case in most experiments. In fact, we commonly faced problems of algebraic dependence between the resulting polynomials (hence our choice to take a large number of polynomials, rather than the first few, to compute the Gröbner basis). Nevertheless, it was usually possible to recover the message, as the polynomials in the Gröbner basis had a very simple form. In this particular case, for instance, p 4 is affine and p 3 can be written as (ay + bz + c) 2 , making it easy to recover the common root.

N i =

Fig. 1 .

 1 Fig. 1. pkcs#1 v1.5 Security

5

  Broadcast Attacks on pkcs#1 v1.5

Figure 2 Fig. 2 .

 22 Figure 2 summarizes our current knowledge of pkcs#1 v1.5 security.The authors regard the new flaws as an indication that the process of phasing out pkcs#1 v1.5 should be accelerated.

Fig. 3 .

 3 Fig. 3. Public-Key Encryption Security Hierarchy

p 1 =

 1 150 bits, m = 5 bits, r = 6 bits, e = 3, ν = 2 f (x, y, z) with modular root (24, 58, 34) z 4 + 512z 3 + 98304z

  If m is a message consisting of a string of 00 16 bytes, then c ′ is a valid ciphertext with probability at least 0.47. c ′ is a valid ciphertext corresponding to a message of the same length as m with probability

	at least:	64	239	ω-1
		1445	255

  In the length-checking case, it is over 2.8% (resp. 1.6%) for 64-bit (resp. 128-bit) randomizers.

	which is non-negligible.
	47	if the oracle doesn't check message length
	64 1445 • 239 255	ω-1 otherwise

  table.

		ℓ = 2		ℓ = 3		ℓ = 4
	ν 2	dim(L) 84	|m| 213	dim(L) 210	|m| 246	dim(L) 462	|m| 249
	3	220	306	715	395	2002	451
	4	455	359	1820	483	6188	578
	5	816	394	3876	542	15504	664
	6	1330	418	7315	584	33649	726
	7	2024	435	12650	615	65780	773
	10	5456	469	46376	675	324632	863

  2 + 86093442y -94710946z -1908346880 p 2 = yz 2 -89 81 z 3 + 256yz -7936 27 z 2 + 16384y -573440 27 z -33783328 81 p 3 = y 2 -62 27 yz + 961 729 z 2 -1024 27 y + 31744 729 z + 262144

729 p 4 = x -55297y + 63489z + 1048576

November 2009

Besides attempting to achieve indistinguishability.

A Preliminaries

In this appendix we recall a few basic definitions necessary for an accurate description of our attack:

A.1 Public-Key Encryption

A Public-Key Encryption Scheme P = (K, E, D) is a collection of three (probabilistic) algorithms:

A Key Generation Algorithm K: Given a security parameter k ∈ N, the algorithm K produces a pair (pk, sk) of matching public and private keys (which implicitly define a message space M). For all m ∈ M and for properly generated {pk, sk}, the following correctness condition holds:

An Encryption Algorithm

We will denote by A adversaries, defined in the next section.

A.2 rsa Encryption

In [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF], the algorithm K produces a pair (pk = (N, e), sk = d) where N = pq is the product of two large primes and e and d are such that ed = 1 mod ϕ(N ). The encryption of a message m ∈ M = Z * N , is simply c = m e mod N . c can be easily decrypted using d: m = c d mod N .

A.3 Security Definitions

Security is traditionally defined by combining an adversarial goal and an attack model. We refer to classical texts on provable security, such as [START_REF]Provable security for public-key schemes[END_REF], for precise statements of security definitions. Intuitively, a public-key encryption scheme P is: In the above, "no adversary" should be read as "an efficient adversary succeeding with a significant probability". The terms "efficiently", "significant probability", "significant information" and "meaningfully related" admit formal definitions which are beyond our scope.

Security notions for encryption schemes are obtained by combining an adversarial goal with an attack model:

Chosen-Plaintext Attack (CPA) A is given nothing more than pk.

Validating-Checking Attack (VCA) A is given access to a validitychecking oracle indicating only if a given ciphertext is a valid or not (i.e. returning the bit D(sk, c) ? =⊥). Note that this is not the same thing as a Plaintext-Checking Attack (PCA) [START_REF]Provable security for public-key schemes[END_REF].


Georg Fuchsbauer

Damien Vergnaud

Fair Blind Signatures without Random Oracles

Keywords: Blind signatures, Revocable anonymity, Standard model, Groth-Sahai proof system

A fair blind signature is a blind signature with revocable anonymity and unlinkability, i.e., an authority can link an issuing session to the resulting signature and trace a signature to the user who requested it. In this paper we first revisit the security model for fair blind signatures given by Hufschmitt and Traoré in 2007. We then give the first practical fair blind signature scheme with a security proof in the standard model. Our scheme satisfies a stronger variant of the Hufschmitt-Traoré model.

Introduction

A blind signature scheme is a protocol for obtaining a signature from an issuer such that the issuer's view of the protocol cannot be linked to the resulting message/signature pair. Blind signatures are employed in privacy-related protocols where the issuer and the message author are different parties (e.g., e-voting or e-cash systems). However, blind signature schemes provide perfect unlinkability and could therefore be misused by dishonest users. Fair blind signatures were introduced by Stadler, Piveteau and Camenisch [START_REF] Stadler | Fair blind signatures[END_REF] to prevent abuse of unlinkability. They allow two types of blindness revocation: linking a signature to the user who asked for the signature and identifying a signature that resulted from a given signing session. A security model for fair blind signatures was introduced by Hufschmitt and Traoré [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF].

We first revisit their security model and give a stronger variant. We then present the first efficient fair blind signature scheme with a standard-model security proof (i.e., without resorting to the random oracle heuristic) in the strengthened security model. We make extensive use of the non-interactive proof system due to Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] and of the automorphic signatures recently introduced by Fuchsbauer [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups[END_REF] and do not use interactive assumptions.

Prior work

The concept of blind signatures was introduced by Chaum in [START_REF] Chaum | Blind signatures for untraceable payments[END_REF]. A blind signature scheme is a cryptographic primitive that allows a user to obtain from the issuer (signer) a digital signature on a message of the user's choice in such a way that the issuer's view of the protocol cannot be linked to the resulting message/signature pair.

Blind signatures have numerous applications including e-cash: they prevent linking the withdrawal of money and the payment made by the same customer. However, the impossibility to link withdrawals and payments might lead to frauds (money laundering, blackmailing, . . . ). Some applications therefore require means to identify the resulting signature from the transcript of a signatureissuing protocol or to link a message/signature pair to the corresponding signing session.

Fair blind signatures were introduced by Stadler, Piveteau and Camenisch in [START_REF] Stadler | Fair blind signatures[END_REF] to provide these means. Several fair blind signature schemes have been proposed since then [SPC95, [START_REF] Abe | Provably secure fair blind signatures with tight revocation[END_REF][START_REF] Hufschmitt | Fair blind signatures revisited[END_REF] with applications to e-cash [START_REF] Gaud | On the anonymity of fair offline e-cash systems[END_REF] or e-voting [START_REF] Canard | Defeating malicious servers in a blind signatures based voting system[END_REF]. In [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF], Hufschmitt and Traoré presented a formal security model for fair blind signatures and a scheme based on bilinear maps that satisfies it in the random oracle model under an interactive assumption. In a recent independent work, Rückert and Schröder [START_REF] Rückert | Fair partially blind signatures[END_REF] proposed a generic construction of fair partially blind signatures [START_REF] Abe | How to date blind signatures[END_REF].

Our contribution

As a first contribution, we strengthen the security model proposed in [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF]. In our model, the algorithm opening a transcript not only returns information to identify the signature that resulted from it, but additionally outputs the user that requested the signature and gives a proof of correct tracing.

We give a definition of blindness analogously to [START_REF] Okamoto | Efficient blind and partially blind signatures without random oracles[END_REF], but additionally provide tracing oracles to the adversary. We propose a traceability notion that implies the original one. Finally, we formalize the non-frameability notions analogously to [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF], where it is the adversary's task to output a framing signature (or transcript) and a proof. We believe that our version of signature non-frameability is more intuitive: no corrupt issuer can output a transcript, a "framing" opening of it and a proof (in [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF], the adversary must output a message/signature pair such that an honest transcript opens to it). (cf. § 2.3 for details.)

In 2008, Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] proposed a way to produce efficient noninteractive zero-knowledge (NIZK) and non-interactive witness-indistinguishable (NIWI) proofs for (algebraic) statements related to groups equipped with a bilinear map. In particular, they give proofs of satisfiability of pairing-product equations (cf. § 4.2). In [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups[END_REF], Fuchsbauer introduced the notion of automorphic signatures whose verification keys lie in the message space, messages and signatures consist of group elements only, and verification is done by evaluating a set of pairing-product equations (cf. § 5). Among several applications, he constructed an (automorphic) blind signature in the following way: the user commits to the message, and gives the issuer a randomized message; the issuer produces a "pre-signature" from which the user takes away the randomness to recover a signature. The actual signature is then a Groth-Sahai proof of knowledge of a signature, which guarantees unlinkability to the issuing.

In this paper, we modify Fuchsbauer's blind signature scheme in order to construct the first practical fair blind signature scheme with a security reduc-tion in the standard model. Our security analysis does not introduce any new computational assumptions and relies only on falsifiable assumptions [START_REF] Naor | On cryptographic assumptions and challenges (invited talk)[END_REF] (cf. § 3). First, we extend Fuchsbauer's automorphic signature so it can sign three messages at once. Then, since in fair blind signature schemes blindness has to hold even against adversaries provided with tracing oracles, we use Groth's technique from [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF] to achieve CCA-anonymous group signatures: instead of just committing to the tracing information, we additionally encrypt it (using Kiltz' tag-based encryption scheme [START_REF] Kiltz | Chosen-ciphertext security from tag-based encryption[END_REF]) and provide NIZK proofs of consistency with the commitments. In order to achieve the strengthened notion of non-frameability, we construct simulation-sound NIZK proofs of knowledge of a Diffie-Hellman solution which consist of group elements only and are verified by checking a set of pairing-product equations (i.e. Groth-Sahai compatible proofs).

Since messages and signatures consist of group elements only and their verification is done by evaluating a set of pairing-product equations, our fair blind signatures are Groth-Sahai compatible themselves which makes them perfectly suitable to design efficient fair e-cash systems following the approach proposed in [START_REF] Gaud | On the anonymity of fair offline e-cash systems[END_REF]. In addition, our scheme is compatible with the "generic" variant1 of Votopia [OMA + 99] proposed by Canard, Gaud and Traoré in [START_REF] Canard | Defeating malicious servers in a blind signatures based voting system[END_REF]. Combined with a suitable mix-net (e.g. [START_REF] Groth | A non-interactive shuffle with pairing based verifiability[END_REF]), it provides a practical electronic voting protocol in the standard model including public verifiability, and compares favorably with other similar systems in terms of computational cost. Setup is a PPT that takes as input an integer λ and outputs the parameters pp and the revocation key rk. We call λ the security parameter. IKGen is a PPT that takes as input the parameters pp and outputs a pair (ipk, isk), the issuer's public and secret key. UKGen is a PPT that takes as input the parameters pp and outputs a pair (upk, usk), the user's public and secret key. Sign and User are interactive PPTs such that User takes as inputs the parameters pp, the issuer's public key ipk, the user's secret key usk and a bit string m; Sign takes as input pp, the issuer's secret key isk and user public key upk. Sign and User engage in the signature issuing protocol and when they stop, Sign outputs completed or not-completed while User outputs ⊥ or a bit string σ.

The Model

Ver is a deterministic PT that on input the parameters pp, an issuer public key ipk and a pair of bit strings (m, σ) outputs either 0 or 1. If it outputs 1 then σ is a valid signature on the message m TrSig is a deterministic PT that on input pp, an issuer public key ipk, a transcript of a signature issuing protocol and a revocation key rk outputs three bit strings (upk, id σ , π). TrId is a deterministic PT that on input pp, an issuer public key ipk, a pair message/signature (m, σ) for ipk and a revocation key rk outputs two bit strings (upk, π). ChkSig is a deterministic PT that on input pp, an issuer public key ipk, a transcript of a signature issuing protocol, a pair message/signature (m, σ) for ipk and three bit strings (upk, id σ , π), outputs either 0 or 1. ChkId is a deterministic PT that on input pp, an issuer public key ipk, a pair message/signature (m, σ) for ipk and two bit strings (upk, π), outputs either 0 or 1.

For all λ ∈ N, all pairs (pp, rk) output by Setup(λ) all pairs (ipk, isk) output by IKGen(pp), and all pairs (upk, usk) output by UKGen(pp):

1. if Sign and User follow the signature issuing protocol with input (pp, isk, upk) and (pp, usk, ipk, m) respectively, then Sign outputs completed and User outputs a bit string σ that satisfies Ver(ipk, (m, σ)) = 1; 2. on input ipk, the transcript trans of the protocol and rk, TrSig outputs three bit strings (upk, id σ , π) s.t. ChkSig(pp, ipk, trans, (m, σ), (upk, id σ , π)) = 1; 3. on input ipk, the pair (m, σ) and rk, TrId outputs two bit strings (upk, π) such that ChkId(pp, ipk, (m, σ), (upk, π)) = 1.

Security Definitions

To define the security notions for fair blind signatures, we use a notation similar to the one in [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] used in [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF]:

HU denotes the set of honest users and CU is the set of corrupted users.

AddU is an add-user oracle. By calling this oracle, the adversary creates a new user with keys (upk, usk). The oracle adds upk to HU and returns it to the adversary. CrptU is a corrupt-user oracle. The adversary calls this oracle with a pair (upk, usk) and upk added to the set CU. USK is a user-secret-key oracle enabling the adversary to obtain the private key usk for some upk ∈ HU. The oracle transfers upk to CU and returns usk. User is an honest-user oracle. The adversary impersonating a corrupt issuer calls it with (upk, m). If upk ∈ HU, the experiment simulates the honest user holding upk running the signature issuing protocol with the adversary for message m. If the issuing protocol completed successfully, the adversary is given the resulting signature. The experiment keeps a list Set with entries of the form (upk, m, trans, σ), to record an execution of User, where trans is the transcript of the issuing protocol and σ is the resulting signature. (Note that only valid σ's (i.e., the protocol was successful) are written to Set.

Sign is a signing oracle. The adversary impersonating a corrupt user can use it to run the signature issuing protocol with the honest issuer. The experiment keeps a list Trans in which the transcripts trans i resulting from Sign calls are stored. Challenge b is a challenge oracle, which (w.l.o.g.) can only be called once. The adversary provides two user public keys upk 0 and upk 1 and two messages m 0 and m 1 . The oracle first simulates User on inputs (pp, ipk, usk b , m b ) and then, in a second protocol run, simulates User on inputs (pp, ipk, usk 1-b , m 1-b ).

Finally, the oracle returns (σ 0 , σ 1 ), the resulting signatures on m 0 and m 1 . TrSig (resp. TrId) is a signature (resp. identity) tracing oracle. When queried on the transcripts (or messages) emanating from a Challenge call, they return ⊥.

Figure 1 formalizes the experiments for the following security notions:

Blindness. Not even the issuer with access to tracing oracles can link a message/signature pair to the signature issuing session it stems from. Identity Traceability. No coalition of users can produce a set of signatures containing signatures which cannot be linked to an identity. Signature Traceability. No one should be able to produce a message/signature pair which is not traced by any issuing transcript or two pairs which are traced by the same transcript. Identity Non-Frameability. No coalition of issuer, users and tracing authority should be able to provide a signature and a proof that the signature opens to an honest user who did not ask for the signature. Signature Non-Frameability. No coalition of issuer, users and tracing authority should be able to provide a transcript that either wrongfully opens to an honest signature or an honest user.

We say that a fair blind signature achieves blindness if for all PPT adversaries A, the following is negligible:

| Pr[Exp blind-1 A = 1] -Pr[Exp blind-0 A = 1] -1 2 .
The remaining security notions are achieved if for all PPT A, the probability that the corresponding experiment returns 1 is negligible.

A Note on the Hufschmitt-Traoré Security Notions

Blindness. In [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF], the challenge oracle (called "Choose") is defined as follows: the adversary provides two user public keys upk 0 and upk 1 and a message, and obtains a signature under upk b . This gives a weak security guarantee, as the adversary-who impersonates the issuer-cannot actively participate in the issuing of the challenge signature. We define our oracle in the spirit of [START_REF] Okamoto | Efficient blind and partially blind signatures without random oracles[END_REF]: the adversary impersonating the issuer chooses two users (and messages) which interact with him in random order; he gets to see both resulting signatures and has to determine the order of issuing.

Traceability Notions. Intuitively, identity traceability means that no coalition of users and the authority can create a message signature pair that is not traceable to a user, which is what was formalized in [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF].

Exp blind-b A (λ) (pp, rk) ← Setup(1 λ ); (ipk, isk) ← IKGen(pp) b ← A(pp, ipk, isk : AddU, CrptU, USK, Challenge b , User, TrSig, TrId) return b Exp IdTrac A (λ) (pp, rk) ← Setup(1 λ ); (ipk, isk) ← IKGen(pp) Trans ← ∅ (m 1 , σ 1 , . . . , mn, σn) ← A(pp, ipk, rk : AddU, CrptU, USK, Sign) for i = 1 . . . |Trans| do (upk i , id i , π i ) ← TrSig(pp, rk, ipk, trans i ) for i = 1 . . . n do (upk i , π i ) ← TrId(pp, rk, ipk, m i , σ i ) if ∃ i : upk i = ⊥ or ChkId(pp, ipk, (m i , σ i ), upk i , π i ) = 0
return 1 if some upk appears more often in (upk 1 , . . . , upk n ) than in (upk 1 , . . . , upk |Trans| ) then return else return 0

Exp IdNF A (λ) (pp, rk) ← Setup(1 λ ); (ipk, isk) ← IKGen(pp) Set ← ∅; HU ← ∅; CU ← ∅ (upk, m, σ, π) ← A(pp, ipk, isk, rk : AddU, CrptU, USK, User) if Ver(pp, ipk, m, σ) = 0 or ChkId(pp, ipk, m, σ, upk, π) = 0 then return 0 if (upk, m, •, σ) /
∈ Set and upk ∈ HU then return 1; else return 0

Exp SigTrac A (λ) (pp, rk) ← Setup(1 λ ); (ipk, isk) ← IKGen(pp) Trans ← ∅ (m 1 , σ 1 , m 2 , σ 2 ) ← A(pp, ipk, rk : AddU, CrptU, USK, Sign) let Trans = (trans i ) n i=1 ; for i = 1 . . . n do (upk i , id i , π i ) ← TrSig(pp, rk, ipk, trans i ) if Ver(pp, ipk, m 1 , σ 1 ) = 1 and ∀ i : ChkSig(pp, ipk, trans i , m 1 , σ 1 , upk i , id i , π i ) = 0 then return if (m 1 , σ 1 ) = (m 2 , σ 2 ) and Ver(pp, ipk, m 1 , σ 1 ) = 1 and Ver(pp, ipk, m 2 , σ 2 ) = 1 and ∃ i : ChkSig(pp, ipk, trans i , m 1 , σ 1 , upk i , id i , π i ) = = ChkSig(pp, ipk, trans i , m 2 , σ 2 , upk i , id i , π i )) = then return 1; else return 0 Exp SigNF A (λ) (pp, rk) ← Setup(1 λ ); (ipk, isk) ← IKGen(pp) Set ← ∅; HU ← ∅; CU ← ∅ (trans * , m * , σ * , upk * , id * σ , π * ) ← A(pp, ipk, isk, rk : AddU, CrptU, USK, User) let Set = (upk i , m i , trans i , σ i ) n i=1 if ∃ i : trans * = trans i and ChkSig(pp, ipk, trans * , m i , σ i , upk * , id * σ , π * ) = 1 then return 1 if ( ∀ i : upk * = upk i ⇒ trans * = trans i )
and ChkSig(. . . , trans * , m * , σ * , upk * , id * σ , π * ) = then return 1; else return 0 We propose the following experiment leading to a stronger notion: the adversary gets the authority's key and impersonates corrupt users, who, via the Sign oracle can request signatures from the honest issuer. The latter is simulated by the experiment and keeps a set Trans of transcripts of oracle calls. Eventually, the adversary outputs a set of message/signature pairs. The experiment opens all transcripts to get a list of users to which signatures were issued. Another list of users is constructed by opening the returned signatures. The adversary wins if there exists a user who appears more often in the second list than in the first, or if ⊥ is in the second list or if any of the proofs output by the opening algorithm do not verify. Note that the notion of [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF] is implied by ours.

Non-Frameability Notions. Non-frameability means that not even a coalition of everyone else can "frame" an honest user. For example, no adversary can output a signature which opens to a user who did not participate in its issuing. In [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF], the adversary outputs a message/signature pair, which is then opened by the experiment to determine if it "framed" a user. Analogously to [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] (who defined non-frameability for group signatures), we define a stronger notion requiring the adversary to output an incriminating signature, an honest user and a valid proof, that the signature opens to that user. Note that only this formalization makes the π output by the tracing algorithms a proof, as it guarantees that no adversary can produce a proof that verifies for a false opening.

Identity Non-Frameability. In [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF], the adversary wins if it produces a pair (m, σ) such that, when opened to upk, we have (m, σ, upk) / ∈ Set. This seems to guarantee a strong notion of unforgeability where an adversary modifying a signature wins the game. This is however not the case in the scheme proposed in [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF]: the final signature is a proof of knowledge of some values computed by the issuer made non-interactive by the Fiat-Shamir heuristic; hence from a given signature issuing session the user may derive several valid signatures on a message m. For that reason, the model in [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF] considers that two signatures are different only if the underlying secrets are different. We adopt the same convention in this paper in that we consider two signatures equivalent if they have the same identifier.

Signature Non-Frameability. Non-frameability of signature tracing intuitively means: even if everyone else colludes against an honest user, they cannot produce a transcript that opens to an honest signature. In the definition proposed in [START_REF] Hufschmitt | Fair blind signatures revisited[END_REF], the adversary plays the issuer in that he gets his secret key. However, he has no possibility to communicate with honest users since the challenger plays the issuer in the signature issuing sessions with honest users and the adversary only gets the transcripts. His goal is to produce a new message/signature pair (one that does not emanate from a User-oracle call) such that an honest transcript opens to it.

We give the following security notion which we think is more intuitive. No corrupt issuer can produce a transcript of an issuing session and one of the following: either a public key of an honest user and a proof that this user participated in the transcript whereas he did not; or a signature identifier of an honest signature coming from a different session and a proof that the transcript opens to it. Similarly to signatures we consider two transcripts equivalent if the contain the same user randomness and the same issuer randomness.

Unforgeability. Consider an adversary that breaks the classical security notion for blind signatures, one-more unforgeability, i.e., after q -1 Sign-oracle queries, he outputs q signatures on different messages. We show that the adversary must have broken signature traceability: indeed since there are more signatures than transcripts, either there is a signature which no transcripts points to, or there is a transcript that points to two signatures.

Assumptions

A (symmetric) bilinear group is a tuple (p, G, G T , e, G) where (G, •) and (G T , •) are two cyclic groups of prime order p, G is a generator of G, and e : ande(G, G) is a generator of G T .

G × G → G T is a non-degenerate bilinear map, i.e., ∀ U, V ∈ G ∀ a, b ∈ Z : e(U a , V b ) = e(U, V ) ab ,
The Decision Linear (DLIN) Assumption [START_REF] Boneh | Short group signatures[END_REF], in (p, G, G T , e, G) states that given (G α , G β , G rα , G sβ , G t ) for random α, β, r, s ∈ Z p , it is hard to decide whether t = r + s or t is random.

The following two assumptions were introduced by [FPV09] and [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups[END_REF], respectively. Under the knowledge of exponent assumption [START_REF] Damgård | Towards practical public key systems secure against chosen ciphertext attacks[END_REF], the first is equivalent to SDH [START_REF] Boneh | Short signatures without random oracles[END_REF] and the second is equivalent to computing discrete logarithms.

Assumption 1 (q-DHSDH). Given (G, H, K, X = G x ) ∈ G 4 and q -1 tuples

A i = (KG vi ) 1 x+d i , C i = G di , D i = H di , V i = G vi , W i = H vi q-1 i=1 , for d i , v i ← Z p , it
The next assumption states that, given (G, H, T

) ∈ G 3 , it is hard to produce a non-trivial (G m , H m , G r , H r ) such that G m = T r . Assumption 2 (HDL). Given a random triple (G, H, T ) ∈ G 3 , it is hard to output (M, N, R, S) = (1, 1, 1, 1) such that e(R, T ) = e(M, G) e(M, H) = e(G, N ) e(R, H) = e(G, S) (2)
4 Tools

We recall some tools from the literature which we use to construct our scheme.

A Signature Scheme to Sign Group Elements

We present the signature scheme from [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups[END_REF], which is secure against chosenmessage attacks under Assumptions 1 and 2. Its message space is the set of Diffie-Hellman pairs

DH := {(A, B) ∈ G 2 | ∃α : A = G α , B = H α } w.

Groth-Sahai Proofs

We sketch the results of Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] on proofs of satisfiability of sets of equations over a bilinear group (p, G, G T , e, G). Due to the complexity of their methodology, we merely give what is needed for our results and refer to the full version of [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] for any additional details. We define a key for linear commitments. Choose α, β, r 1 , r 2 ∈ Z p and define U = G α , V = G β , and u 1 := (U, 0, G), u 2 := (0, V, G), u 3 := (W 1 , W 2 , W 3 ) where W 1 := U r1 , W 2 := V r2 , for random r 1 , r 2 ← Z p , and W 3 is either soundness setting: W 3 := G r1+r2 (which makes u a binding key) witness-indistinguishable setting: W 3 := G r1+r2-1 (making u a hiding key)

Under key ck = (U, V, W 1 , W 2 , W 3 ), a commitment to a group element X ∈ G using randomness (s 1 , s 2 , s 3 ) ← Z 3 p is defined as (with ι(X) := (0, 0, X))

Com ck, X; (s 1 , s 2 , s 3 ) := ι(X) • 3 i=1 u si i = (U s1 W s3 1 , V s2 W s3 2 , XG s1+s2 W s3 3 ) .
In the soundness setting, given the extraction key ek := (α, β), the committed value can be extracted from a commitment c = (c 1 , c 2 , c 3 ). On the other hand, in the witness-indistinguishable (WI) setting, c is equally distributed for every X. The two settings are indistinguishable under the DLIN assumption. A pairing-product equation is an equation for variables

Y 1 , . . . , Y n ∈ G of the form n i=1 e(A i , Y i ) n i=1 n j=1 e(Y i , Y j ) γi,j = t T , with A i ∈ G, γ i,j ∈ Z p and t T ∈ G T .
To show satisfiability of a set of equations of this form, one first makes commitments to a satisfying witness (i.e., an assignment to the variables of each equation) and then adds a "proof" per equation. Groth and Sahai describe how to construct these: they are in G 3×3 . In the soundness setting, if the proof is valid, then Extr extracts the witness satisfying the pairing-product equation. In the WI setting, commitments and proofs of different witnesses which both satisfy the same pairing-product equation are equally distributed.

Commit and Encrypt

In order to build CCA-anonymous group signatures, Groth [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF] uses the following technique: a group signature consists of linear commitments to a certified signature and Groth-Sahai proofs that the committed values constitute a valid signature. CPA-anonymity follows from WI of GS proofs: once the commitment key has been replaced by a perfectly hiding one, a group signature reveals no information about the signer. However, in order to simulate opening queries in the WI setting, some commitments are doubled with a tag-based encryption under Kiltz' scheme [START_REF] Kiltz | Chosen-ciphertext security from tag-based encryption[END_REF] and a Groth-Sahai NIZK proof that the committed and the encrypted value are the same. To produce a group signature, the user first chooses a key pair for a one-time signature scheme, uses the verification key as the tag for the encryption and the secret key to sign the group signature.

By Sig ot = (KeyGen ot , Sign ot , Ver ot ) we will denote the signature scheme discussed in § 5.2 which satisfies the required security notion. By CEP (commitencrypt-prove) we denote the following: CEP(ck, pk, tag, msg; (ρ, r)) := Com(ck, msg; ρ), Enc(pk, tag, msg; r), NizkEq(ck, pk, msg, tag, ρ, r)

where Enc denotes Kiltz' encryption and NizkEq denotes a Groth-Sahai NIZK proof that the commitment and the encryption contain the same plaintext (cf. [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF]). We say that an output ψ = (c, C, ζ) of CEP is valid if the ciphertext and the zero-knowledge proof are valid.

New Tools

A Scheme To Sign Three Diffie-Hellman Pairs

We extend the scheme from § 4.1, so it signs three messages at once; we prove existential unforgeability against adversaries making a particular chosen message attack: the first message is given (as usual) as a Diffie-Hellman pair, whereas the second and third message are queried as their logarithms, i.e., instead of querying (G v , H v ), the adversary has to give v explicitly. As we will see, this combines smoothly with our application.

Scheme 2 (Sig 3 ). Theorem 1. Sig 3 is existentially unforgeable against adversaries making chosen message attacks of the form ((M 1 , N 1 ), m 2 , m 3 ).

Proof. Let (M i , N i , y i , v i ) be the queries, (A i , C i , D i , R i = G ri , S i ) be the responses. Let (M, N, Y, Z, V, W ) and (A, C, D, R = G r , S) be a successful forgery.

We distinguish 4 types of forgers (where

Y i := G yi , V i := G vi ): Type I ∀ i : T ri M i Y i V u i = T r M Y V u (5) Type II ∃ i : T ri M i Y i V u i = T r M Y V u ∧ M i Y i V u i = M Y V u (6) Type III ∃ i : M i Y i V u i = M Y V u ∧ M i V u i = M V u (7) Type IV ∃ i : M i Y i V u i = M Y V u ∧ M i V u i = M V u ( 8
)
Type I is reduced to DHSDH. Let G, H, K, (A i , C i , D i , E i , F i ) q-1 i=1 be an instance. Choose and t, , u ← Z p and set

T = G t , L = G and U = G u . A signature on (M i , N i , Y i , Z i , y i , V i , W i , v i ) is (after a consistency check) answered as (A i , C i , D i , (E i M -1 i Y - i V -u i ) 1/t , (F i N -1 i Z - i W -u i ) 1/t
). After a successful forgery, return (A, C, D, R t M Y V u , S t N Z W u ), which is a valid DHSDH solution by (5). Type II is reduced to HDL. Let (G, H, T ) be an HDL instance. Generate the rest of the parameters and a public key and answer the queries by signing. After a successful forgery, return

(M Y V u M -1 i Y - i V -u i , N Z W u N -1 i Z - i W -u i , R i R -1 , S i S -1
), which is non-trivial by (6). Type III is reduced to HDL. Let (G, H, L) be an instance. Choose K, T ← G and x, u ← Z p and return the parameters and public key (X = G x , L, U = G u ). Thanks to the y i in the signing queries, we can simulate them: return

((KT ri M i L yi V u i ) 1 x+d i , G di , H di , G ri , H ri ). From (7) we have M V u M -1 i V -u i = Y i Y -= L yi-y ,
so from a successful forgery, we can return

(M V u M -1 i V -u i , N W u N -1 i W -u i , Y i Y -1 , Z i Z -1
) which is non-trivial by (7).

Type IV is also reduced to HDL. Let (G, H, U ) be an HDL instance. Choose K, T ← G and x, ← Z p and return the parameters and public key (X = G x , L = G , U ). Thanks to the v i in the signing queries, we can simulate them: return ((

KT ri M i Y i U vi ) 1 x+d i , G di , H di , G ri , H ri ).
From a successful forgery of Type IV we have M M -1 i = U vi-v from (7), we can thus return

(M M -1 i , N N -1 i , V i V -1 , W i W -1
), which is non-trivial, (M, N, Y, Z, V, W ) being a valid forgery and (Y, Z) = (Y i , Z i ) by (8).

A Simulation-Sound Non-Interactive Zero-Knowledge Proof of Knowledge of a CDH Solution

Let (G, F, V ) be elements of G. We construct a simulation-sound non-interactive zero-knowledge (SSNIZK) proof of knowledge (PoK) of W s.t. e(V, F ) = e(G, W ). We follow the overall approach by Groth [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF]. The common reference string (CRS) contains a CRS for Groth-Sahai (GS) proofs and a public key for a EUF-CMA signature scheme Sig. A proof is done as follows: choose a key pair for a one-time signature scheme Sig ot , and make a witness-indistinguishable GS proof of the following: either to know W , a CDH solution for (G, F, V ) or to know a signature on the chosen one-time key which is valid under the public key from the CRS;2 finally sign the proof using the one-time key. A SSNIZKPoK is verified by checking the GS proofs and the one-time signature. Knowing the signing key corresponding to the key in the CRS, one can simulate proofs by using as a witness a signature on the one-time key. We require that a proof consist of group elements only and is verified by checking a set of pairing-product equations. This can be achieved by using the scheme from Scheme 1 and a one-time scheme to sign group elements using the commitment scheme in [START_REF] Groth | Homomorphic trapdoor commitments to group elements[END_REF] based on the DLIN assumption.3

A Fair Blind Signature Scheme

The basis of our protocol is the blind automorphic signature scheme from [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups[END_REF]: the user randomizes the message to be signed, the issuer produces a pre-signature from which the user obtains a signature by removing the randomness; the final signature is a Groth-Sahai proof of knowledge of the resulting signature.

In our scheme, in addition to the message, the issuer signs the user's public key, and an identifier of the signature, which the issuer and the user define jointly. Note that the issuer may neither learn the user's public key nor the identifier. To guarantee provable tracings, the user signs what she sends in the issuing protocol and the final signature. To prevent malicious issuers from producing a transcript that opens to an honest signature, the proof contains a SSNIZK proof of knowledge of the randomness introduced by the user. To guarantee blindness against adversaries with tracing oracles, the elements that serve as proofs of correct tracing are additionally encrypted and the transcript (and final signature) is signed with a one-time key (cf. § 4.3).

To trace a signature, the authority extracts tracing information from the commitments as well as signatures that act as proofs.

Setup and Key Generation

Setup. Choose a bilinear group G := (p, G, G T , e, G) and parameters (H, K, T ) for Sig 3 . Pick F, H ← G, a commitment and extraction key (ck, ek) for Groth-Sahai proofs, a key pair for tag-based encryption (epk, esk) and sscrs, a common reference string for SSNIZKPoK. Output pp := (G, G, H, K, T, F, H , ck, epk, sscrs) and rk := ek. Key Generation. Both IKGen and UKGen is defined as KeyGen, i.e., the key generation algorithm for Sig 1 (and Sig 3 ).

The Signature Issuing Protocol and Verification

The common inputs are (pp, ipk = G x ), the issuer's additional input is isk = x, the user's additional inputs are (upk = G y , usk = y, (M, N ) ∈ DH).

1. User Choose η, v ← Z p and set P = G η , Q = F η , V = G v , W = F v .
Produce ξ ← SSNIZKPoK(sscrs, (P, V ), (Q, W )).4 Choose (vk ot , sk ot ) ← KeyGen ot (G) and set Σ ← Sign(usk, vk ot ). 5 Send the following

(a) Y = G y , Z = H y , vk ot , Σ , (b) c M = Com(ck, M ); c N := Com(ck, N ), ψ P , ψ V , ψ ξ , with ψ := CEP(ck, epk, vk ot , ), a proof φ M that (M, N ) ∈ DH and a proof φ ξ of validity of ξ, (c) J := (KM L y U v ) 1 η , (d) a zero-knowledge proof ζ of knowledge of η, y and v such that -Y = G y ; -c V commits to G v ; and -c M commits to J η L -y U -v K -1 . (e) sig ← Sign ot (sk ot , (Y, Z, Σ , c M , c N , ψ P , ψ V , ψ ξ , φ M , φ ξ , J, ζ, vk ot )).
2. Issuer If Σ , ψ P , ψ V , ψ ξ as well as φ M , φ ξ , sig and the proof of knowledge are valid, choose d, r, v ← Z p and send:

A := (JT r U v ) 1 x+d C := G d D := F d R := G r S := H r v
The user does the following:

(a) set A := (A ) η , R := (R ) η , S := (S ) η , V := G v +ηv , W := H v
(f) set sig ← Sign ot sk ot , (V, W, M, N, c A , c C , c D , c R , c S , ψ Y , ψ Z , ψ Σ , φ Y , φ S , φ Σ , vk ot ) .
The signature on (M, N ) is

(V, W, c A , c C , c D , c R , c S , ψ Y , ψ Z , ψ Σ , φ Y , φ S , φ Σ , vk ot , sig) .
A signature is verified by verifying sig under vk ot , checking the proofs φ Y , φ S and φ Σ , and verifying the encryptions and NIZK proofs in ψ Y , ψ Z and ψ Σ .

Remark 1. As mentioned by [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups[END_REF], there are two possible instantiations of the zero-knowledge proof of knowledge in 1.d: either using bit-by-bit techniques (which does not increase the rounds of the protocol); or optimizing the amount of data sent by adding 3 rounds using interactive concurrent Schnorr proofs.

Theorem 2. The above scheme is an unforgeable blind signature (in the classical sense) under the DLIN, the DHSDH and the HDL assumptions.

The proof of unforgeability is by reduction to unforgeability of Scheme 2, analogously to the proof in [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups[END_REF]. Note that by additionally extracting y and v from the proof of knowledge, the simulator can make the special signing queries. The proof of blindness is also analogous to [START_REF] Fuchsbauer | Automorphic signatures in bilinear groups[END_REF].

Tracing Algorithms

Opening of a Transcript ("Signature Tracing"). Given a transcript (Y, Z, Σ , c M , c N , ψ P , ψ V , ψ ξ , φ M , φ ξ , J, ζ, vk ot , sig ) , v verify Σ , sig , the proofs φ M and φ ξ and the ciphertexts and proofs in ψ P , ψ V and ψ ξ . If everything is valid, use rk = ek to open the commitments in ψ P , ψ V and ψ ξ to P, V and ξ respectively and set V :

= V P v = G v +ηv .
Return id σ := V , upk = Y and π := (V , P, v , ξ, Σ ). The proof π is verified by checking V = V P v , verifying ξ on V and P , and verifying Σ under Y .

Opening of a Signature ("Identity Tracing"). Given a valid signature

(V, W, c A , c C , c D , c R , c S , ψ Y , ψ Z , ψ Σ , φ Y , φ S , φ Σ , vk ot , sig) ,
open the commitments in ψ Y , ψ Z and ψ Σ using ek and return upk = Y and π = Σ. A proof π is verified by checking if Σ is a valid signature on (V, W ) under Y .

Security Proofs

Theorem 3. The above scheme is a secure fair blind signature scheme (in the model defined in § 2) under the DLIN, the DHSDH and the HDL assumptions.

Due to space limitation, we sketch the security proofs of all security notions. Blindness (under DLIN). In the witness-indistinguishability setting of Groth-Sahai proofs, the commitments and proofs do not reveal anything-and neither do the ciphertexts. Furthermore, for every M and V , there exist η and v that explain J. In more detail: the proof proceeds by games, Game 0 being the original game. In Game 1, we use the decryption key for the tag-based encryptions to answer queries to trace signatures and identities. The zero-knowledge proofs in the ψ's guarantees that the committed and the encrypted values are the same; the games are thus indistinguishable.

In Game 2, we replace the commitment key ck by a witness indistinguishable one. In Game 3, we simulate the NIZK proofs in the ψ's and in Game 4, we replace the ciphertexts in the ψ's by encryptions of 0. Games 3 and 4 are indistinguishable by selective-tag weak CCA security of Kiltz' cryptosystem (which follows from DLIN): by unforgeability of the one-time signature, the adversary cannot query a different transcript (or signature) with the same tag as the target transcript (or signature), therefore we can answer all tracing queries.

In Game 5, we simulate the zero-knowledge proofs in Step 1d. In this game, the adversary's view is the following: J = (KM L y U v ) 1 η and M * , V * which are either M and G v +ηv or not. Let small letters denote the logarithms of the respective capital letters. Then for every m * = log M * , v * = log V * there exist η, v such that v * = v +ηv and j = 1 η (k +m * +yl +v u), i.e., that make M * , V * consistent with J. In Game 5, which is indistinguishable from the original game, the adversary has thus no information on whether a given transcript corresponds to a given signature.

Identity Traceability (under DHSDH+HDL). An adversary wins if he can produce a set of valid pairs (m i , σ i ) s.t. either (I) for one of them the tracing returns ⊥ or the proof does not verify, or (II) a user appears more often in the openings of the signatures than in the openings of the transcripts. By soundness of Groth-Sahai, we can always extract a user public key and a valid signature. If an adversary wins by (II), then we can use him to forge a Sig 3 signature:

Given parameters and a public key for Sig 3 , we set up the rest of the parameters for the blind signature. Whenever the adversary queries his Sign oracle, we do the following: use ek to extract (M, N ) from (c M , c N ), extract η, y and v from the zero-knowledge proof ζ. Choose v ← Z p and query (M, N, y, v + ηv ) to signing oracle to receive (A, C, D, R, S). Return (A

1 η , C, D, R 1 η , S 1 η , v ).
If the adversary wins by outputting a set of different (i.e., with distinct identifiers (V, W )) blind signatures with one user appearing more often then in the transcripts, then among the Sig 3 signatures extracted from the blind signatures there must be a forgery.

Identity Non-Frameability (under DLIN+DHSDH+HDL). Using a successful adversary, we can either forge a signature by the user on vk ot or a one-time signature (which is secure under DLIN). More precisely, we call an adversary of Type I if it reuses a one-time key from the signatures it received from the User oracle. Since the signature A returns must not be contained in Set, it is different from the one containing the reused one-time key. The contained one-time signature can thus be returned as a forgery.

An adversary of Type II uses a new one-time key for the returned signature. We use A to forge a Sig signature. The simulator is given parameters (H , K, T ) and a public key Y for Sig, sets it as one of the honest users' upk and queries its signing oracle to simulate the user. Having set H = G h , the simulator can produce Z = H y = Y h in the User oracle queries. Since the vk ot contained A's output was never queried, we get a valid forgery.

Signature Traceability (under DHSDH+HDL). If the adversary wins by outputting a message/signature pair with an identifier (V, W ) s.t. no transcript opens to it, we can extract a Sig 3 signature on (M, N, Y, Z, V, W ) without having ever queried a signature on any (•, •, •, •, V, W ). The simulation is done analogously to the proof of identity traceability. Consider an adversary outputting two message/signature pairs with two different messages. With overwhelming probability, the identifiers of the signatures are different (since v is chosen randomly by the experiment after the adversary chose v and η). Thus the simulator only asked one query for (•, •, •, •, V, W ). The second signature can therefore be returned as a forgery by the simulator. Lastly, if the messages are the same, the signatures must be different, thus have different identifiers. One of the ChkSig calls in the experiment returns thus 0.

Signature Non-Frameability (under DLIN+DHSDH+HDL). There are two ways for an issuer to "wrongfully" open a transcript: either he opens it to a user (not necessarily honest) and an identifier of a signature which was produced by an honest user in another session; or it opens it to an honest user who has not participated in the issuing session.

Framing an honest signature. Suppose the adversary impersonating the issuer manages to produce a new opening of a transcript that leads to an honestly generated signature.

We reduce this framing attack to break CDH, whose hardness is implied by that of DLIN. Let (G, F, V ) be a CDH challenge, i.e., we seek to produce W := F (log G V ) . Set up the parameters of the scheme setting H = G h and knowing the trapdoor for SSNIZKPoK. In one call of the adversary's User oracle calls we do the following: choose η ← Z p and use V from the CDH challenge. Simulate the proof of knowledge of W . Let v be the value returned from the adversary, and (V := V P η , W := V h ) be the identifier of the resulting signature.

Suppose the adversary produces a proof ( V , P , v , π, Σ) with ( V , P ) = (V , P ) for the honest identifier (V, W ). By simulation soundness of SSNIZKPoK, we can extract W = F (log G V ) and Q = F (log G P ) . From V G ηv = V = V P v we get V = V P v G -ηv and thus W = W Qv F -ηv is a CDH solution. If the adversary recycles (V , P ), then it must find a new v which leads to a V of an honest signature, and thus has to solve a discrete logarithm.

Framing an honest user. Suppose the adversary outputs an opening of a transcript and a proof revealing an honest user that has never participated in that transcript. Analogously to the proof for signature traceability, we can use the adversary to either forge a signature under a user public key or to forge a one-time signature.

Conclusion

We presented the first efficient fair blind signature scheme with a security proof in the standard model. The scheme satisfies a new security model that strengthens the one proposed by Hufschmitt and Traoré in 2007. The new scheme is efficient (both keys and signatures consist of a constant number of group elements) and does not rely on any new assumptions. As byproducts, we proposed an extension of Fuchsbauer's automorphic signatures and a simulation-sound non-interactive zero-knowledge proof of knowledge of a Diffie-Hellman solution, both compatible with the Groth-Sahai methodology.

A A One-Time Signature on Vectors of Group Elements Our one-time signature is based on the simultaneous triple pairing assumption (STP) stating that the following problem is hard: Given random generators (g r , h r , g s , h s , g t , h t ) ∈ G 6 , output (r, s, t) ∈ G 3 \ {(1, 1, 1)} such that e(g r , r) e(g s , s) e(g t , t) = 1 e(h r , r) e(h s , s) e(h t , t) = 1

In Groth [START_REF] Groth | Homomorphic trapdoor commitments to group elements[END_REF] proves that DLIN implies STP and presents a homomorphic commitment scheme whose binding property is implied by the above assumption. We transform his commitment scheme to a one-time signature scheme analogous to the scheme in [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] based on Pedersen commitments. The signature uses a commitment with an additional trapdoor. The public key is a commitment to 0 and a signature is a trapdoor opening of the commitment to the message.

We give a scheme with message space G n .

KeyGen ot Choose x r , y r , x s , y s , x t , y t , x 1 , y 1 , . . . , x n , y n , v, w ← Z p such that x r y s = x s y r . Define g i := g xi , h i =: g yi for i = r, s, t, 1, . . . , n, c = g v , d = g w . Let α, β, γ, δ s.t. . The public key is (c, d, g = (g r , g s , g t , g 1 , . . . , g n ), h = (h r , h s , h t , h 1 , . . . , h n ))

and the secret key is (α, β, γ, δ, x t , y t , x 1 , y 1 , . . . , x n , y n ). . Return (r = a α b β , s = a γ b δ , t). Verify ot A signature (r, s, t) is verified on (m 1 , . . . , m n ) by checking e(g r , r) e(g s , s) e(g t , t) e(g i , m i ) = e(c, g) e(h r , r) e(h s , s) e(h t , t) e(h i , m i ) = e(d, g) A signature produced by Sign ot is indeed accepted by Verify ot since: e(g r , r) e(g s , s) e(g t , t) e(g i , m i ) = e(g r , a α b β ) e(g s , a γ b δ ) e(g t , t) e(g i , m i ) = e(a αxr+γxs , g)e(b βxr+δxs , g) e(g t , t) e(g i , m i ) = e(a, g) e(g t , t) e(g i , m i ) = e(c t -xt m -xi i , g) e(g t , t) e(g i , m i ) = e(c, g)e(t -xt , g) e(g t , t) e(m -xi i , g)e(g i , m i ) = e(c, g) and similarly e(h r , r) e(h s , s) e(h t , t) e(h i , m i ) = e(h r , a α b β ) e(h s , a γ b δ ) e(h t , t) e(h i , m i ) = e(a αyr+γys , g)e(b βyr+δys , g) e(h t , t) e(h i , m i ) = e(b, g) e(h t , t) e(h i , m i ) = e(d, g)

2. 1

 1 SyntaxDefinition 1. A fair blind signature scheme is a 10-tuple (Setup, IKGen, UKGen, Sign, User, Ver, TrSig, TrId, ChkSig, ChkId) of (interactive) (probabilistic) polynomial-time Turing machines ((P)PTs):

Fig. 1 .

 1 Fig. 1. Security experiments for fair blind signatures

  is hard to output a new tuple (A, C, D, V, W ) that satisfies e(A, XC) = e(KV, G) e(C, H) = e(G, D) e(V, H) = e(G, W )

  Scheme 1 (Sig 1 ).Setup 1 Given (p, G, G T , e, G), choose additional generators H, K, T ∈ G.KeyGen 1 Choose sk = x ← Z p and set vk = G x .Sign 1 A signature on (M, N ) ∈ DH under public key G x , is defined asS 1 := (KT r M ) 1 x+d , S 2 := G d , S 3 := H d , S 4 := G r , S 5 := H r , for random d, r ← Z p Verify 1 (S 1 , S 2 , S 3 , S 4 , S5 ) is valid on (M, N ) ∈ DH under public key vk = X iff e(S 1 , XS 2 ) = e(KM, G) e(T, S 4 ) e(S 2 , H) = e(G, S 3 ) e(S 4 , H) = e(G, S 5 ) (3)

  Setup 3 (G) Given G = (p, G, G T , e, G), choose additional generators H, K, T ∈ G.KeyGen 3 (G) Choose sk = (x, , u) ← Z 3 p and set vk = (G x , G , G u ). Sign 3 ((x, , u), (M, N, Y, Z, V, W )) A signature on ((M, N ), (Y, Z), (V, W )) ∈ DH 3under public key G x , is defined as (for random d, r ← Z p )S 1 := (KT r M Y V u )1 x+d , S 2 := G d , S 3 := H d , S 4 := G r , S 5 := H r Verify 3 (S 1 , S 2 , S 3 , S 4 , S 5 ) is valid on messages (M, N ), (Y, Z), (V, W ) under a public key (X, L, U ) iff e(S 1 , XS 2 ) = e(KM, G) e(T, S 4 ) e(L, Y ) e(U, V ) e(S 2 , H) = e(G, S 3 ) e(S 4 , H) = e(G, S 5 ) (4)

  +ηv and check whether (A, C, D, R, S) is valid on (M, N ), (Y, Z), (V, W ) under ipk; (b) choose (vk ot , sk ot ) ← KeyGen ot and define Σ = Sign(y, vk ot ); (c) make commitments c A , c C , c D , c R , c S to A, C, D, R, S under ck; (d) run CEP(ck, epk, vk ot , •) on Y, Z and Σ (let ψ Y , ψ Z and ψ Σ denote the outputs); (e) make a proof φ Y that (Y, Z) ∈ DH and proofs φ S and φ Σ of validity of the signatures (A, C, D, R, S) and Σ;

  Sign ot To sign a message (m 1 , . . . , m n ) ∈ G n . Choose t ← G and set a := c t -xt m -xi i and b := d t -yt m -yi i

This variant was used during the French referendum on the European Constitution in May

In[START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] it is shown how to express a disjunction of two equation sets by a new set of equations.

The strong one-time signature scheme used in[START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF] works as follows: The verification key is a Pedersen commitment to 0. To sign a message, using the trapdoor, the commitment is opened to the message. By putting a second trapdoor in the commitment scheme, we can simulate one signing query and use a forger to break the binding property of the commitment scheme. In[START_REF] Groth | Homomorphic trapdoor commitments to group elements[END_REF], Groth proposes a scheme to commit to group elements. Using his scheme rather than Pedersen commitments, we can construct an efficient one-time signature scheme for group elements whose signatures consist of group elements (see Appendix A).

A simulation-sound non-interactive proof of knowledge of Q and W such that e(V , F ) = e(G, W ) and e(P, F ) = e(G, Q). (cf. §

5.2).5 The message space for Sig is the set of DH pairs w.r.t. (G, H ). Since all logarithms of vkot are known when picking a key, the user can complete the second components of the DH pairs.

Acknowledgments

This work was supported by the French ANR 07-TCOM-013-04 PACE Project, the European Commission through the IST Program under Contract ICT-2007-216646 ECRYPT II, and EADS.

Assuming STP, the signature is strongly unforgeable under a one-time chosen message attack. Let (g r , h r , g s , h s , g t , h t ) be an STP instance. If (g r , g s , h r , h s ) is a Diffie-Hellman (DH) tuple, (i.e., e(g r , h s ) = e(g s , h r )), we have an STP solution (g s , g -1 r , 1), since e(g r , g s )e(g s , g -1 r )e(g t , 1) = 1 and e(h r , g s )e(h s , g -1 r )e(h t , 1) = 1. If (g r , g s , h r , h s ) is not a DH-tuple, we choose ρ, σ, τ , ρ 1 , σ 1 , τ 1 , . . . , ρ n , σ n , τ n ← Z p and set g i := g ρi r g σi s g τi t , h i := h ρi r h σi s h τi t , for 1 ≤ i ≤ n; and c :=

Since (g r , g s ) and (h r , h s ) are "linearly independent", all these group elements look random. We give the adversary the public key (c, d, g, h). The signing query for (m 1 , . . . ,

and similarly e(h r , r) e(h s , s) e(h t , t) = e(d, g) e(h -1 i , m i ).

Thus (r, s, t) is a valid signature for (m 1 , . . . , m n ) and since τ and the τ i 's are perfectly hidden, this looks like a random signature produced by Sign ot . Suppose the adversary outputs (m 1 , . . . , m n , r , s , t ) = (m 1 , . . . , m n , r, s, t). Dividing the verification relation for each signatures yields:

If (m 1 , . . . , m n ) = (m 1 , . . . , m n ), then (r r -1 , s s -1 , t t -1 ) = (1, 1, 1) and these relations provide a solution to the STP problem. Otherwise, if we denote I ⊂ {1, . . . , n}, the set of indices for which m i = m i and n i := m i m -1 i , the probability that the adversary's output satisfies r i∈S n ρi i = r is upper-bounded by 1/p since the ρ i 's are perfectly hidden. Therefore if (m 1 , . . . , m n ) = (m 1 , . . . , m n ), we also obtain a solution to the STP problem with overwhelming probability.