Benoît Libert

Thomas Peters

Chen Qian

Logarithmic-Size Ring Signatures With Tight Security from the DDH Assumption

Keywords: Ring signatures, anonymity, tight security, random oracles

Ring signatures make it possible for a signer to anonymously and, yet, convincingly leak a secret by signing a message while concealing his identity within a flexibly chosen ring of users. Unlike group signatures, they do not involve any setup phase or tracing authority. Despite a lot of research efforts in more than 15 years, most of their realizations require linear-size signatures in the cardinality of the ring. In the random oracle model, two recent constructions decreased the signature length to be only logarithmic in the number N of ring members. On the downside, their suffer from rather loose reductions incurred by the use of the Forking Lemma. In this paper, we consider the problem of proving them tightly secure without affecting their space efficiency. Surprisingly, existing techniques for proving tight security in ordinary signature schemes do not trivially extend to the ring signature setting. We overcome these difficulties by combining the Groth-Kohlweiss Σ-protocol (Eurocrypt'15) with dualmode encryption schemes. Our main result is a fully tight construction based on the Decision Diffie-Hellman assumption in the random oracle model. By full tightness, we mean that the reduction's advantage is as large as the adversary's, up to a constant factor.

Introduction

As introduced by Rivest, Shamir and Tauman [START_REF] Rivest | How To Leak a Secret[END_REF], ring signatures make it possible for a signer to sign messages while hiding his identity within an ad hoc set of users, called a ring, that includes himself. To this end, the signer only needs to know the public keys of all ring members (besides his own secret key) in order to generate an anonymous signature on behalf of the entire ring. Unlike group signatures [START_REF] Chaum | Group Signatures[END_REF], ring signatures do not require any setup, coordination or registration phase and neither do they involve a tracing authority to de-anonymize signatures. Whoever has a public key can be appointed as a ring member without being asked for his agreement or even being aware of it. Moreover, signatures should ideally provide everlasting anonymity and carry no information as to which ring member created them. The main motivation of ring signatures is to enable the anonymous leakage of secrets, by concealing the identity of a source (e.g., a whistleblower in a political scandal) while simultaneously providing guarantees of its reliability.

In this paper, we consider the exact security of ring signatures in the random oracle model [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF]. So far, the only known solutions with logarithmic signature length [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF][START_REF] Libert | Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors[END_REF] suffered from loose reductions: the underlying hard problem could only be solved with a probability smaller than the adversary's advantage by a linear factor in the number of hash queries. Our main result is to give the first construction that simultaneously provides tight security -meaning that there is essentially no gap between the adversary's probability of success and the reduction's advantage in solving a hard problem -and logarithmic signature size in the number of ring members. In particular, the advantage of our reduction is not multiplicatively affected by the number Q H of random oracle queries nor the number of Q V of public verification keys in a ring.

Our Contribution. We describe the first logarithmic-size ring signatures with tight security proofs in the random oracle model. The unforgeability of our construction is proved under the standard Decision Diffie-Hellman (DDH) assumption in groups without a bilinear map while anonymity is achieved against unbounded adversaries. Our security proof eliminates both the linear gap in the number of random oracle queries and the Θ(Q V ) security loss. It thus features a fully tight reduction, meaning that -up to statistically negligible terms -the reduction's advantage as a DDH distinguisher is only smaller than the adversary's forging probability by a factor 2. To our knowledge, our scheme is the first ring signature for which such a fully tight reduction is reported. It is obtained by tweaking a construction due to Groth and Kohlweiss [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] and achieves tight security at the expense of increasing the number of scalars and group elements per signature by a small constant factor. For the same exact security, our reduction allows smaller key sizes which essentially decrease the signature length of [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] by a logarithmic factor n in the cardinality N of the ring and the time complexity by a factor ω(n 2 ). For rings of cardinality N = 2 6 , for example, our signatures can be 36 times faster to compute and 6 times shorter than [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF].

Our Techniques. Our scheme builds on the Groth-Kohlweiss proof system [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] that allows proving that one-out-of-N commitments opens to 0 with a communication complexity O(log N ). This proof system was shown to imply logarithmic-size ring signatures with perfect anonymity assuming that the underlying commitment scheme is perfectly hiding. At the heart of the protocol of [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] is a clever use of a Σ-protocol showing that a committed value is 0 or 1, which proceeds in the following way. In order to prove that a commitment C ∈ {C i } N -1 i=0 opens to 0 without revealing the index ∈ {0, . . . , N -1}, the n-bit indexes j of the binary representation 1 . . . n ∈ {0, 1} n of ∈ {0, . . . , N -1} are committed to and, for each of them, the prover uses the aforementioned Σ-protocol to prove that j ∈ {0, 1}. The response f j = a j + j x of the Σ-protocol is then viewed as a degree-one polynomial in the challenge x ∈ Z q and used to define polynomials

P i [Z] = n j=1 f j,ij = δ i, • Z n + n-1 k=0 p i,k • Z k ∀i ∈ [N ],
where f j,0 = f j and f f,1 = x -f j , which have degree n = log N if i = and degree n -1 otherwise. In order to prove that one of the polynomials {P i [Z]} N -1 i=0 has degree n without revealing which one, Groth and Kohlweiss [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] homomorphically compute the commitment

N -1 i=0 C Pi(x) i
and multiply it with

n-1 k=0 C -x k d k , for auxiliary homomorphic commitments {C d k = N -1 i=0 C p i,k i } n-1 k=0
, in order to cancel out the terms of degree 0 to n -1 in the exponent. Then, they prove that the product

N -1 i=0 C Pi(x) i • n-1 k=0 C -x k d k is indeed a commitment of 0.
The soundness of the proof relies on the Schwartz-Zippel lemma, which ensures that

N -1 i=0 C Pi(x) i • n-1 k=0 C -x k d k is unlikely to be a commitment to 0 if C is not.
As an application of their proof system, Groth and Kohlweiss [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] obtained logarithmic-size ring signatures from the discrete logarithm assumption in the random oracle model. While efficient and based on a standard assumption, their scheme suffers from a loose security reduction incurred by the use of the Forking Lemma [START_REF] Pointcheval | Security Proofs for Signature Schemes[END_REF]. In order to extract a discrete logarithm from a ring signature forger, the adversary has to be run n = log N times with the same random tape (where N is the ring cardinality), leading to a reduction with advantage ε

≈ ε n Q V •Q H ,
where Q H is the number of hash queries and Q V is the number of public keys. This means that, if we want to increase the key size so as to compensate for the concrete security gap, we need to multiply the security parameter by a factor n = log N , even without taking into account the factors Q H and Q V .

In our pursuit of a tight reduction, a first idea is to apply the lossy identification paradigm [START_REF] Katz | Efficiency improvements for signature schemes with tight security reductions[END_REF][START_REF] Abdalla | Tightly-Secure Signatures from Lossy Identification Schemes[END_REF] where the security proofs proceed by replacing a well-formed public key by a so-called lossy public key, with respect to which forging a signature becomes statistically impossible. In particular, the DDH-based instantiation of Katz and Wang [START_REF] Katz | Efficiency improvements for signature schemes with tight security reductions[END_REF] appears as an ideal candidate since, somewhat analogously to [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF], well-formed public keys can be seen as homomorphic Elgamal encryptions of 0. However, several difficulties arise when we try to adapt the techniques of [START_REF] Katz | Efficiency improvements for signature schemes with tight security reductions[END_REF][START_REF] Abdalla | Tightly-Secure Signatures from Lossy Identification Schemes[END_REF] to the ring signature setting.

The first one is that the Groth-Kohlweiss ring signatures [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] rely on perfectly hiding commitments in order to achieve unconditional anonymity whereas the Elgamal encryption scheme is a perfectly binding commitment. This fortunately leaves us the hope for computational anonymity if we trade the perfectly hiding commitments for Elgamal encryptions. A second difficulty is to determine which public keys should be replaced by lossy keys in the reduction. At each public key generation query, the reduction has to decide if the newly generated key will be lossy or injective. Replacing all public keys by lossy keys is not possible because of corruptions (indeed, lossy public keys have no underlying secret key) and the reduction does not know in advance which public keys will end up in the target ring R of the forgery. Only replacing a randomly chosen key by a lossy key does not work either: indeed, in the ring signature setting, having one lossy public key P K † in the target ring R does not prevent an unbounded adversary from using the secret key of a well-formed key P K ∈ R \ {P K † } to create a forgery. Moreover, as long as the reduction can only embed the challenge (injective or lossy) key in one output of the key generation oracle, it remains stuck with an advantage Θ(ε/Q V ) if the forger has advantage ε. Arguably, this bound is the best we can hope for by directly applying the lossy identification technique.

To obtain a fully tight reduction, we depart from the lossy identification paradigm [START_REF] Abdalla | Tightly-Secure Signatures from Lossy Identification Schemes[END_REF] in that, instead of tampering with one user's public keys at some step, our security proof embeds a DDH instance in the public parameters pp of the scheme. This allows the reduction to have all users' private keys at disposal and reveal them to the adversary upon request. In the real system, the set pp contains uniformly random group elements (g, h, g, h, U, V ) ∈ G 6 and each user's public key consists of a pair (X, Y ) = (g α • h β , gα • hβ ), where (α, β) ∈ Z 2 q is the secret key. The idea of the security proof is that, if (g, h, g, h) ∈ G 4 is not a Diffie-Hellman tuple, the public key P K = (X, Y ) uniquely determines (α, β) ∈ Z 2 q . In the case h = glog g (h) , the public key (X, Y ) is compatible with q equally likely pairs (α, β) since it only reveals the information log g (X) = α + log g (h) • β.

The reduction thus builds a DDH distinguisher by forcing the adversary's forgery to contain a committed encoding Γ = U α • V β of the signer's secret key (α, β) ∈ Z 2 q , which can be extracted using some trapdoor information. So long as (U, V ) is linearly independent of (g, h), the encoding Γ = U α • V β is independent of the adversary's view if (g, h, g, h) is a Diffie-Hellman tuple. In contrast, this encoding is uniquely determined by the public key if h = glog g (h) . This allows the reduction to infer that (g, h, g, h) is a Diffie-Hellman tuple whenever it extracts Γ = U α • V β from the adversary's forgery. To apply this argument, however, we need to make sure that signing queries do not leak any more information about (α, β) than the public key P K = (X, Y ) does. For this purpose, we resort to lossy encryption schemes [START_REF] Bellare | Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening[END_REF] (a.k.a. dual-mode encryption/commitments [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF][START_REF] Peikert | A Framework for Efficient and Composable Oblivious Transfer[END_REF]), which can either behave as perfectly hiding or perfectly binding commitments depending on the distribution of the public key. In each signature, we embed a lossy encryption (T 0 , T

1 ) = (g θ1 • h θ2 , U α • V β • H θ1 1 • H θ2 2 ) of Γ = U α • V β ,
which is computed using the DDH-based lossy encryption scheme of [START_REF] Bellare | Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening[END_REF]. If (H 1 , H 2 ) ∈ G 2 is linearly independent of (g, h), then (T 0 , T 1 ) perfectly hides Γ . At the same time, the reduction should be able to extract Γ from (T 0 , T 1 ) in the forgery. To combine these seemingly conflicting requirements, we derive (H 1 , H 2 ) from a (pseudo-)random oracle which is programmed to have (H 1 , H 2 ) = (g γ , h γ ), for some γ ∈ R Z q , in the adversary's forgery and maintain the uniformity of all pairs (H 1 , H 2 ) ∈ G 2 in all signing queries. By doing so, the witness indistinguishability of the Groth-Kohlweiss Σ-protocol [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] implies that the adversary only obtains a limited amount of information from uncorrupted users' private keys. While the above information theoretic argument is reminiscent of the security proof of Okamoto's identification scheme [START_REF] Okamoto | Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes[END_REF], our proof departs from [START_REF] Okamoto | Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes[END_REF] in that we do not rewind the adversary as it would not enable a tight reduction.

Related Work. The concept of ring signatures was coined by Rivest, Shamir and Tauman [START_REF] Rivest | How To Leak a Secret[END_REF] who gave constructions based on trapdoor functions and proved their security in the ideal cipher model. They also mentioned different realizations based on proofs of partial knowledge [START_REF] Cramer | Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[END_REF]. The latter approach was extended by Abe et al. [START_REF] Abe | 1-out-of-n Signatures from a Variety of Keys[END_REF] to support rings containing keys from different underlying signatures and assumptions. Bresson, Stern and Szydlo [START_REF] Bresson | Threshold Ring Signatures and Applications to Ad-hoc Groups[END_REF] modified the scheme of Rivest et al. [START_REF] Rivest | How To Leak a Secret[END_REF] so as to prove it secure in the random oracle model.

In 2006, Bender, Katz and Morselli [START_REF] Bender | Ring Signatures: Stronger Definitions, and Constructions Without Random Oracles[END_REF] provided rigorous security definitions and theoretical constructions without random oracles. In the standard model, the first efficient instantiations were put forth by Shacham and Waters [START_REF] Shacham | Efficient Ring Signatures Without Random Oracles[END_REF] in groups with a bilinear map. Brakerski and Tauman-Kalai [START_REF] Brakerski | A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model[END_REF] gave alternative constructions based on lattice assumptions. Meanwhile, Boyen [START_REF] Boyen | Mesh Signatures[END_REF] suggested a generalization of the primitive with standard-model instantiations.

The early realizations [START_REF] Rivest | How To Leak a Secret[END_REF][START_REF] Bresson | Threshold Ring Signatures and Applications to Ad-hoc Groups[END_REF] had linear size in the cardinality of the ring. Dodis et al. [START_REF] Dodis | Anonymous Identification in Ad Hoc Groups[END_REF] mentioned constant-size ring signatures as an application of their anonymous ad hoc identification protocols. However, their approach requires a setup phase where an RSA modulus is generated by some trusted entity. Chase and Lysyanskaya [START_REF] Chase | On Signatures of Knowledge[END_REF] suggested a similar construction of constant-size ring signatures from cryptographic accumulators [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Sinatures[END_REF]. However, efficiently instantiating their construction requires setup-free accumulators which are compatible with zero-knowledge proofs. The hash-based accumulators of [START_REF] Buldas | Accountable Certificate Management Using Undeniable Attestations[END_REF][START_REF] Camacho | Strong Accumulators from Collision-Resistant Hashing[END_REF] would not provide efficient solutions as they would incur proofs of knowledge of hash function pre-images. While the lattice-based construction of [START_REF] Libert | Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors[END_REF] relies on hash-based accumulators, its security proof is not tight and its efficiency is not competitive with discrete-logarithm-based techniques. Sander's number-theoretic accumulator [START_REF] Sander | Efficient Accumulators Without Trapdoor[END_REF] is an alternative candidate to instantiate [START_REF] Chase | On Signatures of Knowledge[END_REF] without a setup phase. However, it is not known to provide practical protocols: as observed in [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF], it would involve much larger composite integers than standard RSA moduli (besides zero-knowledge proofs for double discrete logarithms). Moreover, it is not clear how it would be compatible with tight security proofs.

Chandran, Groth and Sahai [START_REF] Chandran | Ring Signatures of Sub-linear Size Without Random Oracles[END_REF] gave sub-linear-size signatures in the standard model, which were recently improved in [START_REF] González | A Ring Signature of size O( 3 √ n) without Random Oracles[END_REF]. Assuming a common reference string, Malavolta and Schröder [START_REF] Malavolta | Efficient Ring Signatures in the Standard Model[END_REF] suggested a scheme with constant-size signatures. Their construction, however, relies on SNARKs (and thus non-falsifiable assumptions) to obtain a signature length independent of the number of ring members. In the random oracle model, Groth and Kohlweiss [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] described an elegant construction of logarithmic-size ring signatures based on the discrete logarithm assumption. Libert et al. [START_REF] Libert | Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors[END_REF] obtained logarithmic-size lattice-based ring signatures in the random oracle model.

The logarithmic-size ring signatures of [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF][START_REF] Bootle | Short Accountable Ring Signatures Based on DDH[END_REF][START_REF] Libert | Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors[END_REF] are obtained by applying the Fiat-Shamir heuristic [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] to interactive Σ-protocols. While these solutions admit security proofs under well-established assumptions in the random oracle model, their security reductions are pretty loose. In terms of exact security, they are doomed [START_REF] Paillier | Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log[END_REF] to lose a linear factor in the number Q H of random oracle queries as long as they rely on the Forking Lemma [START_REF] Pointcheval | Security Proofs for Signature Schemes[END_REF].

The exact security of digital signatures was first considered by Bellare and Rogaway [START_REF] Bellare | The Exact Security of Digital Signatures -How to Sign with RSA and Rabin[END_REF] and drew a lot of attention [START_REF] Coron | On the Exact Security of Full Domain Hash[END_REF][START_REF] Goh | A Signature Scheme as Secure as the Diffie-Hellman Problem[END_REF][START_REF] Katz | Efficiency improvements for signature schemes with tight security reductions[END_REF][START_REF] Abdalla | Tightly-Secure Signatures from Lossy Identification Schemes[END_REF][START_REF] Kakvi | Kiltz Optimal Security Proofs for Full Domain Hash, Revisited[END_REF] since then.

Background

2.1 Syntax and Security Definitions for Ring Signatures Definition 1. A ring signature scheme consists of a tuple of efficient algorithms (Par-Gen, Keygen, Sign, Verify) with the following specifications:

Par-Gen(1 λ ): Given a security parameter λ, outputs the public parameters pp. Keygen(pp): Given pp, outputs a key pair (P K, SK) for the user. Sign(pp, SK, R, M ): Given the user's secret key SK, a ring R and a message M , outputs the signature σ of the message M on behalf of the ring R. Verify(pp, M, R, σ): Given the message M , a ring R and a candidate signature σ, the verification algorithm outputs 0 or 1.

These algorithms must also verify the correctness, meaning that for all pp ← Par-Gen(1 λ ), (P K, SK) ← KeyGen(pp), for all M , and for all R such that P K ∈ R, we have w.h.p Verify(pp, M, R,

Sign(pp, SK, R, M )) = 1.
From a security point of view, Bender et al. [START_REF] Bender | Ring Signatures: Stronger Definitions, and Constructions Without Random Oracles[END_REF] suggested the following stringent definitions of anonymity and unforgeability. Definition 2. A ring signature (Par-Gen, Keygen, Sign, Verify) provides statistical anonymity under full key exposure if, for any computationally unbounded adversary A, there exists a negligible function ε(λ) such that

| Pr[pp ← Par-Gen(1 λ ); (M , i 0 , i 1 , R ) ← A Keygen(•) ; b R ← {0, 1}; σ ← Sign(pp, SK i b , R , M ) : A(σ ) = b] - 1 2 | < ε(λ),
where P K i0 , P K i1 ∈ R and Keygen is an oracle that generates a fresh key pair (P K, SK) ← Keygen(pp) at each query and returns both P K and SK to A.

Definition 3. A ring signature (Par-Gen, Keygen, Sign, Verify) provides unforgeability w.r.t insider corruption if, for any PPT adversary A, there exists a negligible function ε(λ) such that, for any pp ← Par-Gen(1 λ ), we have

Pr[(M, R, σ) ← A Keygen(•),Sign(•),Corrupt(•) (pp) : Verify(pp, M, R, σ) = 1] < ε(λ),
-Keygen(): is an oracle that maintains a counter j initialized to 0. At each query, it increments j, generates (P K j , SK j ) ← KeyGen(pp) and outputs

P K j . -Sign(i, M, R) is an oracle that returns σ ← Sign(pp, SK i , R, M ) if P K i ∈ R
and (P K i , SK i ) has been generated by Keygen. Otherwise, it returns ⊥. -Corrupt(i) returns SK i if (P K i , SK i ) was output by Keygen and ⊥ otherwise.

-A is restricted to output a triple (M, R, σ) such that: (i) No query of the form ( , M, R) has been made to Sign(•, •, •); (ii) R only contains public keys P K i produced by Keygen and for which i was never queried to Corrupt(•).

Hardness Assumptions

Definition 4. The Decision Diffie-Hellman (DDH) problem in G, is to distinguish the distributions (g a , g b , g ab ) and (g a , g b , g c ), with a, b, c R ← Z q . The DDH assumption is the intractability of the problem for any PPT distinguisher.

Reminders on Σ-Protocols

Definition 5 ([18]). Let a prover P and a verifier V, which are PPT algorithms, and a binary relation R. A protocol (P, V) is a Σ-protocol w.r.t. R, the challenge set C, the public input u and the private input w, if it satisfies the following:

-3-move form: The protocol is of the following form:

• P compute commitments {c i } j i=0 , where j ∈ N, and sends {c i } j i=0 to V. • The verifier V generates a random challenge x R ← C and sends c to P. • The prover P sends a response s to V.

• On input of a transcript ({c i } j i=0 , x, s), V outputs 1 or 0. -Completeness: If (u, w) ∈ R and the prover P honestly generates the transcript ({c i } j i=0 , x, s) for a random challenge x R ← C sent by V, there is a negligible function ε(λ) such that V accepts with probability 1 -ε(λ).

-2-Special soundness: There exists a PPT knowledge extractor E that, for any public input u, on input of two accepting transcripts ({c i } j i=0 , x, s) and ({c i } j i=0 , x , s ) with x = x , outputs a witness w such that (u, w ) ∈ R. -Special Honest Verifier Zero-Knowledge (SHVZK): There is a PPT simulator S that, given u and a random x ∈ C, outputs a simulated transcript ({c i } j i=0 , x, s ) which is computationally indistinguishable from a real one.

Σ-protocol

Showing that a Commitment Opens to 0 or 1

We recall the Σ-protocol used in [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] to prove that a commitment opens to 0 or

1. Let R = {(ck, c, (m, r)) | c = Com ck (m, r) ∧ (m, r) ∈ {0, 1} × Z q } the
binary relation, where ck is the commitment key generated for the underlying commitment scheme, u = c is the public input and w = (m, r) is the private input. Figure 1 gives us a Σ-protocol (P, V) for R.

Theorem 1 ([24, Theorem 2]). Let (Setup, Com) be a perfectly binding, computationally hiding, strongly binding and additively homomorphic commitment scheme. The Σ-protocol presented in figure 1 for the commitment to 0 or to 1 is perfectly complete, perfectly 2-special sound and perfectly SHVZK.

Σ-protocol for One-out-of-N Commitments Containing 0

Groth and Kohlweiss [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] used the Σ-protocol of Section 2.4 to build an efficient Σprotocol allowing to prove knowledge of an opening of one-out-of-N commitments {c i } N -1 i=0 to m = 0. Their protocol outperforms the standard OR-proof approach [START_REF] Cramer | Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols[END_REF] in that its communication complexity is only O(log N ), instead of O(N ). The idea is to see the responses f = mx + a of the basic Σ protocol as degree-1 polynomials in x ∈ Z q and exploit the homomorphism of the commitment.

Prover(ck, c; m, r) Verifier(ck, (c0, . . . , cN-1)) For j = 1, . . . , n rj, aj, sj, tj, ρj ← Zq, c j = Comck( j , rj) ca j = Comck(aj, sj), cb j = Comck(bj, tj)

Verifier(ck, c) a, s, t R ← Zq ca = Comck(a; s) cb = Comck(am; t) (ca,c b ) ----------------→ x ←---------------- x ← {0, 1} λ f = mx + a za = rx + s zb = r(x -f ) + t f,za,z b ----------------→ Accept if and only if ca, cb ∈ Cck, f, za, zb ∈ Zb, c x ca = Comck(f ; za), c x-f cb = Comck(0; zb)
with bj = j • aj cd j-1 = N -1 i=0 c p i,j-1 i
• Comck(0, ρj-1) with pi,k defined in (1)

{c j ,ca j ,c b j ,c d j-1 } n j=1 ------------------→ x ← ------------------ x R ← {0, 1} λ For j = 1, . . . , n fj = j x + aj, za j = rjx + sj zb j = rj(x -fj) + tj zd = rx n -n-1 k=0 ρkx k {f j ,za j ,z b j } n j=1 ,z d ------------------→
Accept if and only if {c j , ca j , cb j , cd j-1 } n j=1 ∈ Cck, {fj, za j , zb j } n j=1 , zd ∈ Zq For all j = 1, . . . , n c x j ca j = Comck(fj; za j ), c

f j -x j cb j = Comck(0; zb j ) N -1 i=0 c n j=1 f j,i j i • n-1 k=0 c -x k d k
= Comck(0; zd) with fj,1 = fj and fj,0 = x -fj Fig. 2: Σ-protocol for one of (c 0 , . . . , c N -1 ) commits to 0 Theorem 2 ([24, Theorem 3]). The Σ-protocol of figure 2 is perfectly complete. It is (perfectly) (n + 1)-special sound if the commitment is (perfectly) binding. It is (perfectly) SHVZK if the commitment scheme is (perfectly) hiding.

In Figure 2, for each i, p i,0 , . . . , p i,n-1 ∈ Z q are the coefficients of the polynomial

P i [Z] = n j=1 F j,ij [Z] = δ i, • Z n + n-1 k=0 p i,k • Z k ∀i ∈ {0, . . . , N -1} (1)
obtained by defining

F j,1 [Z] = j • Z + a j and F j,0 [Z] = Z -F j,1 [Z] for all j ∈ [n]
. Note that the equality (1) stems from the fact that, for each index i = i 1 . . . i n ∈ {0, . . . , N -1}, we have

F j,ij [Z] = δ ij , j • Z + (-1) δ0,i j • a j for all j ∈ [n]
, so that the coefficient of Z n in (1) is non-zero if and only if i = .

A Note on the Application to Ring Signatures

In [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF], Groth and Kohlweiss obtained a ring signature scheme by applying the Fiat-Shamir paradigm [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] to the above Σ-protocol. In short, key pairs are of the form (c, r) such that c = Com(0; r) and a ring signature associated with R = {c 0 , . . . , c N } is simply a proof that the signer knows how to open to 0 one of the N commitments in that ring. In [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF], the following theorem states about the security of the resulting construction, denoted (Setup, KGen, Sign, Vfy).

Theorem 3 ([24, Theorem 4]). The scheme (Setup, KGen, Sign, Vfy) is a ring signature scheme with perfect correctness. It has perfect anonymity if the commitment scheme is perfectly hiding. It is unforgeable in the random oracle model if the commitment scheme is perfectly hiding and computationally binding.

As the security of the ring signature relies on that of the Σ-protocol, it is interesting to take a closer look at the computation of commitments {C dj-1 } n j=1 in Figure 2. This part of the Σ-protocol is the only point where the ring signature generation may involve adversarially-generated values. In the anonymity game, the signer's public key may be one of the only two honestly-generated public keys in the ring R. The security proof of [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] argues that, as long as the commitment is perfectly hiding, the fact that each C dj-1 contains a (randomizing) factor Com(0; ρ j-1 ), for some uniformly random ρ j-1 , is sufficient to guarantee perfect anonymity. We point out an issue that arises when R = {c 0 , . . . , c N } contains maliciously generated keys outside the space of honestly generated commitments (even if they are perfectly hiding). In short, multiplying a maliciously generated commitment by a fresh commitment may not fully "clean-up" its distribution.

The following example is a perfectly hiding commitment where re-randomizing does not wipe out maliciously generated commitments components: the setup algorithm outputs generators ck = (g, h) cyclic group G of prime order q; committing to m ∈ Z q using randomness ρ = (r, s) R ← Z 2 q is achieved by computing Com ck (m; ρ) = (c 1 , c 2 , c 3 ) = (g m h r , g s , h s ) ∈ G 3 , which is a perfectly hiding commitment since c 1 is a Pedersen commitment and the Elgamal encryption (c 2 , c 3 ) of 0 is independent of c 1 . If we consider the maliciously generated commitment (c 1 , c 2 , c 3 ) = (h u , g v , g • h v ), multiplying it by any Com ck (0; ρ) does not bring it back in the range of Com. Therefore, in an instantiation with the above commitment, an unbounded adversary can defeat the anonymity property.

The only missing requirement on behalf of the underlying perfectly hiding commitment is that it should be possible to efficiently recognize elements in the range of the commitment algorithm. This assumption is quite natural and satisfied by schemes like Pedersen's commitment. Hence, this observation does not affect the perfect anonymity of the discrete-log-based instantiation of [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF].

A Fully Tight Construction from the DDH Assumption

We modify the scheme of [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] so as to prove its unforgeability via a fully tight reduction from the DDH assumption. The advantage of the DDH distinguisher is only smaller than the adversary's advantage by a (small) constant factor.

The price to pay for this fully tight reduction is relatively small since signatures are only longer than in [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] by roughly 2n group elements. Moreover, as in [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF], our signing algorithm requires Θ(N ) exponentiations if N is the size of the ring.

Description

We exploit the fact that, in the Σ-protocol of [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF], not all first-round messages should be computed using the same commitment scheme as the one used to compute the public key. The second step of the signing algorithm computes perfectly hiding commitments {C d k } n-1 k=0 which are vectors of dimension 4. They live in a different space than public keys (X, Y ) = (g α • h β , gα • hβ ), which are DDH-based lossy encryptions of (and thus perfectly hiding commitments to) 0.

The signer generates a commitment (T 0 , T

1 ) = (g θ1 • h θ2 , Γ • H θ1 1 • H θ2 2 ) to Γ = U α • V β , which encodes his secret key (α , β ) ∈ Z 2
q . This defines a vector V = (X , Y , T 0 , T 1 ) ∈ G 4 in the column space of a matrix M H ∈ G 4×4 , which has full rank in the scheme but not in the proof of unforgeability. Then, for each key X i = (X i , Y i ) in the ring R, the signer defines V i = (X i , Y i , T 0 , T 1 ) ∈ G 4 and, by extending the technique of [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF], generates a NIZK proof that one of the vectors {V i } N -1 i=0 is in the column span of M H . To prove this without revealing which V ∈ G 4 is used, the commitments {C dj-1 } n j=1 are re-randomized by multiplying them with a random vector in the column space of M H .

Par-Gen(1 λ ): Given a security parameter λ, choose a cyclic group G of prime order q with generators g, h, g, h R ← G and U, V R ← G. Choose hash functions H FS : {0, 1} * → Z q and H : {0, 1} * → G 2 which will be modeled as random oracles. Output the common public parameters pp = λ, G, g, h, g, h, U, V .

Keygen(pp):

Given pp, choose a secret key is SK = (α, β) R ← Z 2 q and compute the public key

P K = X = (X, Y ) = (g α • h β , gα • hβ ). Sign(pp, SK, R, M ): To sign M ∈ {0, 1} * on behalf of R = {X 0 , . . . , X N -1 } such that X i = (X i , Y i ) ∈ G 2 for each i ∈ [N ]
, the signer uses SK = (α, β) and P K = X = (X, Y ) = (g α • h β , gα • hβ ) ∈ R as follows. We assume that N = 2 n for some n. Let ∈ {0, . . . , N -1} the index of P K = X in R when R is arranged in lexicographical order and write it as = 1 . . . n ∈ {0, 1} n .

1. Choose θ 1 , θ 2 R ← Z q . For all j ∈ [n], choose a j , r j , s j , t j , u j , v j , w j , ρ j-1

R ← Z q and compute (T 0 , T 1 ) = g θ1 • h θ2 , U α • V β • H θ1 1 • H θ2 2 ,
as well as

C j = (C j ,0 , C j ,1 ) = g rj • h sj , g j • H rj 1 • H sj 2 C aj = (C aj ,0 , C aj ,1 ) = g tj • h uj , g aj • H tj 1 • H uj 2 (2)
C bj = (C bj ,0 , C bj ,1 ) = g vj • h wj , g j •aj • H vj 1 • H wj 2 , where (H 1 , H 2 ) = H M, R, T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 ∈ G 2 . Define M H =     g h 1 1 g h 1 1 1 1 g h U V H 1 H 2     ∈ G 4×4 (3)
and its corresponding discrete logarithms L h = log g (M H ) matrix

L h =     1 log g (h) 0 0 log g (g) log g ( h) 0 0 0 0 1 log g (h) log g (U ) log g (V ) log g (H 1 ) log g (H 2 )     ∈ Z 4×4 q . (4)
Note that the signer's witnesses (α,

β, θ 1 , θ 2 ) ∈ Z 4 q satisfy log g X | Y | T 0 | T 1 = L h • α | β | θ 1 | θ 2 . ( 5
)
In the following, we will sometimes re-write relation [START_REF] Bellare | The Exact Security of Digital Signatures -How to Sign with RSA and Rabin[END_REF] as

    X Y T 0 T 1     =     g h 1 1 g h 1 1 1 1 g h U V H 1 H 2         α β θ 1 θ 2     . ( 6
)
For each i ∈ [N ], define the vector

V i = (X i , Y i , T 0 , T 1 ) ∈ G 4 . The next step is to prove knowledge of witnesses (α , β , θ 1 , θ 2 ) ∈ Z 4 q such that V = (X , Y , T 0 , T 1 ) = g L h •(α ,β ,θ1,θ2) , for some ∈ [N ]. 2. For each j ∈ [n], pick ρ j-1,α , ρ j-1,β , ρ j-1,θ1 , ρ j-1,θ2 R ← Z q and compute C dj-1 = N -1 i=0 V pi,j-1 i • g L h •(ρj-1,α,ρ j-1,β ,ρ j-1,θ 1 ,ρ j-1,θ 2 ) ∈ G 4 , (7)
where, for each i ∈ {0, . . . , N -1}, p i,0 , . . . , p i,n-1 are the coefficients of

P i [Z] = n j=1 F j,ij [Z] = δ i, • Z n + n-1 k=0 p i,k • Z k ∈ Z q [Z], (8)
where 8) is non-zero if and only if i = .

F j,1 [Z] = j • Z + a j and F j,0 [Z] = Z -F j,1 [Z] for all j ∈ [n]. Note that the coefficient of Z n in (

Compute

x = H FS (M, R, T 0 , T 1 , {C j , C aj , C bj , C dj-1 } n j=1 ) ∈ Z q . 4. For each j ∈ [n], compute (modulo q) f j = j • x + a j = F j,1 (x) and z rj = r j • x + t j , zrj = r j • (x -f j ) + v j z sj = s j • x + u j , zsj = s j • (x -f j ) + w j and z d,α = α • x n - n-1 k=0 ρ k,α • x k , z d,β = β • x n - n-1 k=0 ρ k,β • x k z d,θ1 = θ 1 • x n - n-1 k=0 ρ k,θ1 • x k , z d,θ2 = θ 2 • x n - n-1 k=0 ρ k,θ2 • x k Let Σ j = C j , C aj , C bj , C dj-1 , f j , z rj , z sj , zrj , zsj for all j ∈ [n] and output σ = {Σ j } n j=1 , T 0 , T 1 , z d,α , z d,β , z d,θ1 , z d,θ2 . (9)
Verify(pp, M, R, σ): Given a ring R = {X 0 , . . . , X N -1 } and a pair (M, σ), parse σ as in ( 9) and define f j,1 = f j and f j,0 = x -f j for each j ∈

[n]. 1. Compute (H 1 , H 2 ) = H M, R, T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 ∈ G 2 and, for each public key X i = (X i , Y i ) ∈ G 2 in R, set V i = (X i , Y i , T 0 , T 1 ) ∈ G 4 . 2. Let x = H FS (M, R, T 0 , T 1 , {C j , C aj , C bj , C dj-1 } n j=1 ). If the equalities C aj • C x j = g zr j • h zs j , g fj • H zr j 1 • H zs j 2 , ( 10
)
C bj • C x-fj j = g zr j • h zs j , H zr j 1 • H zs j 2 , ∀j ∈ [n]
are not satisfied, return 0. Then, return 1 if and only if

N -1 i=0 V n j=1 fj,i j i • n j=1 C -(x j-1 ) dj-1 =     g h 1 1 g h 1 1 1 1 g h U V H 1 H 2         z d,α z d,β z d,θ1 z d,θ2     . (11)
Correctness is shown by observing from (8) that

N -1 i=0 V n j=1 fj,i j i equals N -1 i=0 V Pi(x) i = N -1 i=0 V δ i, •x n + n-1 k=0 p i,k •x k i = V x n • N -1 i=0 V n-1 k=0 p i,k •x k i = V x n • n-1 k=0 • N -1 i=0 V p i,k i x k = V x n • n-1 k=0 • C d k • g -L h •(ρ k,α ,ρ k,β ,ρ k,θ 1 ,ρ k,θ 2 ) x k ,
where the last equality follows from [START_REF] Bender | Ring Signatures: Stronger Definitions, and Constructions Without Random Oracles[END_REF]. Since V = g L h •(α ,β ,θ1,θ2) , we obtain

N -1 i=0 V n j=1 fj,i j i • n-1 k=0 •C -x k d k = V x n • n-1 k=0 g -L h •(ρ k,α ,ρ k,β ,ρ k,θ 1 ,ρ k,θ 2 ) (x k ) , = g L h •(z d,α ,z d,β ,z d,θ 1 ,z d,θ 2 ) .

Security Proofs

Statistical anonymity is achieved because {C dj-1 } n j=1 are uniformly distributed. The reason is that the matrices (4) have full rank in the scheme (but not in the proof of unforgeability), so that computing C dj-1 as per (7) makes its distribution uniform over G 4 .

Theorem 4. Any unbounded anonymity adversary A has advantage at most

Adv anon A (λ) ≤ 2 q + Q H FS q 2 ,
where Q H FS is the number of hash queries to H FS . The proof of Theorem 4 is given in Appendix B.1. Theorem 5. The scheme is unforgeable under the DDH assumption in the random oracle model. For any adversary A with running time t and making Q V queries to the key generation oracle, Q S signing queries as well as Q H and Q H FS queries to the random oracles H and H FS , respectively, there is a DDH distinguisher B with running time

t ≤ t + poly(λ, Q S , Q V , Q H ) and such that Adv euf-cma A (λ) ≤ 2 • Adv DDH B (λ) + Q S + Q H FS • (1 + log Q V ) + 5 q (12)
+ Q S • (Q H FS + 2Q H + 2Q S ) q 2 .
Proof. We use a sequence of games where, for each i, W i stands for the event that the challenger outputs 1 in Game i.

Game 0: This is the real game. At each query i ∈ [Q V ] to the key generation oracle Keygen(•), the challenger B honestly chooses α i , β i R ← Z q and returns the public key

P K i = X i = (X i , Y i ) = (g αi • h βi , gαi • hβi ) and retains SK i = (α i , β i ) for later use. If A subsequently submits X i = (X i , Y i ) to the corruption oracle, B reveals SK i = (α i , β i ).
Moreover, all signing queries are answered by faithfully running the signing algorithm. At the end of the game, A outputs a forgery (M , σ , R ), where R = {X 0 , . . . , X N -1 },

σ = {Σ j } n j=1 , T 0 , T 1 , z d,α , z d,β , z d,θ1 , z d,θ2 , (13)
with Σ j = C j , C aj , C bj , C dj-1 , f j , z rj , z sj , z rj , z sj . At this point, B outputs 1 if and only if A wins, meaning that: (i) σ correctly verifies; (ii) R only contains uncorrupted public keys; (iii) No signing query involved a tuple of the form (•, M , R ) . By definition, we have Adv euf-cma

A (λ) = Pr[W 0 ].
Game 1: This game is like Game 0 but we modify the signing oracle. Note that each signing query triggers a query to the random oracle H(.) since the challenger B has to faithfully compute T 0 and {C j ,0 , C aj ,0 , C bj ,0 } n j=1 before obtaining H M, R, T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 . In Game 1, at each signing query, B aborts in the event that H(•) was already defined for the input M, R, T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 . Since such an input contains uniformly random elements, the probability to abort during the entire game is at most

Q S • (Q S + Q H )/q 2 and we have | Pr[W 1 ] -Pr[W 0 ]| ≤ Q S • (Q S + Q H )/q 2 .
Game 2: We modify the random oracle H when it is directly invoked by A (i.e., H-queries triggered by signing queries are treated as in Game 0). At each H-query M, R, T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 , the challenger B returns the previously defined value if it exists. Otherwise, it picks γ R ← Z q and defines the hash value as (H 1 , H 2 ) = H M, R, T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 = (g γ , h γ ).

Note that H(•) is no longer a truly random oracle since (g, h, H 1 , H 2 ) is a Diffie-Hellman tuple. Still, under the DDH assumption, this modification has no noticeable effect on A's winning probability. Lemma 1 describes a DDH distinguisher such that

| Pr[W 2 ] -Pr[W 1 ]| ≤ Adv DDH B (λ) + 1/q.
Since (g, h, H 1 , H 2 ) is a Diffie-Hellman tuple in Game 2, γ ∈ Z q can be used as a decryption key for the DDH-based dual-mode encryption scheme. Another consequence of the last transition is that the matrix L h of (3) has no longer full rank since its last row is linearly dependent with the first three rows.

Game 3: We introduce a failure event F 3 which causes the challenger B to output 0. When A outputs its forgery σ , B parses σ as in [START_REF] Camacho | Strong Accumulators from Collision-Resistant Hashing[END_REF] and computes

(H 1 , H 2 ) = H M , R , T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 .
Event F 3 is defined to be the event that either: (1) The hash value (H 1 , H 2 ) was not defined at any time; (2) It was defined but collides with a pair (H 1 , H 2 ) = H M, R, T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 defined in response to a signing query ( , M, R) for some index ∈ {0, . . . , |R| -1}, when R is arranged in lexicographic order. Note that the probability of case (1) cannot exceed 1/q because H(•) is unpredictable as a random oracle. Moreover, since a winning adversary must forge a signature on some (M , R ) that has never been queried for signature, the probability of case ( 2) is bounded by Q S /q 2 multiplied by Q H since we must consider the probability that a tuple (g, h, H 1 , H 2 ) defined in a signing query is accidentally a Diffie-Hellman tuple and collides with the response of a hash query. We find

| Pr[W 3 ] -Pr[W 2 ]| ≤ Pr[F 3 ] ≤ 1/q + Q S • Q H /q 2 .
Game 4: This game is identical to Game 3 with one modification. When the adversary A outputs its forgery σ , B parses σ as in [START_REF] Camacho | Strong Accumulators from Collision-Resistant Hashing[END_REF] and computes (H 1 , H 2 ) = H M , R , T 0 , {C j ,0 , C aj ,0 , C bj ,0 } n j=1 . Then, B recalls the previously defined exponent γ ∈ Z q such that (H 1 , H 2 ) = (g γ , h γ ) and uses it to decrypt the dual-mode ciphertexts {C j } n j=1 . It aborts and outputs 0 if one of these ciphertexts turns out not to encrypt a bit j ∈ {0, 1}. Note that, if B does not abort, it decodes an n-bit string = 1 . . . n ∈ {0, 1} n from {C j } n j=1 . We claim that we have

| Pr[W 4 ] -Pr[W 3 ]| ≤ (1 + Q H FS )/q.
The only situation where Game 4 deviates from Game 3 is the event F 4 that either: (i) A did not query H FS (•) on the input that the forgery relates to; (ii) A manages to break the soundness of the proof system showing that each of the ciphertexts {C j } n j=1 encrypts a bit. Lemma 2 shows that Pr

[F 4 ] ≤ (1 + Q H FS )/q.
Game 5: In this game, we modify the challenger's behavior when A outputs a forgery σ . Having decoded the n-bit string = 1 . . . n ∈ {0, 1} n from the dual-mode ciphertexts {C j } n j=1 , B also runs the decryption algorithm for (T 0 , T 1 ) to compute Γ = T 1 /T 0 γ . At this point, B recalls the secret key SK = (α , β ) of the -th member of the ring R = {X 0 , . . .

X N -1 } in lexicographical order. If Γ = U α • V β , B outputs 1. Otherwise, it outputs 0. Lemma 3 shows that | Pr[W 5 ] -Pr[W 4 ]| ≤ Q H FS • log(Q V )/q.
Game 6: This game is identical to Game 5 except that we change the distribution of pp = λ, G, g, h, g, h, U, V . Here, instead of choosing g, h, g, h R ← G uniformly, we set (g, h, g, h) = (g, h, g ρ , h ρ ) for a randomly chosen ρ R ← Z q . Clearly, the two distributions of pp are indistinguishable under the DDH assumption and B can immediately be turned into an efficient DDH distinguisher (the proof is straightforward

) such that | Pr[W 6 ] -Pr[W 5 ]| ≤ Adv DDH B (λ).
Game 7: This game is like Game 6 except that we now simulate the proof of knowledge of secret keys in all outputs of the signing oracle. On a signing query (M, R, ), where (0 ≤ ≤ |R| -1), the challenger parses R as {X 0 , . . . , X N -1 } and returns ⊥ if X is not public keys produced by the Keygen(.) oracle. Otherwise, the challenger chooses x R ← Z q as well as z d,α , z d,β , z d,θ1 , z d,θ2 R ← Z q and f j , z rj , z sj , zrj , zsj R ← Z q , for all j ∈ [n]. Then, it picks T 0 R ← G as well as r j , s j R ← Z q for all j ∈ [n], and honestly computes C j ,0 = g rj • h sj for all j ∈ [n]. It can now compute for all j ∈ [n],

C aj ,0 = g zr j • h zs j • C -x j ,0 , C bj ,0 = g zr j • h zs j • C fj -x j ,0 ,
and define (H 1 , H 2 ) = H(M, R, T 0 , {(C j ,0 , C aj ,0 , C bj ,0 )} n j=1 ). Then, it completes the computation of dual-mode commitments as follows. First, it chooses

T 1 R ← G and computes C j ,1 = g j • H rj 1 • H sj 2 for all j ∈ [n]. Then, it computes C aj ,1 = g fj • H zr j 1 • H zs j 2 • C -x j ,1 , C bj ,1 = H zr j 1 • H zs j 2 • C fj -x j ,1 ,
for all j ∈ [n]. Then, for each j ∈ {2, . . . , n}, the challenger faithfully computes C dj-1 as per [START_REF] Bender | Ring Signatures: Stronger Definitions, and Constructions Without Random Oracles[END_REF] but, for index j = 1, it computes

C d0 = N -1 i=0 V n j=1 fj,i j i n j=2 C -(x j-1 ) dj-1 M H (-z d,α , -z d,β , -z d,θ1 , -z d,θ2 ) ,
where V i = (X i , Y i , T 0 , T 1 ) , f j,1 = f j and f j,0 = x -f j for each j ∈ [n]. Finally, the challenger B programs the random oracle H FS to have the equality x = H FS (M, R, T 0 , T 1 , {C j , C aj , C bj , C dj-1 } n j=1 ). If H FS was already defined for this input, B aborts and outputs 0. If the simulation does not fail, the oracle sets Σ j = C j , C aj , C bj , C dj-1 , f j , z rj , z sj , zrj , zsj for all j ∈ [n] and outputs the signature σ

= {Σ j } n j=1 , T 0 , T 1 , z d,α , z d,β , z d,θ1 , z d,θ2
, which is distributed exactly as in Game 6 unless (g, h, H 1 , H 2 ) happens to form a Diffie-Hellman tuple. Indeed, although the adversary's signing queries may involve rings R that contain maliciously generated keys of the form

X i = (X i , Y i ) = (X i , Ω i • X log g (g) i
), with Ω i = 1 G , this does not prevent the simulated commitments {C dj-1 } n j=1 from having the same distribution as in Game 6. In simulated signatures, we indeed have

C dj-1 = N -1 i=0 V pi,j-1 i • g L h •ρj ∀j ∈ {2, . . . , n -1}
for random ρ 2 , . . . , ρ n-1 ∈ R Z 4 q , where p i,0 , . . . , p i,n-1 are the coefficients of

n j=1 f j,ij = δ i, x n + n j=1 p i,j-1 x j-1 . Since V = g L h •(α ,β ,θ1,θ2) and defining ρ 1 = -(z d,α , z d,β , z d,θ1 , z d,θ1 ) - n j=2 ρ j x j-1 + (α , β , θ 1 , θ 2 ) • x n , we have C d0 = V x n • N -1 i=0 V n j=1 pi,j-1x j-1 i • N -1 i=0 V -n j=2 pi,j-1x j-1 i •g -L h •(z d,α ,z d,β ,z d,θ 1 ,z d,θ 1 ) -L h • n j=2 ρj x j-1 = N -1 i=0 V pi,0 i • g L h •ρ1
Note that the Fiat-Shamir proof does not hide which index ∈ {0, 1} n the signing oracle uses (and it does not have to since A knows ): indeed, for any signing query, the matrix L h has only rank 3 and X may be the only key of the ring R to be in the column span of M H . However, the same holds in Game 6. As long as the simulation does not fail because of a collision on H FS or because (H 1 , H 2 ) accidentally lands in the span of (g, h) at some signing query, the simulated proof is perfectly indistinguishable from a real proof that would be generated as in Game 6. Taking into account the probability that the signing oracle fails at some query, we obtain the inequality

| Pr[W 7 ] -Pr[W 6 ]| ≤ Q S /q + Q S • (Q H FS + Q S )/q 2 .
In Game 7, we claim that Pr[W 7 ] = 2/q. To prove this claim, we recall that B only outputs 1 if (T 0 , T 1 ) decrypts to Γ = U α • V β . We next argue that, except with probability 1/q, Γ is independent of A's view in Game 7.

Indeed, since (g, h, g, h) is a Diffie-Hellman tuple, the only information that X = (X , Y ) = (g α • h β , gα • hβ ) reveals about (α , β ) ∈ Z 2 q is log g (X ) = α +log g (h)•β since log g (Y ) only provides redundant information. Also, in all outputs of the signing oracle, the pair (T 0 , T 1 ) R ← G 2 is chosen independently of U α • V α . Finally, in Game 7, all signing queries are answered by simulating a NIZK proof without using the witnesses SK = (α , β ) ∈ Z 2 q at any time. This ensures that no information is leaked about (α , β ) whatsoever.

Taking into account the event that (U, V ) accidentally falls in the span of (g, h), we find that Γ remains independent of A's view until the forgery stage. In this case, (T 0 , T 1 ) only decrypts to U α • V β with probability 1/q, which implies Pr[W 7 ] = 2/q. When counting probabilities, we obtain the bound (12). Lemma 1. There exists an efficient DDH distinguisher B that bridges between Game 1 and Game 2 and such that | Pr

[W 2 ] -Pr[W 1 ]| ≤ Adv DDH B (λ) + 1/q.
Proof. We consider a DDH instance (g, g a , g b , g ab+c ) for which B has to decide if c = 0 or c ∈ R Z q . To do this, B initially defines h = g b and emulates the random oracle H(•) at each (direct) query by randomly choosing δ

1 , δ 2 R ← Z q and setting (H 1 , H 2 ) = (g a ) δ1 • g δ2 , (g ab+c ) δ1 • (g b ) δ2 = g aδ1+δ2 , g (aδ1+δ2)b+cδ1 . If c = 0, (H 1 , H 2 ) is distributed as in Game 2 for γ = aδ 1 + δ 2 . If c ∈ R Z q ,
we have c = 0 with probability 1 -1/q, so that (H 1 , H 2 ) are uniform over G 2 and independently distributed across distinct queries, exactly as in Game 1. When A halts, B outputs 1 if A creates a valid forgery and 0 otherwise. Lemma 2. From Game 3 to Game 4, the adversary's winning probabilities differ by at most | Pr

[W 4 ] -Pr[W 3 ]| ≤ (1 + Q H FS )/q.
Proof. We bound the probability Pr[F 4 ]. Recall that F 4 occurs if A breaks the soundness of the proof that a dual-mode ciphertext encrypts a bit. This implies that σ = {Σ j } n j=1 , T 0 , T

that C k encrypts k ∈ {0, 1}. This proof, which is obtained from the Σ-protocol of [24, Figure 1], is known [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF]Theorem 2] to provide special soundness with soundness error 1/q. Hence, if the statement is false and C k does not encrypt a bit, for any given pair (C a k , C b k ), only one challenge value x ∈ Z q admits a response (f k , z r k , z s k , z r k , z s k ) that makes ( 14) into an accepting transcript.

At each query H FS (M, R, T 0 , T 1 , {C j , C aj , C bj , C dj-1 } n j=1 ) such that one of the {C j } j=1 does not encrypt a binary value, the probability that oracle H FS (•) returns the unique "bad" x ∈ Z q for which a correct response exists is exactly 1/q. Finally, since H FS is simulated by the challenger B, we may assume that B makes the query H FS (M , R , T 0 , T 1 , {C Proof. The only situation where Game 5 differs from Game 4 is the event F 5 that extracting {C j } n j=1 leads to a string ∈ {0, 1} n but (T 0 , T 1 ) does not decrypt to an encoding U α • V β of the -th ring member's secret key. This implies that V = (X , Y , T 0 , T 1 ) is not in the column space of M H (as defined in (3)) and we show that this event can only happen with probability Q H FS • n/q ≤ Q H FS • log(Q V )/q, where n = log N .

Note that [START_REF] Brakerski | A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model[END_REF] implies that f j equals f j = a j + j • x for all j ∈ [n], where a j ∈ Z q is encrypted by C aj . Defining f j,1 = f j and f j,0 = x -f j , we know that

n j=1 f j,ij = δ i, • x n + n-1 k=0 p i,k • x k ∀i ∈ [N ],
for some p i,0 , . . . , p i,n-1 ∈ Z q . This implies

N -1 i=0 V n j=1 f j,i j i = N -1 i=0 V δ i, •x n + n-1 k=0 p i,k •x k i = V x n • N -1 i=0 V n-1 k=0 p i,k •x k i = V x n • n-1 k=0 • N -1 i=0 V p i,k i x k .
Moreover, the last verification equation ( 11) implies

V x n • n-1 k=0 • N -1 i=0 V p i,k i x k • n-1 k=0 C -(x k ) d k = g L h •(z d,α ,z d,β ,z d,θ 1 ,z d,θ 2 ) . (15)
By taking the discrete logarithms log g (•) of both members of (15), we get Since L h has rank at most 3 due to the modification introduced in Game 2 and Game 3, assuming that v = log g (V ) ∈ Z 4 q is not in the column space of L h , there exists a non-zero vector t ∈ Z 4 q such that t • L h = 0 1×4 and t • v = 0. If we multiply both members of ( 16) on the left by t , we obtain

x n • v + N -1
x n • (t • v ) + N -1 i=0 n-1 k=0 (p i,k • x k ) • (t • v i ) - n-1 k=0 x k • (t • c d k ) = 0. ( 17
)
If t • v = 0, equality [START_REF] Coron | On the Exact Security of Full Domain Hash[END_REF] implies that x is a root of a non-zero polynomial of degree n. However, x is uniformly distributed over Z q and the Schwartz-Zippel Lemma implies that (17) can only hold with probability n/q < log(Q V )/q. In order to bound the probability Pr[F 5 ], we have to consider all hash queries H F S (M, R, T 0 , T 1 , {C j , C aj , C bj , C dj-1 } n j=1 ) for which R only contains honestly generated keys and (T 0 , T 1 ) does not decrypt to an encoding U α • V β of the -th key of R, where ∈ {0, . . . , |R| -1} is determined by {C j } n j=1 . Taking a union bound over all hash queries, we obtain Pr[F 5 ] ≤ Q H FS • log(Q V )/q.

Fig. 1 :

 1 Fig. 1: Σ-protocol for commitment to m ∈ {0, 1}

  j , C aj , C bj , C dj-1 } n j=1 ) for itself in case it was not explicitly made by the time A terminates. Taking a union bound over all H FS -queries, we obtain | Pr[W 4 ] -Pr[W 3 ]| ≤ Pr[F 4 ] ≤ (1 + Q H FS )/q. Lemma 3. From Game 4 to Game 5, the adversary's winning probabilities differ by at most | Pr[W 5 ] -Pr[W 4 ]| ≤ Q H FS • log(Q V )/q. (The proof is Appendix B.2.) B.2 Proof of Lemma 3

i=0 n- 1 k=0(

 1 p i,k x k ) • v i -n-1 k=0 x k • c d k = L h • (z d,α , z d,β , z d,θ1 , z d,θ2) .[START_REF] Chaum | Group Signatures[END_REF]

  1 , z d,α , z d,β , z d,θ1 , z d,θ2 verifies and there exists k∈ [n] such that Σ k = (C k , C a k , C b k , C d k-1 , f k , z r k , z s k , z r k , z s k ) contains a ciphertext C k that decrypts to k ∈ {0, 1}. For this index k, σ contains a NIZK proof (C a k , C b k ), x, (f k , z r k , z s k , z r k , z s k )

Acknowledgements

This work was funded in part by the French ANR ALAMBIC project (ANR-16-CE39-0006).

A Reminders on Commitment Schemes

A non-interactive commitment scheme allows a sender to commit to a message m by sending a commitment string to the receiver. Later on the sender can convince the receiver that the committed value was really m. A commitment scheme must satisfy two security properties called hiding and binding. The former captures that the commitment hides any partial information about the message. The latter requires that the sender be unable to open the commitment to two distinct messages. Formally, a non-interactive commitment scheme is a pair of PPT algorithms (Setup, Com). The setup algorithm ck ← Setup(1 λ ) generates a commitment key ck, which specifies a message space M ck , a randomness space R ck and a commitment space C ck . The commitment algorithm Com defines a function Com ck :

It is perfectly binding if any element of the commitment space C ck uniquely determines the message. Groth and Kohlweiss [START_REF] Groth | One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin[END_REF] use the following additional properties. Definition 6. A commitment scheme (Setup, Com) is strongly binding if, for any PPT adversary A, there exists a negligible function ε(λ) such that

We consider a prime q > 2 λ specified in the commitment key ck. The message space and the randomness space are both

B Deferred Proofs for the Fully Tight Construction

B.1 Proof of Theorem 4

Proof. We consider a sequence of games and, for each i, we call W i the event that the challenger outputs 1 in Game i, meaning that the adversary successfully guesses the challenger's bit and outputs b = b. In each game, we also consider the event E i by which the tuple (g, h, g, h) of the public parameter or the tuple (g, h, H 1 , H 2 ) defined in the challenge signature forms a Diffie-Hellman tuple.

Game 0: This is the real game where the challenger outputs 1 if and only if A wins. By definition, A's advantage is Adv anon

. We assume that, for all public keys generated by the Keygen(.) oracle, the adversary immediately obtains the secret keys. Since (g, h) is uniformly distributed in pp and since (H 1 , H 2 ) is an independent random output of the random oracle H, we find Pr[E 0 ] = 2/q -1/q 2 and then Pr[W 0 ] ≤ Pr[W 0 |¬E 0 ] + (2/q -1/q 2 ). We are left with bounding Pr[W 0 |¬E 0 ]. Game 1: We modify the generation of the challenge signature. On a challenge query (M, R, (0) , (1) ), where (0 ≤ (0) , (1) ≤ |R|-1), the challenger B parses R as {X 0 , . . . , X N -1 } and returns ⊥ if X (0) and X (1) are not public keys produced by the Keygen(.) oracle. Otherwise, it flips a coin b R ← {0, 1} and sets ( 1 , . . . , n ) as the bit representation of (b) . Then, it chooses x R ← Z q as well as

so as to define (H 1 , H 2 ) = H(M, R, T 0 , {(C j ,0 , C aj ,0 , C bj ,0 )} n j=1 ). Then, B completes the computation of the dual-mode commitments as follows. First, it picks

It draws C dj-1 R ← G for each j ∈ {2, . . . , n} while, for j = 1, it computes

where V i = (X i , Y i , T 0 , T 1 ) , f j,1 = f j and f j,0 = x -f j for each j ∈ [n]. Finally, the challenger programs the random oracle H FS to have the equality x = H FS (M, R, T 0 , T 1 , {C j , C aj , C bj , C dj-1 } n j=1 ). If H FS was already defined for this input, the challenger aborts and picks b as a random bit. If the simulation does not fail, the oracle outputs the challenge signature σ = {Σ j } n j=1 , T 0 , T 1 , z d,α , z d,β , z d,θ1 , z d,θ2 , which is distributed exactly as in W 0 |¬E 0 , assuming that E 1 does not occur. Indeed, if (g, h, H 1 , H 2 ) is not a Diffie-Hellman tuple in both games, all the dual-mode commitments are perfectly hiding and if (g, h, g, h) is not a Diffie-Hellman tuple as well, the matrix M H has full rank, meaning that {C dj-1 } n j=1 are uniformly distributed over G 4 . Therefore, as long as no collision occurs in the simulation of the challenge, A's view in W 1 |¬E 1 is the same as in W 0 |¬E 0 . If we call F 1 the event that a hash collision prevents the correct generation of the challenge signature, we obtain the inequality

In Game 1, when neither E 1 nor F 1 occurs, the signature is perfectly independent of b ∈ R {0, 1}, so that Pr[W 1 |¬(E 1 ∪ F 1 )] = 1/2. All the above observations together thus implies Adv anon A (λ) ≤ 2/q + (Q H FS -1)/q 2 .


A Bidaùd
email: bidaud@lpsc.in2p3.li

S Mima

J Despres

D Hcucr

P Criquix

B Champel

N Hadjsaid

't,

THE VALUE OF LOAD FOLLOWING CAPACITY: WILL INCREASING RENEWABLE SHARE IN EUROPE'S ELECTRICITY REDUCE NUCLEAR REACTORS' CAPACITY OR LOA.D FACTORS ?

Nuclear energy cost sttuclute mal¡es it a base load lechnolog),. h1 the cases v,here varíable renetyable p|oductiotl has a higher pt iot it)¡ oü tlte grid, renewable lechtlologies x,ill reduce load factors of dispatchable Íecl1¡nlogies. A not able to [ollo.,t, ì'esidual load, nuclear reaclors could be supplat?ted b), nþrc Ûex¡ble lechnologies. ht lhis paper, \ÿe slud! Í|rc disì'ega ed load following capacity of nuclear rcactot's fo| the nucleûr itldustt)r in leÌ tits ol pt'eserýed ûo¡'ket share.

The honly \tat'ialiotls of Variable Reney,able productir¡n is olmosl Ìrcver sitnulaled ih \he same tool as the decade long linrc scale ol inrrestment ¡t1 nuclear capacilÿ. We use the coupling of POLES (Prospective Outlook for Long Tetnt Energl, Supplý and EUCAD (European Unit ConnÌilnrcnl and D¡spatch) for the dynantic s¡nuletion of coupled supply and demand of enet'Ð,, re'oro'ces and poýrer ntatkels al lhese ÿery dfle¡'eizt tinescales. We pt esent studies of tlle evolution oJ the nuclear Ieet and its load Jactors as a finlcÍion of sone ke), factots such as load followirtg capacities, aÿ.1il.ibility of othet techtiologíes (renev,able sharcs, storage capacit¡es carhon sequeslrcliok opfions), carbon rcduclion policies.

I. INTRODUCTION

Given thc importancc of invcstmcnt cost and thc limitcd cost of its fucl, nuclear power ma¡ginal cost is very low. This makcs nucloa¡ power a base load tcchnology that has limited oconomic ìncentive to ¡educe its production when electricjty prices fall. Daily elcctricity prices in ErÌropc arc now cleârly dependcnt on PV production (with low prices not only at night but also by noon) and on wind po!ÿcr production. Even negative priccs are seen dúring period of reduccd demand and high Ýind. This and the highcr prio¡iry to access thc grid oi rcnewable rcdllcc thc production of controllable power plant, in particular fossil ones. With thc increasing share of renewablc cxpccted jn the future, thc load lacto¡s of controllablc production, aúong which nuclear, will continuc to decrease. And so lvill thei¡ revenues if no o¡ limited development of capacity markets is sct up to compensâte for thc scrvjccs of grid security. Thc actuaÌ market for basc load electricìty, where nucìear compctitivcness is expected to bc the highest may completely disappear. Nùclear cnergy might bc fo¡ccd whether to phase out or to adapt itself and to demonstratc its âbility follow load and p¡jce variations.

NLÌclear reactors have a larger load lollowing câpacity than usualLy saidr, even if technical difficultjcs (Xe effect, fuel constraints, thcrmal fatiguc ctc...) can limit it. Because of thc very high contribution of nuclea¡ power in thc Frcnch energy mix, this capacjty is al¡eady and will probably be even more uscd in the future in France. To simulate the evolution ol the power system on the long te¡rn with a high lcvcl of va¡iable renewablc production and sorne sto¡âge tech¡ologies, onc noeds to simulate both thc sho¡t time period at whjch demand and renewablc productions change (rypjcally hours) and longcr ones, such as thosc of investment life timcs (typically many ycars). This is exactly what can be done with thc combined use of EUCAD'? (European Unir Commitment and Dispatch) and POLEST (Prospectivo Outlook for Long term Encrgy Supply).

In this paper we propose to simuiate the evolution of the nuclear fleets and thcir load factors as a function of some key factors such as the availability of othe¡ technologies (carbon captùre and storage, power storage), as load following capacities, and as a ftÌnction of carbon reduction poJìcies. we focus o¡ thc European and Frcnch cases for which nìrclear sharc is highcr and for which the impact of new renewablc share should be secn fì¡st.

I. COUPLING POLES AND EUCAD

POLES is a partial cquìlibriùm energy markct prospcctjve tool. Thc model simulates the energy dcmand and the sÙpply of45 count¡ies and l2 regions in the world orl a yearly basis up to 2100. lt covcrs 15 sectors of cnergy demarld (primary industries, transportation systems, residential and scrvices), forty technologies of elect¡ical prodrìction and hydrogen.

The choice of investment between technologies is made in order to optimize the ene¡getic ûix according to physical (capacity installâble, aÿailability. .. ) and cconomical parameteÍs (production costs of eìectricity...).

On the base of POLES, yearly power p¡oduction capacities and demand projectiors, the actual utilization factors of capâcities are calculatcd whether with a simpììfìed optimization algo¡ithm in POLES or in a specific external module called EUCAD in the case of Europe.

EUCAD minìmizes thr¿ totai variable costs of electricity of rhe interconnected Eu¡opean markets. It takes into account thc daìly va¡iability of re¡ewable prodìrctions by applying its optirnization algorithm on hvelve days (6 of The economic and technical specificities (costs, efficiencies, fuel consumptions.. . ) of all techûologies whethe¡ ofdemand or production sides are provided by an economic cost database called TECHPOL. It shoùld be noted that jn POLES, eâch technology's cost follows a leaming cune thât starts fÌom the costs of "Fi¡st of a Kind" and decreases with their devclopment. For some of them, a "floor" cost is described so that \¡/hatever the developmcnt of the technology, its cost cannot decrease indefinitely. This evolution is cvaluated on the advice of the experts and reflects the impact of the effofs invested in thc R & D on the profitâbility ofthe rechnologyl.

Profiles for supply ol oil and gases are projected fo¡ key producing countries stârting from a simulation of the activity and discovery of ne\rv ¡eservcs, data of prices, supplies in hand and cumulative production. The integration of demands for impo¡lation and the export capâcities of the various areas are included in the international module of the cnergy markets, which balances inte¡national iìows of energy.

Within each ite¡ation POLES calculares inirially rhe oil price (principal driver), and acco¡ding to this price projects a request on the hydrocarbons which will depend on the cor-ln¡ries, dre areas and thcir CDP and population.

Primary power consumption is estimated to satisry the remaindeÍ of the worldwide needs subtracted by the production pârt of already existing renewable sources.

The remaining fraction, to which nuclear energy E D POLEs Êrrøe)

POLÊS + EUcÂo = nèw capabilitiesl contributcs, is then forwarded to the principle of an optimized choice betwecn capacitìcs, avaìlability, feasibiliry and production costs of all tcchnologics. This need is convcrtcd thc¡cafter into primary energy and an encrgy mix is defined fo¡ that yea¡. This gives the figurc 2 with the cvolution of capacity needed as â function of hours of production each year.

This defines blocks of investmcnts of p¡oduction capacìtìes, rankcd as â ftÌnction of their load factors that â¡e ùsed to calculatc the new capacities investmonts in POLES,

These data and limits in interconnection capacities, load follorving capacities (ûinimum production by technology, maximum hour 7o changcs and associated costs...) arc then used i¡ EUC^D.

6 typìcal profi¡es of daily renewable productions (onshorc wind, off-sho.e wind and solar) of cach season have becn extracted for each country simulated. Those profiÌes where taken using a clustcring algorithml6 applied to a base of l-hoùr-stcps daìly productions takcn f¡om data available on grid operâto¡ wcb sitcs (RTE, T¡ânspa¡ency...). When and where datâ whe¡e not avaiJable, they whcrc jnterpolated from neighboring countrieslT. Noùtron Reacto¡ (TR) and the other one has the ones of Fast B¡eeder Reacto¡s (FBR). Some of tho characte¡istics arc givcn in the Annex or found in Ref In POLES, a ¡cduction of any of nucLea¡ reactor technology installed capacity is usually compensated by a mjx of demand reduction, increase ol thermal power plants (Biomass, coal or gas fuelled) ÿith CO2 Captu¡e and Sequest¡ation, a ¡cduction in dcmand, and more marginally an incrcase in new rencwables (sola¡ and rvind poìre¡).

ý.idý:. Because of ùe high number of compoting technologies, we hardly ever observe the two technologies as direct competitors as is expected by classical nuclcar energy sccnario studies.

ILD, Modeling Urânium Scarcity

The limits of diflerent reserves categories of IAEA Red book3 is often the main rofcrcncc used fo¡ the construction of sûpply curves in many nuclear energy scenario models. Thosc supply curves p¡opose an evolution of uranium price as a fuûction of mined resources. The lower cos! reserves being probably extracted first, ir is expcctcd that higher cost categories of reserves and mo¡e uncertain catego¡ies of resources lvould be ùsed later whcn the price of uranium makes their mining prolitable. As they do not need uraniu¡n once started, FBR may bc developed much faste¡ once thc perspective ofuranium scârcity would become clea¡er.

Two diffcrent principles of limitating the availabiliry ol'uranium have bcen implementcd in POI FS. In tlìe firsl onc', on top of a clâssical supply cuwc. the decision to invest in TR is madc dependent on thc "visibility" of uranium, ie the ratio of Reserves to Production (fuP). Ifthe ratio ìs highcr than the lifetime of the reactors (40 y by default) then, the risks associatcd wjth the unavailability of natural uranium over the expected lifetime of a TR would make the investment in this kind of reaclors very unlikely. Investors would probâbly found them mùch less prelerâble than other technologies, in particular FBR whosc costs are not rclated to uranium ûarket.

In the second onc, a limitation ofthe flow ofuranium has been added to the classical limit in voiumes of uranium availability. The price of uranium can be madc dependent not only on prcviously mined uranium but also as a fùnction of uranium prodùctions as on Fig. 5. This reflects both the difficùlty to open new ûiûes at a fast pace but also the pricc depende¡ce of uranjum when produced as a co-product. Impoúant ¡csources ofu¡anium could be tumed into minable reserves in particular \ÿhen extracted as co product of Those resources are very important when compared to identified rese¡ves, But thei¡ extraction at higher rates than thc nominal rates allorved by the needs of thc coextracted materials will be very expensive. Then, the cost ofuranium wouìd be increasing wtfh the flow ofuranium.

As soon as the nominal flow of uranium going through the process of extraction of thc associated mineral must be increased to sell more uranìum, the price should incrcase.

Fig. In paft III.B, investment in nuclear reactors is limited to a câpacity to answer only base-load and semi-base load demand. Nuclear reactor can cnter the competition for the investments only for tìre investment blocks of the highest drÌrâlion of production in Fig. 2. The investr¡ent blocks opened 10 a contribution from nuclear rcactors are broadening jn part III.C. Evcn though nuclea¡ reactors can contribute to answer dcmand levels seen only 4000 hou¡s a year, it does not mean that individùal reactors will have such limited operation hours. One can see on Fig. 1l that thc average load will not be some.

IIL B. Limited Load Foìlorving Capacities

The evolution of world nuclear capaciry as a fuûction of time for our diflerent scenarios is shown of Fig. 6. The implementation of a "climatc policy" makes nrclear 'I ene¡gy (thc sum of thc 2 nuclcar technology) growjng faster in the first part of this century as it replaces a lot of coal power plants. Then whatever thc sccnario, nuclear may face a platcâu that depends on its compctitors. If storagc is available, nuclqar is slightly reduced domonst¡ating the probable competition wìth a combination of renewable and storagc. If CCS is made avâilablc, lhen nuclcar is a littlc Icss comperirive again. Thc differences in load factors arc lcss than l% different bctween all cases and âre not shown here ÌotâÌWôld NùcleãrCãÞã.ity Figurc 6. Comparison ofworld nuclcar capaciry evo[Ìtion with time.

Figure 7 shows the same evoiution for Eu¡ope. One can scc than when cu¡rent nuclear reactors would be dismantled, POLES doesn't replace all ol thcm by new ¡cactors. This is not only due to phase out policies in Germany, Sweden, Slvitzcrland or Bclgìum. In fact therc would be lowe¡ demand level for base load electricity ând then that a lot of nuclcar rcactor would be supplemcnted by semi'bâse-load technologies even in countries that have not renounced to nuclear, typically France. Thc choicc between thc fossil basod technologies depends on climatc poljcy ând availability ofCCS. The allowcd (Mùhlcbcrg in Switzeriand, Oskarshamn and Ringhals in Swcden, Vcrmont Yankee in thc USA).

Figure 8 shows the cvolution of dcmand and p¡oduction proñlcs jn France in ycar 2100 in the case whe¡e new storagc is made available on a low dcmand level, summcr day. One can see that nuclear ene¡gy is used mainly for base load. A vcry ¡mportant cont¡ibution of wind and solar can be integrated iúto thc grid thanks to strong storage capacitics. The actual dismantling speed is based on the assumplion that all reactors have 40 ycars lifetìme cxactly, whjch is probably not ¡epresentativc of the diversity of tho rcality. Nuclear operators are applying both for lile extensions and for shut down earlier than With acccss to increasing investment blocks, depending on its local competitivcness, ncw nLìclear reacto¡s are boing built as can be seen on Fig As ir the resr of the world, increasing thc oppo¡tunitjcs for nuclear reacfor to competc in a b¡oader market shoìrld increase the installèd capacity. Fig. l0 shows that the capaciry could be iúcreased by Lrp to 30% in the second halfofthe centu¡y. To simulate the evolution of the powe¡ ma¡kets, onc needs to take into account both the long time steps of investments but also the variability of renewable production on an hour-long tiûe step. This is possible thanks to the coupling ofPOLES and EUCAD.

Tf nuclcar has limited load lollowing capaciries. wc have shown that it can be partially ousted in some countries in somc sccnarios. Depending on their availabilities and cxpected relative costs, thc rcplacing

Fig 4 .Fig. 4 .

 44 Fig. 4. Hoùrly Capâciry factor of on shore wind powcr, ofÊshore wind powcr and solar powe¡ of the 6 clustcred winter days lI.C, Nucìear Reactor Models Only two nrÌclear ¡eacto¡ types are modeled in POLES. Globally one has thc characteristics of a Thermal

  ^s thcir startup is dependent on thc availability of recyclcd mate¡ials from TR, their developmcnt wìll bc only indircctly dependent on the assumptions taken on uranium price and resoürces availability. Dependence on investment costs was discusscd in Ref.5 and 15.

Fig. 8 .Figurc 7 .

 87 Fig. 8. Demand and p¡oduction proñles of a summer day lvhen a cljmate policy is called, capacìty availablc. lll.B Ertended Loctd Folloý,ing Capacities ll[.8.I Global hnpact

  winter and 6 of summers) wìth very different hourly solar and wind power p¡odr¡ction profiles.

		One sùmmer and one winter average daily powcr
		dcmand profiles are simulated from the aggrcgation of
		sectorial demands. From those profiles, load, semi load
		and pcak power yea¡ are build and used to calculate
		maxjmum powe¡ capacitics presented in figure 2. As a
		funclion of simula¡ed variâble renewable productio¡s, a
		residual demand profile ìs build within the specific
		module EUCAD for Europc or in POLES for other
		fegioùs.
		l¿!
		Û 1000 rL'uJ
	EUCAD and the representative days are described in part ID. As shorvn on Fig. l, the coupling of the two	-Or;i:._:r Irvrsincnr blockj .¡r-4 D.mândc r¿siddcllc ncrrc du chargcrncnr dcVE, srock¡Bc L't 0R
	programs allows for the simulation ofthe evolutio¡ ofthe long-term energy markets with a yearÌy time step ùat takes into account the hourly variation of variable ¡crÌewable prodrìctions. This coupling can managc thc	Fig.2. Residual deûand from which Elect¡ic vehicules, ìnnovative storages and demand response solutions \ÿhere sustr¿cted and invesments blocks
	impact of this variability on ìoad factors of djspatchable
	powe¡ lechnologies a¡d also demand rcsponse and daily
	storage capacities' evolution sùch as electrìc vehicle
	battcry charging.
	Fig. L Typical time scalcs and time s.eps simùlated i¡ the
	coupling ofEUCAD and POLES
	Il.A, POLES rvorld ene¡gy model
	The behavioral equations describirÌg the demand take
	into account of the combinarion of the price effects, the incomes, the technic economic constraints and
	technologjcal changes. Enorgy demand is build as a sum of erergy intensive sectorial deûands (housing,
	industries, electric vehicle battery charging...). Sectorial
	demands are themsclves based on projection of their o!Ýn
	evolutions, efficicncy gains and fucl switching capâcities_

  The yea¡ly construction is then dcpcndont on thc local needs and compctitiveness of each power sourccs.The main interest for ou¡ analysis of POLES is that any of thesc two nuclea¡ technologies should also be competiliÿc 1Ýith any othe¡ elect¡icity production systems.POLES produccs for each country in Europe two 12 times daily dcmand profìles ave¡aged over 2 hours, one for wintcr ând onc for summer seasons. lt also produccs an imagc of thc jnstalled capacitics and an cstimation of variable costs for câch technology. The p¡oduction of renewable technologics is subt¡acted fiom the seasonal daily profilc as a function of the load factors of each typicâl days, Thosc profiìes a¡e used to simùlate the expected load demand as a fiìnction of working hours.

	ti	\	lr	I
	Fig.3 Thc itcration process simplified
	lI.B, Europe Unit Commitment And D¡spatching
	(EUCAD)

  5. All TR needs naturâl uranium as if using UOX fuels Their used fuel contain about 1ÿo of Plutonium. Fast B¡ccdcr Reactors and thcir associatcd ftrel cycle nced a fissile ûaterials inventory of 24 t of equivalent Pu per Gvy'e, obtaincd lrom recycled TR frÌcls to start up. Sensìtivities to this inventory rvcrc shown in Ref. 15. Uranium costs and limitcd availabìlity of resources arc discusscd in Ref. 15. They impact TR costs directly.FBR production costs are independent of the uranium ma¡ket but dependent on the availability of Pu comi¡g from reprocessed TR used fuels.

  phosphates, coal, black shales, gold, cobalt and other minerals. For instance,20l4lAEA Red Book declares almost the same volur¡es (7MT) for identified resources and fo¡ resources associated with phosphates. Uranium co extraction is cunently done at Olympic Dam in Australia where typically 7ÿo of current world demand is produced. Uranium is or was extracted together with phosphates, gold and rì1ore recently with Nickel, Cobalt, and Copper, in Talvivaa¡a in Finland.

  5. Evolution ofUranium prjce (S/KgU) as fu¡ction of cumulated Mined Uranium (Mt) and Uranium flow (kt/y)

	III. SENSITIVITIES OF NUCLEAR INSTALLED
	CAPACITIES AND LOAD FACTORS
	III.A. Scenârios Descriptions
	In this part ive compare the results of 4 main
	scenarios. In the fìrst one, no specific climate policy is put
	into force. All advanced technologies such as Carbon
	Captu¡c and Sequest¡ation (CCS) and advanced storage
	(not only Pumped Hydro) arc madc available.

ln thc 3 othe¡s, a 2'C policy is put into fo¡ce. The default one vr'ill bc called "Climate policy". The one in rvhich CCS technology is never ma¡ure would be the "No CCS" and the last without nor CCS nor advanced storage would be "No CCS, No sto¡age" case.

  9. On this Figure, the scenarios "No Policy" and "Climate Policy" are compared with or without extension of Load Following capacity. The spccific modulc for Dispatching is nsed only ìn Europe and thcn on ave¡age, the ìrnpact in tcrms ofload factors is limit€d to a rcduction of lo¿.

	lllB.2 Inpact ofextended Load Folloý,¡ig capac¡ties
	in Europe.
	lotäl Nucleãr Cãpãcity Europc
	lotðl World Nuclear Cãpacity
	Figure 9. Comparison of World nuclea¡ capacities with or
	withor¡t extended Load Followjng capacities.

  lot¡l Nucl.ar Cèpêc¡tÿ Eù¡ope lollowing arc made available. On averagc, France has incrcased its capacity by 30o%. NeÝertheless locally, on sunny sümmer days, nuclear energy is strongly reduced during solar production hours. During strong wind winte¡ days, nuclear energy could also be compÌetely supplanted by witd powcr. As cxpected at the time oflhe investmenr, thc extra capacities might not be used at full power depending on relative va¡iable cost and place in meril order. Nevertheless this will gìobally imp¡ove ûarket sha¡e ofnùclcar as shown in Table L Figure 10. Comparison of European nucleâr capacilìes wilh or withoul cxtcndcd Load Following capaciricc. The EUC^D approach is limited to Eùrope and to years after 2040. So the i¡npact iû load factots as a fu¡ction of the diversity of variable ¡enewable productiorì is almost impossible to câpturl] elsewhere. Fig. I I shows the evoLution of load factors in the cases where the loâd following capacities are the most wantcd tvhich are in the cases where the other flexible ìow carbon technologies are not avajlablc: Carbon Capture aùd Sequest¡ation and ìow cost storage. Iû those cases, thc load factors of nuclear power avgraged over Europe may change by 1tp Lo 6yo. Nucle¡r Power P¡anÌ Load Fã.toß Europe Fig. 12. Demand and production profÌles of a French summer day when a climate policy is called

TABLE I

 I energy cost stn¡cru¡e makes it partìcularly suitâble for basc load p¡oduction. V/ith the rising share of variable renervables, the need for base load electricity may reduce drastically, in particular if they have a higher access priority to the g¡id. Thus, if nuclear power cannot adapt to reducing load factors, it could be supplanted by more flexible teclìnoìogies.

	. Eu	ean sha¡e ofnuclear ene	in 2100 (%)
	IV. CONCLUSIONS

Nuclear

  2"cpolrcy, no n€w orage, Figure I l Comparison ofEuropean nuclear Load Factors wilh or wìthout extendcd Lo0d Following capacities.IILB.3 Daily profle in case ofrcducedflexibleFigure9shows the evolution of demand and production profiles in France in year 2100 in the case rvherc no CCS capacity but extended nuclear load technologies could bc a mix of coal(in case of absence ol clìmatc policy), gas, and gas with CCS ìf a climatc policy exists and this tcchnology is availablc. With cxtcndcd Ioad following capacitics. ot¡r sjmùlations shows that dcspìte a rcduction in average load factors, nuclcâr rcactors would p¡oduce moro encrgy globally thanks to highcr installed capacities. One point that may look surprising is that, as rene\ÿablc, nuclcar business model could be improvcd if large storage technologies exist. Reciprocally, ¡f storages arc not aÿailablc, thc Ioad followìng capacity of nuclear .eactors could increâse a little the variable ¡enewable sha¡0. Thcsc non-intuitive conclusions confi¡m the nced for global scale prospective tools. [n particular if those tools must bc able to managc both the very long lifetime of invesh¡s¡15 in po!ver production capaciry and grids and ihe very short pcriod ofva¡iability ofsome sources.

		Base Load	Extended Load
			Following
			CaÞacity
	No Policy	6.1	8.3
	Climate Policy	8.3	10.4
	Climatc Policy	I0.4	t5 2
	no CCS

ACKNOWLEDGMENTS

The authors want to thank the institute Camot- Energie du Futur of Grenoble for supporting the PROSPEN Project and the Défi NEEDS for supponing RUSDYN project.