Balthazar Bauer

Azam

Lenaïck, Pierrick, Louiza, Melissa Antoine Brice

Georges-Axel Aurélien

Florian

Hoeteck

Lelio

Timothée

Charles

Paul

Clément Bruno

Vincent Hugo

Ziyad, Ulysse, Bruno Antonin Lucas

Antoine Cyril

Gaël

Alexis Lucas

Eoghen, Titouan, Jérôme, Léo Tristan

Transferable e-cash: an analysis in the Algebraic Group Model

Transferable e-cash is the most faithful digital analog of physical cash, as it allows users to transfer coins between them without interacting with the bank. Strong anonymity requirements and the need for mechanisms to trace illegal behavior (double-spending of coins) have made instantiating the concept notoriously hard. Baldimtsi et al. (PKC'15) have given a first instantiation, which however relied on a powerful cryptographic primitive that made the scheme non-practical. In this thesis we revisit the model for transferable e-cash, proposing simpler yet stronger security definitions and then give the first concrete instantiation of the primitive, basing it on bilinear groups, and analyze its concrete efficiency. Because to build our scheme, we are using non-standard assumption in a bilinear group context, we analyze the hardness of a broad class of assumptions in a relevant context: the algebraic group model.

Il y a beaucoup de gens que je souhaiterais remercier à cette occasion, à commencer par mes encadrants de thèse Georg Fuchsbauer et David Pointcheval qui m'ont aidé aussi bien dans pour la partie scientifique de ma thèse que dans mes déboires administratifs.

Je remercie également les autres membres du jury, Damien Vergnaud, Olivier Sanders, Carla Ráfols, et tout particulièrement les rapporteurs Olivier Blazy et Eike Kiltz qui auront bien voulu prendre le temps de relire ce manuscrit.

Plus généralement, le cadre de travail à l'ENS était sans doute idéal pour effectuer cette thèse, entre autres grâce à la bonne humeur et à la gentillesse des nombreux membres du DI que j'ai eu l'occasion de côtoyer, comme Chloé, Romain,

Chapter 1 Introduction

Context

Trade and money are likely to have originated within the first societies with strong, centralized power. It was then a matter of taxing people to contribute to the administrations of a strong state. Since the methods of business transactions have been constantly evolving to allow for more efficient volumes, and ever-increasing transaction frequencies over ever-increasing distances. In particular the digitalization of these transactions has become widespread on whole swathes of the globe. It is notable, given the increase in the use of hardware and software from telecommunication, as with communication in general (a financial transaction being only a communicative exchange), digitalization is accompanied by security and confidentiality issues.

While the issue of confidentiality of transactions is not specific to digitized transactions, it is all the more serious in a technological context that requires that the security and confidentiality issues have taken place on a digital medium without guaranteeing to any the moment the digital data is erased.

Anonymity and decentralization. In the 1980s, David Chaum developed concepts such as blind signatures, that make the concept tangible of "confidential transactions". "Cypherpunks" manifests written in the 90s show a real interest in these problems from "anarcho-capitalist" movements. Various companies such as Digicash (1989)(1990)(1991)(1992)(1993)(1994)(1995)(1996)(1997)(1998), Monero (2014-now), Z-Cash (2016now) were founded, their vocation being to respond to this need for anonymity. It is noteworthy that the anarcho-capitalists (libertarians) have also had the other aim to develop parallel (and even competing) monetary systems to those of the states. Thus, following the logic of Bitcoin (2009now) [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash[END_REF], which aims decentralizing the issuance of money (and the validation of transactions), but in no way anonymous (David D. Friedman: "Bitcoin is, in a sense, the least anonymous money that has ever existed since every transaction is observable by anyone with a bitcoin account." [Fri]), contrary to the great misunderstanding by the media coverage, Z-Cash, and Monero thus realize both anonymity and the formal "decentralization" (see table ). The interest in the confidentiality of transactions seems to echo with the willingness displayed by the states to control much more drastically financial transactions, in order to fight against tax evasion, black markets, and other illegal activities. Even though through public research budgets, the states also fund projects related to anonymous transactions. For example, this is the case of this thesis funded by the french national research agency (ANR). This paradox can be explained by the autonomy of state institutions, or by a lack of understanding of the technological challenges that decision-makers face.

Overview of the thesis. After a brief state of the art of the subjects dealt with in the thesis in this chapter, and a reminder of all necessary definitions and properties in Chapter 2, we will show in Chapter 3 why by using the AGM, one may consider as cryptographic assumptions a large family of various assumptions (in particular a non-standard assumption, such as one we will use later).

In Chapter 4, a new primitive is developed: Signatures on rerandomizable ciphertexts. Initially, it was supposed to be used to build transferable e-cash schemes. But we finally showed that it was not necessary, thereby improving the efficiency of our scheme.

Then in chapter 5, we will formally define the security properties of a transferable e-cash scheme in compare our models to previous ones, and finally, we will propose a scheme that addresses the goal of this thesis by formally proving it satisfies our scheme.

State of the art The Algebraic Group Model

A central paradigm for assessing the security of a cryptographic scheme or hardness assumption is to analyze it within an idealized model of computation. A line of work initiated by the seminal work of Nechaev [START_REF] Nechaev | Complexity of a determinate algorithm for the discrete logarithm[END_REF] introduced the generic group model (GGM) [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF][START_REF] Ueli | Abstract models of computation in cryptography[END_REF], in which all algorithms and adversaries are treated as generic algorithms, i.e., algorithms that do not exploit any particular structure of a group and hence can be run in any group. Because for many groups used in cryptography (in particular, groups defined over some elliptic curves), the best known algorithms are in fact generic, the GGM has for many years served as the canonical tool to establish confidence in new cryptographic hardness assumptions. Moreover, when cryptographic schemes have been too difficult to analyze in the standard model, they have also directly been proven secure in the GGM (for example LRSW signatures [START_REF] Lysyanskaya | Pseudonym systems[END_REF][START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF]).

Following the approach first used in [START_REF] Abdalla | Security of the J-PAKE password-authenticated key exchange protocol[END_REF], a more recent work by Fuchsbauer, Kiltz, and Loss [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF] introduces the algebraic group model, in which all algorithms are assumed to be algebraic [START_REF] Paillier | Discrete-log-based signatures may not be equivalent to discrete log[END_REF]. An algebraic algorithm generalizes the notion of a generic algorithm in that all of its output group elements must still be computed by generic operations; however, the algorithm can freely access the structure of the group and obtain more information than what would be possible by purely generic means. This places the AGM between the GGM and the standard model. In contrast to the GGM, one cannot give information-theoretic lower bounds in the AGM; instead, one analyzes the security of a scheme by giving security reductions from computational hardness assumptions.

Because of its generality and because it provides a powerful framework that simplifies the security analyses of complex systems, the AGM has readily been adopted, in particular in the context of SNARK systems [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF][START_REF] Maller | Sonic: Zeroknowledge SNARKs from linear-size universal and updatable structured reference strings[END_REF][START_REF] Lipmaa | Simulation-extractable SNARKs revisited[END_REF][START_REF] Gabizon | PLONK: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge[END_REF]. It has also recently been used to analyze blind (Schnorr) signatures [START_REF] Fuchsbauer | Blind schnorr signatures and signed ElGamal encryption in the algebraic group model[END_REF], which are notoriously difficult to prove secure in the standard or random oracle model. Another recent work by Agrikola, Hofheinz and Kastner [START_REF] Agrikola | On instantiating the algebraic group model from falsifiable assumptions[END_REF] furthermore shows that the AGM constitutes a plausible model, which is instantiable under falsifiable assumptions in the standard model.

Since its inception, many proofs in the AGM have followed a similar structure, which often consists of a series of tedious case distinctions. A natural question is whether it is possible to unify a large body of relevant hardness assumptions under a general 'Uber' assumption. This would avoid having to prove a reduction to a more well-studied hardness assumption for each of them in the AGM separately. In this work, we present a very rich framework of such Uber assumptions, which contain, as special cases, reductions between hardness assumptions in the AGM from prior work [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF][START_REF] Loss | New techniques for the modular analysis of digital signature schemes[END_REF]. We also show that there exists a natural hierarchy among Uber assumptions CHAPTER 1. INTRODUCTION of different strengths. Together, our results give an almost complete classification in the AGM of common hardness assumptions over (bilinear) groups of prime order.

Signatures on randomizable ciphertexts

A standard approach for anonymous authentication is to combine signatures, which yield authentication, with zero-knowledge proofs, which allow to prove possession of a signature without revealing information about the latter and thus provide anonymity. This approach has been followed for (multi-show) anonymous credentials schemes, for which several showings of the same credential cannot be linked (in contrast to one-show credentials, e.g. [START_REF] Brands | Rethinking public-key Infrastructures and Digital Certificates: Building in Privacy[END_REF][START_REF] Baldimtsi | Anonymous credentials light[END_REF]).

The zero-knowledge proofs for these schemes are either instantiated using Σ-protocols [START_REF] Camenisch | A signature scheme with efficient protocols[END_REF][START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF] (and are thus interactive or in the random oracle model) or in the standard model [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF] using Groth-Sahai proofs [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]. As this proof system only supports very specific types of statements in bilinear ("pairing-friendly") groups, signature schemes whose verification is of this type have been introduced: structure-preserving signatures [AFG + 10] sign messages from a group G and are verified by checking equivalences of products of pairings of group elements from the verification key, the message and the signature.

Equivalence-class signatures. Hanser and Slamanig [START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF] extended this concept to structurepreserving signatures on equivalence classes (later improved in [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF]) for messages from G 2 , by adding a functionality called signature adaptation: given a signature on a message m ∈ G 2 and a scalar r, anyone can "adapt" the signature so it verifies for the message r • m. A signature thus authenticates the equivalence class of all multiples of the signed message.

Equivalence-class signatures (ECS) enable anonymous authentication that completely forgoes the layer of zero-knowledge proofs and thus yields considerable efficiency gains. Consider anonymous credentials. A credential is a signature on a message m (which typically contains a commitment to the user's attributes). In previous schemes, when authenticating, the user proves in zero knowledge that she knows a message m (and an opening of the contained commitment to the attributes she wants to show) as well as a signature on m; several authentications with the same credential are thus unlinkable. Using ECS, this is possible without using any proof system [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF]: the user simply shows r • m for a fresh random r together with an adapted signature. Anonymity is implied by the following property of ECS: to someone that is given m and a signature on m, the pair consisting of m := r • m for a random r and the signature adapted to m is indistinguishable from a random element m from G 2 together with a fresh signature on m .

Besides the first attribute-based anonymous credential scheme for which the complexity of showing is independent of the number of attributes [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF], ECS have also been used to build very efficient blind signatures with minimal interaction between the signer and the user that asks for the signature [START_REF] Fuchsbauer | Practical round-optimal blind signatures in the standard model[END_REF][START_REF] Fuchsbauer | Practical round-optimal blind signatures in the standard model from weaker assumptions[END_REF], revocable anonymous credentials [START_REF] Derler | A new approach to efficient revocable attribute-based anonymous credentials[END_REF], as well as efficient constructions [START_REF] Fuchsbauer | Access control encryption for equality, comparison, and more[END_REF][START_REF] Derler | Highly-efficient fully-anonymous dynamic group signatures[END_REF] of both access-control encryption [START_REF] Damgård | Access control encryption: Enforcing information flow with cryptography[END_REF] and dynamic group signatures [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF].

The most efficient construction of ECS is the one from [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF], which was proven secure in the generic group model [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF]. A signature consist of 3 elements from a bilinear group, which the authors show to be optimal by relying on a result by Abe et al. [START_REF] Abe | Optimal structure-preserving signatures in asymmetric bilinear groups[END_REF]. Moreover, there is strong evidence that structure-preserving signatures of this size cannot be proved secure by a reduction to non-interactive assumptions [START_REF] Abe | Separating short structure-preserving signatures from non-interactive assumptions[END_REF], meaning a proof in the generic group model is the best we can hope for. Less efficient constructions of EQS from standard assumptions have since then been given in the standard model by weakening the security guarantees [START_REF] Fuchsbauer | Weakly secure equivalence-class signatures from standard assumptions[END_REF] and in the common-reference string model [START_REF] Khalili | Structure-preserving signatures on equivalence classes from standard assumptions[END_REF] (with signatures 6 times longer than [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF]).

Signatures with flexible public key [START_REF] Backes | Signatures with flexible public key: Introducing equivalence classes for public keys[END_REF] and mercurials signatures [START_REF] Crites | Delegatable anonymous credentials from mercurial signatures[END_REF] are extensions of ECS that allow signatures to be adapted not only to multiples of the signed message, but also to can then spend them to merchants, who later deposit them at the bank. The main two properties that e-cash systems are expected to satisfy are (1) unforgeability: no one, not even a collusion of adversarial users and merchants can spend more e-coins than they have withdrawn; and (2) anonymity: nobody (not even when the bank colludes with the merchant) can determine the spender's identity, that is, link a transaction to a particular withdrawal; spendings should moreover be unlinkable, meaning that no one can tell whether two coins were spent by the same user.

Arguably the most important difference between physical and electronic coins is that while both may be hard to forge, the latter are easy to duplicate. A central challenge in the design of e-cash systems are consequently countermeasures against double-spending, that is, multiple spending of the same coin. The first systems proposed were online e-cash schemes [START_REF] Chaum | Blind signature system[END_REF], where the merchant must be connected to the bank when receiving a payment; so before accepting a coin the merchant can enquire with the bank whether it has already been spent. Necessitating constant connectivity is however a strong requirement and not desirable for constrained devices, or not even practicable for autonomous devices like vending machines. Offline e-cash [START_REF] Chaum | Untraceable electronic cash[END_REF] eliminates this requirement, leading to a more versatile system, as payments can be made in isolation, without talking to the bank. Since in this setting merchants have no means of determining whether a coin has already been spent, double-spending cannot be prevented. Instead, elaborate mechanisms built into coins ensure that if a coin is deposited twice then the bank can determine the double-spender's identity-while as long as a coin is only spent once, the spender's anonymity is guaranteed.

In offline e-cash a coin withdrawn from the bank consists of the bank's signature σ on a unique serial number s, which is unknown to the bank. When spending the coin with a merchant, a double-spending tag t is computed, which encodes the identity of the spender in a non-retrievable way. The merchant then deposits c = (s, σ, t) at the bank. If two coins c, c with the same serial number but with different double-spending tags t, t are deposited, these tags together reveal the identity of the user who double-spent.

Variants of e-cash proposed in the literature include compact e-cash [START_REF] Camenisch | Compact e-cash[END_REF] and divisible e-cash [EO95, Oka95, CG07, CPST15], which aim at making withdrawal more efficient by withdrawing a large number of coins at once or by splitting coins later before spending. Fair e-cash [START_REF] Sebastiaan | On blind signatures and perfect crimes[END_REF] adds a tracing mechanism that not only allows to persecute double-spenders, but using a special key an authority can trace any user or coin in the system at any time.

Research on e-cash had progressed slowly for quite some time, arguably due to the fact that banks were unlikely to support it and that credit cards and centralised payment services despite offering little privacy are broadly accepted for online payments. With the advent of Bitcoin [?], which proposed an electronic currency that simply bypassed the banks, there has been renewed interest in e-cash, and techniques from the literature on anonymous e-cash are being applied to decentralised cryptocurrencies as well [MGGR13, BCG + 14].

Transferable e-cash. Classical e-cash requires merchants to deposit received coins at the bank, as these systems do not allow for coins to be transferred from one user to another. This is in stark contrast with physical cash, which naturally changes hands many times before eventually returning to a bank. A more truthful analogue of physical cash should therefore allow users to transfer coins to others, who should be able to further transfer the received coins, and so on; moreover, like spending in offline e-cash, these transfers should be possible offline, in particular, without being connected to the bank. This decreases the communication cost between the bank and the users, and also allows for faster realisations of coin transfers.

Transferable e-cash [START_REF] Van Antwerpen | [END_REF][START_REF] Okamoto | Disposable zero-knowledge authentications and their applications to untraceable electronic cash[END_REF][START_REF] Franklin | Secure and efficient off-line digital money (extended abstract)[END_REF] was proposed in the 1990s and a line of research analysed the desired security properties. Despite two decades of research, all proposed schemes are either flawed, only meet weak security and privacy requirements, or are of purely theoretical interest. Examples of the latter category are schemes whose coins grow exponentially in the number [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF]. It does not assume any trusted parties nor does it rely on Cook-Levin reductions or heuristics like the random-oracle model [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF] and is proven secure under standard assumptions from elliptic-curve cryptography. Although coins only grow linearly in the number of transfers and the scheme can be implemented in principle, it is hardly practical. The work first revisits (game-based) anonymity definitions and introduces a new notion that had not been captured before, which is a strengthening of PA2 (a.k.a. spend-then-receive), the strongest anonymity notion defending against a malicious bank. While it is impossible to prevent an adversary that colludes with the bank from linking a coin he previously owned to one he receives [START_REF] Canard | Anonymity in transferable e-cash[END_REF], the new notion demands that he should not learn anything about the users that possessed the coin in between.

For transferable e-cash, the owner of a coin should be able to pass a coin, containing the bank's signature, to another user in a way that maintains the validity of the coin, carries all necessary information to detect double-spending, and all this while preserving anonymity. This can be abstracted as computing from a signature a fresh variant (unlinkable to the original one to ensure anonymity) that includes further information (such as double-spending information for the new owner). Generalising homomorphic signatures [START_REF] Boneh | Signing a linear subspace: Signature schemes for network coding[END_REF] and commuting signatures [START_REF] Fuchsbauer | Commuting signatures and verifiable encryption[END_REF], Chase et al. [START_REF] Chase | Malleable signatures: New definitions and delegatable anonymous credentials[END_REF] proposed malleable signatures, where anyone can transform a signature on a message m into a signature on m , as long as T (m) = m for some allowed transformation T . They show that malleable signatures yield delegatable credentials, and the transferable e-cash scheme in [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] builds on this construction, while adding traceability of double-spenders. A coin is first signed by the bank and when transferring the coin, a user "mauls" this signature using a valid transformation that guarantees that the coin is owned by the spender and the new coin/signature encodes the right information on the receiver. Serial number and double-spending tag are encrypted under the public key of the bank, which can therefore be used to decrypt to check for double-spending on deposit. Anonymity is ensured by re-randomising these ciphertexts before every transfer.

While malleable signatures are a useful abstraction of the concepts required to transfer coins in an anonymous manner, they dissimulate the considerable complexity underlying their actual instantiations.

Other works. For the sake of completeness, let us also mention the following works on transferable e-cash. Zhang et al. [START_REF] Zhang | Anonymous transferable conditional e-cash[END_REF] proposed a transferable variant of conditional e-cash [START_REF] Shi | Conditional e-cash[END_REF], where the validity of a coin depends on the outcome of an event. The scheme extends the security definitions and the scheme from [BCF + 11], but the additional security requirements are not formalised and the proofs are not convincing. Sarkar [START_REF] Sarkar | Multiple-use transferable e-cash[END_REF] constructed a protocol, which was later shown to be neither anonymous nor to prevent double-spending by Barguil and Barreto [START_REF] Joao | Security issues in Sarkar's e-cash protocol[END_REF]. Tiwari and Gupta [START_REF] Tiwari | Biometrics based observer free transferable e-cash[END_REF] proposed "biometric-based" transferable e-cash and claimed security under hardness of the discrete logarithm problem, but gave no formal security analysis or security proofs.

Very recently, Tewari and Hughes [START_REF] Tewari | Fully anonymous transferable ecash[END_REF] proposed "fully anonymous transferable ecash", a title that is doubly misleading. As their transfer protocol provides no means for tracing double-spenders, they require every transfer to be included in a blockchain. The scheme does thus not meet a central requirement of transferable e-cash, namely offline transferability; it is also not anonymous (let alone "fully"), as every coin has a non-hidden unique identifier, which lets anyone trace coins across transfers.

Instantiation.

Our main contribution is an instantiation of transferable e-cash, which we prove satisfies our security model, and which is much more efficient than the only previous realization [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF]. To do so, we depart from the use of malleable signatures, which due to their generality and strong security guarantees in the spirit of simulation-sound extractability result in very inefficient schemes.

OUR RESULTS

Instead, we give a direct instantiation based on Groth-Sahai proofs [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], which are randomizable, structure-preserving signatures [AFG + 10], which are compatible with GS proofs, and rerandomizable encryption satisfying RCCA-security [START_REF] Canetti | Relaxing chosen-ciphertext security[END_REF] (a the corresponding variant of CCA security). While we use signature schemes from the literature [START_REF] Abe | Optimal structure-preserving signatures in asymmetric bilinear groups[END_REF][START_REF] Fuchsbauer | Commuting signatures and verifiable encryption[END_REF], we construct a new RCCA-secure encryption scheme based on [START_REF] Libert | Structure-preserving chosen-ciphertext security with shorter verifiable ciphertexts[END_REF] that is tailored to our scheme. Finally, we reuse the (efficient) tags introduced in [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] to trace double-spenders.

Due to the existence of an omnipotent "judge", no such tags were required in [BCF + 11]. Surprisingly, although we do not assume any active trusted parties, we achieve a comparable efficiency, which we do by realizing that the full potential of these tags had not been leveraged in [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF]: they had only been used to encode a user's identity; but, as we show, they can at the same time be used to commit the user. This means that, contrary to all previous instantiations, we can omit the inclusion of signatures by the users in the coins, which makes them lighter. For an informal, yet more detailed overview of our scheme see Sect. 5.3.

Our results

The Algebraic Group Model

An Uber-Assumption Framework for the AGM

The main challenge in analyzing Boyen's framework in the AGM setting is that we can no longer prove lower bounds as in the GGM. The next best thing would be to reduce the Uber assumption to a well-established assumption such as the discrete logarithm (DLog) assumption. Due to the general nature of the Uber assumption, this turns out to be impossible; in particular, our negative result (see below) establishes that algebraic reductions in the AGM can only reduce DLog to Uber assumptions that are defined by linear polynomials.

Indeed, as for Boyen's [START_REF] Boyen | The uber-assumption family (invited talk)[END_REF] proofs in the GGM, the degrees of the involved polynomials are expected to appear in our reductions. In our first theorem in Sect. 3.1 we show that in the AGM any Uber assumption is implied by a parametrized variant of the discrete logarithm problem: in the q-DLog problem the adversary, on top of the instance g z , is also given g z 2 , . . . , g z q and must compute z. We prove that if the maximum total degree of the challenge polynomials in ( -→ R , -→ S , -→ T ) of an Uber assumption is at most q, then it is implied by the hardness of the q-DLog problem. This establishes that under q-DLog, anything that is not trivially computable from a given instance (represented by (

- → R , - → S , - → T )
) is infeasible to compute. We prove this by generalizing a technique first used by Fuchsbauer et al. [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF] to prove soundness of Groth's SNARK [START_REF] Groth | On the size of pairing-based non-interactive arguments[END_REF] under the q-DLog assumption in the AGM.

Proof idea. To convey our main idea, consider a simple instance of the Uber assumption parametrized by polynomials R 1 , . . . , R r , F 1 and let

- → S = - → T = ∅. That is, the the adversary is given group elements U 1 = g R 1 ( -→ x ) 1 , . . . , U r = g Rr( -→ x ) 1 for a random - → x and must compute U = g F 1 ( -→ x ) 1
. For this problem to be non-trivial, F 1 must be linearly independent of R 1 , . . . , R r , that is, for all -→ a ∈ Z r p we have R (

- → X ) = i a i R i ( - → X )
. Since the adversary is assumed to be algebraic (see Def. 2.4), it computes its output U from its inputs U 1 , . . . , U r by generic group operations, that is, for some vector -→ µ we have U = i U µ i i . In the AGM, the adversary is assumed to output this vector -→ µ . Taking the logarithm of the previous equation yields

R ( - → x ) = r i=1 µ i R i ( - → x ). (1.1) Since R is independent from - → R , the polynomial P ( - → X ) := R ( - → X ) -i µ i R i ( - → X
) is non-zero. On the other hand, (1.1) yields P ( -→ x ) = 0 for a successful adversary.

The adversary has thus (implicitly) found a non-zero polynomial P , which has the secret -→ x among its roots. Now, in order to use this to solve a q-DLog instance (g 1 , g z 1 , . . . , g z q 1 ), we embed a randomized version of z into every coordinate of -→ x . In particular, for random vectors -→ y and -→ v , we implicitly let x i := y i z + v i mod p. By leveraging linearity, the reduction can compute the group elements

U i = g R i ( -→ x ) 1 , etc, from its DLog instance. If P ( - → X ) is non-zero then Q(Z) := P (y 1 Z + v 1 , . . . , y m Z + v m
) is non-zero with overwhelming probability: the values v i guarantee that the values y i are perfectly hidden from the adversary and, as we show (Lemma 2.2), the leading coefficient of Q is a non-zero polynomial evaluated at y 1 , . . . , y m , values that are independent of the adversary's behavior. Schwartz-Zippel thus bounds the probability that the leading coefficient of Q is zero, and thus, that Q ≡ 0. Since Q(z) = P ( -→ x ) = 0, we can factor the univariate polynomial Q and find the DLog solution z, which is among its roots.

Extensions. We next extend our approach to a flexible (i.e., adaptive) version of the static Uber assumption, where the adversary can adaptively choose the polynomials (Sect. 3.2) as well as a generalization from polynomials to rational fractions (Sect. 3.3). We combine the flexible framework with the rational fraction framework in Sect. 3.4. After these generalizations, our framework covers assumptions such as strong Diffie-Hellman [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF], where the adversary must compute a rational fraction of its own choice in the exponent. In a next step (Sect. 3.5), we extend our framework to also cover gap-type assumptions such as Gap Diffie-Hellman (GDH) [START_REF] Okamoto | The gap-problems: A new class of problems for the security of cryptographic schemes[END_REF], which was recently proven equivalent to the DLog assumption in the AGM by Loss [START_REF] Loss | New techniques for the modular analysis of digital signature schemes[END_REF]. GDH states that the CDH assumption remains true even when the DDH assumption no longer holds. Informally, the idea of the proof given in [START_REF] Loss | New techniques for the modular analysis of digital signature schemes[END_REF] (first presented in [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF] for a restricted version of GDH) is to argue that the DDH oracle given to an algebraic adversary is useless, unless the adversary succeeds in breaking CDH during an oracle query. The reduction simulates the DDH oracle by always returning false. We generalize this to a broader class of assumptions, using a different simulation strategy, which avoids a security loss.

We also present (Sect. 3.6) an extension of our (adaptive) framework that allows to capture assumptions as strong as the LRSW assumption [START_REF] Lysyanskaya | Pseudonym systems[END_REF], which forms the basis of the Camenisch-Lysyanskaya signature scheme [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF]. The LRSW assumption falls outside (even the adaptive version of) Boyen's Uber framework, since the adversary need not output the polynomial it is computing in the exponent.

The LRSW and GDH assumptions were previously studied in the AGM in the works of [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF][START_REF] Loss | New techniques for the modular analysis of digital signature schemes[END_REF], who gave very technical proofs spanning multiple pages of case distinctions. By comparison, our Uber Framework offers a more general and much simpler proof for both of these assumptions. Finally, we are able to prove all these results using tight reductions. This, in particular, improves upon the non-tight reduction of DLog to LRSW in [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF].

Classifying Assumptions in our Framework

Finally, we prove two separation results that show the following: Separating (q + 1)-DLog from q-DLog. This shows that with respect to currently known (i.e., algebraic) reduction techniques, the Uber assumption, for increasing degrees of the polynomials, defines a natural hierarchy of assumptions in the AGM. More concretely, the q-lowest class within the established hierarchy consists of all assumptions that are covered by a specific instantiation of the Uber assumption which can be reduced from the q-DLog problem. Our separation result (Theorem 3.15) shows that there is no algebraic reduction from the q-DLog problem to the (q + 1)-DLog problem in the AGM. This implies that assumptions within different classes are separated with respect to algebraic reductions. Interestingly, we are even able to show our separation for reductions that can rewind and choose the random coins of the solver for the (q + 1)-DLog problem freely.

Separating OMDL from q-DLog. Our second result (Theorem 3.17) shows a separation result between the one-more-DLog problem (OMDL) (where the adversary has to solve q DLog instances and is given an oracle that computes discrete logarithms, which it can access q -1 times) and the q-DLog problem (for any q) in the AGM. Our result strengthens a previous result by Bresson, Monnerat, and Vergnaud [START_REF] Bresson | Separation results on the "one-more" computational problems[END_REF], who showed a separation between the discrete logarithm problem (i.e, where q = 1) and the 2-one-more-DLog problem with respect to black-box reductions. By comparison, our result holds even in the AGM, where reductions are inherently non-black-box, as the AGM implicitly assumes an efficient extractor algorithm that extracts algebraic coefficients from the algebraic adversary. As the extractor is non-black-box (since it depends on the algebraic adversary), neither is any reduction that non-trivially leverages the AGM.

Our result clearly establishes the limits of our framework, as it excludes the OMDL family of assumptions. Unlike our first separation, this one comes with the caveat that it only applies to reductions that are "black-box in the AGM", meaning that they simply obtain the algebraic coefficients via the extractor, but cannot rewind the adversary or choose its random coins.

Related Work

A long line of research has considered frameworks to capture general classes of assumptions. We give an overview of the most closely related works. The first Uber assumptions were introduced by Boyen et al. [START_REF] Boneh | Hierarchical identity based encryption with constant size ciphertext[END_REF][START_REF] Boyen | The uber-assumption family (invited talk)[END_REF]. Others later gave alternative concepts to classify assumptions within cyclic groups. The works of Chase et al. [START_REF] Chase | Déjà Q: Using dual systems to revisit q-type assumptions[END_REF][START_REF] Chase | Déjà Q all over again: Tighter and broader reductions of q-type assumptions[END_REF] study assumptions in bilinear groups of composite order, which are not considered in the original Uber framework. They show that several q-type assumptions are implied by (static) "subgroup-hiding" assumptions. This gives evidence that this type of assumption, which is specific to composite-order groups, is particularly strong.

More recently, Ghadafi and Groth [START_REF] Ghadafi | Towards a classification of non-interactive computational assumptions in cyclic groups[END_REF] studied a broader class of assumptions in which the adversary must compute a group element from G T . Like our work, their framework applies to prime-order groups and extends to the case where the exponents can be described by rational fractions, and they also separate classes of assumptions from each other. However, their framework only deals with non-interactive assumptions, which do not cover the adaptive type of assumptions we study in our flexible variants (in fact, the authors mention extending their work to interactive assumptions as an open problem [START_REF] Ghadafi | Towards a classification of non-interactive computational assumptions in cyclic groups[END_REF]). Their work does not cover assumptions such as GDH or LRSW, which we view as particularly interesting (and challenging) to classify. Indeed, our framework appears to be the first in this line of work that offers a classification comprising this type of assumptions.

A key difference is that Ghadafi and Groth's results are in the standard model whereas we work in the AGM. While this yields stronger results for reductions, their separations are weaker (in addition to separating less broad types of Uber assumptions), as they are with respect to generic reductions, whereas ours hold against algebraic reductions that can assume that the adversary is algebraic. Furthermore, their work considers black-box reductions that treat the underlying solver as an (imperfect) oracle, while we show the non-existence of reductions in the AGM, which are, by definition, non-black-box (see above). A final difference to the work of [START_REF] Ghadafi | Towards a classification of non-interactive computational assumptions in cyclic groups[END_REF] lies in the tightness of all our reductions, whereas non of theirs are tight.

At CT-RSA'19 Mizuide, Takayasu, and Takagi [START_REF] Mizuide | Tight reductions for Diffie-Hellman variants in the algebraic group model[END_REF] studied static (i.e., non-flexible) variants and generalizations of the Diffie-Hellman problem in prime-order groups (also with extensions to the bilinear setting) by extending proofs from [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF] in the obvious manner. Most of their results are special cases of our Uber assumption framework. Concretely, when restricting the degrees of all input polynomials to 1 in our static Uber Assumption, our non-triviality condition implies all corresponding theorems in their paper (except the ones relating to Matrix assumptions, which are outside the scope of this work). By our separation of q-DLog for different q, our results for higher degrees do not follow from theirs by currently known techniques. Finally, they do not cover the flexible (adaptive) variants nor oracle-enhanced-and hidden-polynomial-type assumptions (such as GDH and LRSW).

A further distinction that sets our work apart from these prior works is our formulation of the aforementioned 'hidden-type' assumptions, where we allow the adversary to solve the problem with respect to a group generator of its own choice instead of the one provided by the game. A recent work [START_REF] Bartusek | The distinction between fixed and random generators in group-based assumptions[END_REF] shows that even in the GGM, allowing randomly chosen generators results in unexpected complications when proving lower bounds. Similarly, giving the adversary this additional freedom makes proving (and formalizing) our results more challenging. We also give this freedom to the reductions that we study (and prove impossible) in our separation results.

Signatures on randomizable ciphertexts

Our contribution. Our aim was to construct a scheme of signatures on randomizable ciphertexts with a large message space and short signatures. But first we strengthen the notion of signature unforgeability. In SoRC, signatures are produced (and verified) on pairs of encryption keys and ciphertexts (ek, c). In the original unforgeability notion [START_REF] Blazy | Signatures on randomizable ciphertexts[END_REF] the adversary is given a signature verification key and a set of encryption keys ek 1 , . . . , ek n and can then make queries (i, c) to get a signature for (ek i , c). Its goal is to return (i * , c * ) and a signature for (ek i * , c * ), so that c * encrypts a message of which no encryption has been submitted to the signing oracle. Signatures thus authenticate plaintexts irrespective of the encryption key.

In more detail, once a query (1, Enc(ek 1 , m)) was made, a signature for (ek 2 , Enc(ek 2 , m)) is not considered a forgery. In contrast, in our new definition (Def. 4.6), this is considered a forgery, since we view a signature as (obliviously) authenticating a message for a particular encryption key. That is, if from a signature on an encryption of a message for one key one can forge a signature on the same message for another key, this is considered a break of the scheme. A further difference is that, while in [START_REF] Blazy | Signatures on randomizable ciphertexts[END_REF] encryption keys are generated by the challenger, we let the adversary choose (in any, possibly malicious, way) the encryption keys (in addition to the ciphertexts) on which it wishes to see a signature, as well as the key for its forgery.

We then construct a scheme which signs ElGamal ciphertexts and whose signatures consist of 4 elements of an (asymmetric) bilinear group (3 elements from G 1 and 1 from G 2 ). Our scheme (given in Fig. 4.3) is inspired by the original equivalence-class signature scheme [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF], whose equivalence classes only provide "selfless" anonymity. We show that signatures adapted to a randomization of a ciphertext are equivalently distributed to fresh signatures on the new ciphertext (Proposition 4.8). We then prove that our scheme satisfies our strengthened unforgeability notion in the generic group model (Theorem 4.9).

Comparison with Blazy et al.

Apart from the stronger unforgeability notion we achieve, the main improvement of our scheme over [START_REF] Blazy | Signatures on randomizable ciphertexts[END_REF] concerns its efficiency. The Blazy et al. scheme builds on (a new variant of) Waters signatures [START_REF] Brent | Efficient identity-based encryption without random oracles[END_REF] and Groth-Sahai proofs [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], which allows them to prove unforgeability from standard assumptions. However, encrypting and signing a k-bit message yields a ciphertext/signature pair consisting of 12 + 12k group elements of an asymmetric bilinear group. In our scheme, a message is a group element (as for ElGamal encryption), which lets us encode 128-bit messages (or messages of unbounded length by hashing into the group). A ciphertext/signature pair consists of 6 group elements. We also propose a generalization to messages of n group elements for which a ciphertext/signature pair consists of n + 5 group elements.

The price we pay for this length reduction by a factor of over 250 (for 128-bit messages or longer) is an unforgeability proof in the generic group model. But, as we argue next, this is to be expected. Since we sign group elements and verification consists in checking pairing-product equations, our scheme is structure-preserving [AFG + 10]. Signatures for such schemes must at least contain 3 group elements [START_REF] Abe | Optimal structure-preserving signatures in asymmetric bilinear groups[END_REF] and schemes with such short signatures cannot be proved from non-interactive (let alone standard) assumptions [START_REF] Abe | Separating short structure-preserving signatures from non-interactive assumptions[END_REF]. Our 4-element signatures, which provide additional functionalities, and its unforgeability proof are therefore close to being optimal. We also note that a security reduction to computational hardness assumptions for schemes satisfying our unforgeability notion seems challenging, as the challenger cannot efficiently decide whether the adversary has won (in contrast to the weaker notion [START_REF] Blazy | Signatures on randomizable ciphertexts[END_REF]).

Transferable e-cash

Our contribution. Our contributions are two-fold: Security model. We first revisit the formal model for transferable e-cash, departing from [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF], whose model had itself already been a refined version of earlier ones. We start with giving a definition of correctness, which was lacking in previous works. Moreover, we discovered attacks against users following the protocol, against which previous models did not protect:

• When a user receives a coin (that is, the protocol accepts the received coin), then in previous models there is no guarantee that this coin will be accepted by other users when transferred. An adversary could thus send a mal-formed coin to a user, which the latter accepts but can then not spend.

• There are no guarantees for user against a malicious bank which at coin deposit refuses to credit the user's account (e.g., by claiming that the coin was invalid or had been double-spent).

In our model, when the bank refuses a coin, it is forced to accuse a user of double-spending and exhibiting a proof for this.

We moreover simplify the anonymity definitions, which in earlier version had been cluttered with numerous oracles the adversary has access to, and for which the intuitive notion that they were formalizing was hard to grasp. While our definitions are simpler, they are stronger in that they imply previous definitions (except for the previous notion of "spend-then-receive (StR) anonymity", whose version we argue is not relevant in practice).

We also show that the proof of StR anonymity of the previous scheme [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] is flawed.

Chapter 2

Preliminaries

In this chapter, we introduce the notations and basic assumptions and primitives employed throughout this manuscript. We start by recalling some standard mathematical and computational notions, then we briefly introduce provable security. We also recall some well-known numbertheoretic assumptions, to introduce the cryptographic primitives used throughout this work.

Notations

Sets, integers, moduli, and associated rings and groups. We denote real numbers by R, integers by Z and non-negative integers by N. If a, b are two integers such that a < b, we denote the (closed) integer interval from a to b by a; b . If q is a positive integer, we denote by Z q the ring of integers modulo q. In all of our constructions, the order of Z q will be public. Therefore, elements of Z q are represented as integers of the set 0; q -1 . For an integer x ∈ Z, x mod q is the reminder of the Euclidean division of x by q. It can be seen both as an integer in 0; q -1 and as an element of Z q . Vectors are denoted by letters with arrows, like -→ v . We indicated a vector -→ v 's entry by v i . We use -→ v T to denote the transpose of a vector -→ v .

Random variables. For a random variable X over a probability space (Ω, Σ, Pr), and a possible outcome x, we write Pr[X = x] to indicate the measure of the preimage of {x} ∈ Σ under Pr. We denote the action of sampling uniformly at random x from X with x ← X. Let us call range of a random variable X : Ω → E the set of elements x ∈ E for which the probability that X has outcome x is strictly positive. In this work, we refer only to random variables whose range is finite.

A random variable X defined on a finite probability space (Ω, Pr) is said to have the uniform distribution if Pr[X = x] = 1/| Im(X)| where Im(X) denotes the image of X. Given a non-empty finite set S, we let x $ ← -S denote the operation of sampling an element x from S uniformly at random.

Asymptotics. Given a function f : N → R, the set O(f ) describes all functions that can be asymptotically upper-bounded by f , that is, all g such that ∃c, λ 0 ∈ N, 0 ≤ g(λ) ≤ cf (λ) for all λ ≥ λ 0 . With a slight abuse of notation, we write g = O(f ) to denote that g ∈ O(f ). The set Õ(f ) describes all functions that can be upper-bounded by f ignoring logarithmic factors, that is, all g such that ∃c, k, λ 0 ∈ N, 0 ≤ g(λ) ≤ cf (λ) log k (λ) for all λ ≥ λ 0 . We use the notation o(f ) to identify all functions that can be asymptotically upper-bounded by f , where the upper-bound is strict. That is, all g such that ∀c ∃λ 0 ∈ N, 0 ≤ g(λ) < cf (λ) for all λ ≥ λ 0 .

A function µ :

N → [0, 1] is negligible (denoted µ = negl(λ)) if µ(λ) = o(λ -c
) for any fixed constant c. That is, if for all c ∈ N there exists λ c ∈ N such that µ(λ) < λ -c for all λ ≥ λ c . A CHAPTER 2. PRELIMINARIES function ν is overwhelming if 1 -ν = negl(λ). We let poly(λ) denote the set of polynomials in λ (more precisely, functions upper-bounded by a polynomial in λ) with integer coefficients.

Languages, machines, function families and complexity classes. Languages are denoted in calligraphic, e.g. L. We focus on languages whose alphabet is the set of bits {0, 1}.

Algorithms are formalized as Turing Machines and denoted in serif, e.g. M. We let M.rl(λ) be a length function (i.e., a function N → N polynomially bounded) in λ defining the length of the randomness for a probabilistic interactive Turing Machine M. By y := M(x 1 , . . . ; r) we denote the operation of running algorithm M on inputs x 1 , . . . and coins r ∈ {0, 1} M.rl(λ) and letting y denote the output. We see M both as a Turing Machine as well as a random variable. By y ← M(x 1 , . . .), we denote y := M(x 1 , . . . ; r) for random r ∈ M.rl(λ), and [M(x 1 , . . .)] the range of M on inputs x 1 , . . .. Unless otherwise specified, all the algorithms defined throughout this work are assumed to be probabilistic Turing machines that run in time poly(λ) -i.e., in PPT. An adversary is denoted by A; when it is interacting with an oracle O, we write A O . For two PPT machines A, B, with (A B)(x) we denote the execution of A followed by the execution of B on the same input x and with the same random coins. The output of the two machines is concatenated and separated with a semicolon, e.g., (out A ; out B ) ← (A B) (x).

Polynomials and rational fractions. We denote polynomials by uppercase letters P, Q and specify them by a list of their coefficients. If m is an integer, we denote by Z p [X 1 , . . . , X m ] the set of m-variate polynomials with coefficients in Z p and by Z p (X 1 , . . . , X m ) the set of rational fractions in m variables with coefficients in Z p . We define the total degree of a polynomial

P (X 1 , . . . , X m ) = -→ i ∈N m λ i 1 ,...,im m j=1 X i j j ∈ Z p [X 1 , . . . , X m ] as max -→ i ∈N m : λ i 1 ,...,im ≡p0 m j=1 i j .
For the degree of rational fractions we will use the "French" definition [START_REF] Deschamps | Mathématiques 1ère année : Cours et exercices corrigés[END_REF]: for (P,

Q) ∈ Z p [X 1 , . . . , X m ] × (Z p [X 1 , . . . , X m ] \ {0}) we define deg P Q := deg P -deg Q.
This definition has the following properties: The degree does not depend on the choice of the representative; it generalizes the definition for polynomials; and the following holds: deg(

F 1 • F 2 ) = deg F 1 + deg F 2 ,
Q(Z) ∈ (Z p [Y 1 , . . . , Y m , V 1 , . . . , V m ])[Z] as Q(Z) := P (Y 1 Z + V 1 , . . . , Y m Z + V m ). Then the coefficient of maximal degree of Q is a polynomial in Z p [Y 1 , . . . , Y m ] of degree d. 2.1. NOTATIONS Proof. P is of the form P ( - → X ) = -→ i ∈N m : Σ j i j ≤d λ i 1 ,...,im m j=1 X i j
j for coefficients λ i 1 ,...,im and thus

Q(Z) = -→ i ∈N m : Σ j i j ≤d λ i 1 ,...,im m j=1 (Y j Z + V j ) i j = -→ i ∈N m : Σ j i j ≤d λ-→ i m j=1 i j k=0 i j k Y k j Z k V i j -k j = -→ i ∈N m : Σ j i j ≤d λ-→ i i 1 k 1 =0 • • • im km=0 m j=1 i j k j Y k j j Z k j V i j -k j j = d =0 -→ i ∈N m : Σ j i j ≤d λ-→ i -→ k ∈N m : Σ j k j = m j=1 i j k j Y k j j Z k j V i j -k j j = d =0 λ Z with λ := -→ i ∈N m : Σ j i j ≤d λ-→ i -→ k ∈N m : Σ j k j = m j=1 i j k j Y k j j V i j -k j j
.

By assumption P ≡ 0. Thus for some i 1 , . . . , i m ≥ 0 with j i j = d we have λ i 1 ,...,im = 0, while λ i 1 ,...,im = 0 when j i j > d. By the latter we have

λ d = -→ i ∈N m : Σ j i j ≤d λ-→ i -→ k : Σ j k j =d m j=1 i j k j Y k j j V i j -k j j = -→ i ∈N m : Σ j i j =d λ-→ i m j=1 Y i j j ,
where the last step follows since k j ≤ i j for all j and j i j ≤ d, j k j = d implies that k j = i j for all j. Since P is a polynomial of total degree d, for some -→ i ∈ N m we have j i j = d and λ-→ i = 0. We conclude that λ d is a polynomial in (Y 1 , . . . , Y m ) of total degree d.

Bilinear Groups. We next state the definition of a bilinear group.

Definition 2.3 (Bilinear group). A bilinear group (description) is a tuple

G = (G 1 , G 2 , G T , e, φ, ψ, p) such that • G i is a cyclic group of prime order p, for i ∈ {1, 2, T };
• e is a non-degenerate bilinear map e : G 1 × G 2 → G T , that is, for all a, b ∈ Z p and all generators g 1 of G 1 and g 2 of G 2 we have that g T := e(g 1 , g 2 ) generates G T and e(g a 1 , g

b 2 ) = e(g 1 , g 2 ) ab = g ab T ; • φ is an isomorphism φ : G 1 → G 2 , and ψ is an isomorphism ψ : G 2 → G 1 .
All group operations and the bilinear map e must be efficiently computable. G is of Type 1 if the maps φ and ψ are efficiently computable; G is of Type 2 if there is no efficiently computable map φ; and G is of Type 3 if there are no efficiently computable maps φ and ψ. We require that there exist an efficient algorithm GenSamp that returns generators g 1 of G 1 and g 2 of G 2 , so that g 2 is uniformly random, and (for Types 1 and 2) g 1 = ψ(g 2 ) or (Type 3) g 1 is also uniformly random. By GenSamp i we denote a restricted version that only returns g i .

We assume the existence of a probabilistic polynomial-time (p.p.t.) algorithm BGGen that takes as input an integer λ in unary and outputs a description of an (asymmetric) bilinear group (p, G, G, Ĝ, Ĝ, G T , e) consisting of groups (G, •) and ( Ĝ, •), generated by G and Ĝ, resp., and (G T , •), all of cardinality a prime number p ∈ {2 λ , . . . , 2 λ+1 }, and a bilinear map e : G × Ĝ → G T , such that e(G, Ĝ) generates G T , called pairing. CHAPTER 2. PRELIMINARIES (Algebraic) Security games. We use a variant of (code-based) security games [START_REF] Bellare | Code-based game-playing proofs and the security of triple encryption[END_REF]. In game G G (defined relative to G), an adversary A interacts with a challenger that answers oracle queries issued by A. The game has a main procedure and (possibly zero) oracle procedures which describe how oracle queries are answered. We denote the output of a game G G between a challenger and an adversary A by

G A G . A is said to win if G A G = 1. We define the advantage of A in G G as Adv G G,A := Pr G A G = 1 and the running time of G A G as Time G G,A .
In this work, we are primarily concerned with algebraic security games G G , in which we syntactically distinguish between elements of groups G 1 , G 2 and G T (written in bold, uppercase letters, e.g., Z) and all other elements, which must not depend on any group elements.

We next define algebraic algorithms. Intuitively, the only way for an algebraic algorithm to output a new group element Z is to derive it via group operations from known group elements. Definition 2.4 (Algebraic algorithm for bilinear groups). An algorithm A alg executed in an algebraic game G G is called algebraic if for all group elements Z ∈ G (where G ∈ {G 1 , G 2 , G T }) that A alg outputs, it additionally provides a representation in terms of received group elements in G and those from groups from which there is an efficient mapping to G; in particular: if U 0 , . . . , U ∈ G 1 , V 0 , . . . , V m ∈ G 2 and W 0 , . . . , W t ∈ G T are the group elements received so far then

A alg provides vectors - → µ , - → ν , - → ζ , - → η , - → δ and matrices A = (α i,j ), B = (β i,j ), Γ = (γ i,j ) such that • Z ∈ G 1 (Type 1 and 2): Z = i U µ i i • i ψ(V i ) ν i (Type 3): Z = i U µ i i • Z ∈ G 2 (Type 1): Z = i φ(U i ) ζ i • i V η i i
(Type 2 and 3):

Z = i V η i i • Z ∈ G T : Z = i j e U i , V j α i,j • i j e U i , φ(U j ) β i,j • i j e ψ(V i ), V j γ i,j • i W δ i i
, where β i,j = 0 for Type 2 and β i,j = γ i,j = 0 for Type 3.

We remark that oracle access to an algorithm B in the AGM includes any (usually non-black-box) access to B that is needed to extract the algebraic coefficients. Thus, our notion of black-box access in the AGM mainly rules out techniques such as rewinding B or running it on non-uniform random coins.

Security Model

Generic group model. Generic algorithms A gen are only allowed to use generic properties of a group. Informally, an algorithm is generic if it works regardless of what group it is run in. This is usually modeled by giving an algorithm indirect access to group elements via abstract handles. It is straight-forward to translate all of our algebraic games into games that are syntactically compatible with generic algorithms accessing group elements only via abstract handles. We measure the running times of generic algorithms as queries to an oracle that implements the abstract group operation, i.e., every query accounts for one step of the algorithm. We highlight this difference by denoting the running time of a generic algorithm with the letter o rather than t. We say that winning algebraic game G G is (ε, o)-hard in the generic group model if for every generic algorithm

A gen it holds that Time G G,Agen ≤ o =⇒ Adv G G,Agen ≤ ε.
As all of our reductions run the adversary only once and without rewinding, the overhead in the running time of our reductions is additive only. We make the reasonable assumption that, 2.3. COMPUTATIONAL ASSUMPTIONS compared to the running time of the adversary, this is typically small, and therefore ignore the losses in the running times for this work in order to keep notational overhead low.

We assume that a generic algorithm A gen provides the representation of Z relative to all previously received group elements, for all group elements Z that it outputs. This assumption is w.l.o.g. since a generic algorithm can only obtain new group elements by querying two known group elements to the generic group oracle; hence a reduction can always extract a valid representation of a group element output by a generic algorithm. This way, every generic algorithm is also an algebraic algorithm.

Furthermore, if B gen is a generic oracle algorithm and A alg is an algebraic algorithm, then

B alg := B A alg
gen is also an algebraic algorithm. We refer to [START_REF] Ueli | Abstract models of computation in cryptography[END_REF] for more on generic algorithms.

Security Reductions. All our security reductions are (bilinear) generic algorithms, which allows us to compose all of our reductions with hardness bounds in the (bilinear) generic group model (see next paragraph). Let G G , H G be security games. We say that algorithm R gen is a generic (∆

(•) ε , ∆ (+) ε , ∆ (•) o , ∆ (+) o )-reduction from H G to G G if
Adv H G,B alg ≥ 1 ∆ (•) ε • Adv G G,A alg -∆ (+) ε , Time H G,B alg ≤ ∆ (•) o • Time G G,A alg + ∆ (+) o .
Furthermore, for simplicity of notation, we will make the convention of referring to 1, ∆ ε , 1, ∆ oreductions as (∆ ε , ∆ o )-reductions.

Composing information-theoretic lower bounds with reductions in the AGM. The following lemma from [START_REF] Loss | New techniques for the modular analysis of digital signature schemes[END_REF] explains how statements in the AGM compose with bounds from the GGM.

Lemma 2.5. Let G G and H G be algebraic security games and let R gen be a generic ∆

(•) ε , ∆ (+) ε , ∆ (•) o , ∆ (+) o -reduction from H G to G G . If H G is (ε, o)-secure in the GGM, then G G is (ε , o )-secure in the GGM where ε = ε • ∆ (•) ε + ∆ (+) ε , o = o/∆ (•) o -∆ (+) o .

Computational assumptions

Definition 2.6 (SXDH). The Symmetric External Diffie-Hellman Assumption states that given (g r , g s , g t ) for random r, s ∈ Z p , it is hard to decide whether t = rs or t is random; moreover, given (ĝ r , ĝs , ĝt ) for random r , s ∈ Z p , it is hard to decide whether t = r s or t is random.

The two following assumptions have been introduced in [AFG + 10]. We call it the Asymetric Double Hidden Strong Diffie Hellman (ADHSDH) assumption and the Asymetric Weak Flexible Computational Diffie Hellman (AWFCDH) assumption.

Definition 2.7 (q-ADHSDH). Given λ ∈ Z p and (g, f, k, x = g λ , ĝ, ŷ = ĝλ ) ← G 4 × Ĝ2 , a i = (kg β i ) 1 λ+α i , b i = f α i , v i = g β i , di = ĝα i , ŵi = ĝβ i q i=1 , for c i , v i $ ← -Z p , it is hard to output a new tuple (a, b, v, d, ŵ) ∈ G 3 × Ĝ2 of this form, i.
2. PRELIMINARIES q-dlog A G i 01 g $ ← -GenSamp i 02 z $ ← -Z * p 03 z * $ ← -A g, g z , g z 2 , . . . , g z q 04 Return (z * = z) (q 1 , q 2 )-dlog A G 01 (g 1 , g 2 ) $ ← -GenSamp 02 z $ ← -Z * p 03 z * $ ← -A g 1 , g z 1 , g z 2 1 , . . . , g z q 1 1 , g 2 , g z 2 , . . . , g z q 2
2 04 Return (z * = z) Figure 2.1: q-discrete logarithm game q-dlog G i (left) and (q 1 , q 2 )-discrete logarithm game (q 1 , q 2 )-dlog G (right) relative to group G i , i ∈ {1, 2} and G, resp., and adversary A.

Definition 2.8 (AWFCDH).

Given random generators g ∈ G, ĝ ∈ Ĝ, and a = g α for α ← Z p , it is hard to output (g ν , g να , ĝν , ĝνα ), i.e., a tuple (r, m, ŝ, n) that satisfies e(a, ŝ) = e(m, ĝ) ∧ e(m, ĝ) = e(g, n) ∧ e(r, ĝ) = e(g, ŝ).

The q-discrete logarithm assumption and variants. For this work, we consider two generalizations of the DLog assumption, which are parametrized (i.e., "q-type") variants of the DLog assumption. We describe them via the algebraic security games q-dlog G i and (q 1 , q 2 )-dlog G in Fig. 2.1.

The following lemma, which follows similarly to the generic security of q-SDH [BB08], was proved (asymptotically) by Lipmaa [START_REF] Lipmaa | Progression-free sets and sublinear pairing-based non-interactive zeroknowledge arguments[END_REF]. For completeness, we give a concrete proof in Section 2.5. Lemma 2.9. Let o, q 1 , q 2 ∈ N, let q := max{q 1 , q 2 }. Then q-DLog and (q 1 , q 2 )-DLog are 1+(o+q+1) 2 q p-1 , osecure in the bilinear generic group model.

We remark that all though our composition results are stated in the bilinear GGM, it is straight forward to translate them to the standard GGM if the associated hardness assumption is stated over a pairing-free group. This is true, because in those cases, our reductions will also be pairing-free and hence are standard generic algorithms themselves.

Primitives used

Bilinear groups

The building blocks of our scheme will be defined over a (Type-3, i.e., asymmetric) bilinear group, which is a tuple Gr = (p, G, Ĝ, G T , e, g, ĝ), where G, Ĝ and G T are groups of prime order p; g = G, ĝ = Ĝ, and e : G × Ĝ → G T is a bilinear map (i.e., for all a, b ∈ Z p : e(g a , ĝb ) = e(g, ĝ) ab ) so that e(g, ĝ) generates G T . We assume that the groups are discrete-log-hard and other computational problems (DDH, CDH, SXDH, etc. defined in Section 2.3) are infeasible as well. We assume that there exists an algorithm BGGen that, on input the security parameter λ in unary, outputs the description of a bilinear group with p ≥ 2 λ-1 .

Randomizable proofs of knowledge and signatures

Commit-and-prove proof systems

As coins must be unforgeable, at their core lie digital signatures. To achieve anonymity, these must be hidden, which can be achieved via non-interactive zero-knowledge (NIZK) proofs of knowledge; if these proofs are re-randomizable, then they can not even be recognized by a past owner. We will

M-structure-preserving signatures

To prove knowledge of signatures, we require a scheme that is compatible with Groth-Sahai proofs [AFG + 10].

S.Setup(Gr), on input the bilinear group description, outputs signature parameters par S , defining a message space M. We require M ⊆ V n for some n.

S.KeyGen(par S ), on input the parameters par S , outputs the signing and the verification key (sk, vk).

We require that vk is composed of values in V.

S.Sign(sk, M ), on input a signing key sk and a message M ∈ M, outputs a signature Σ. We require that Σ is composed of values in V. The first equality also holds for ck ← C.Setup, since it is distributed like ck output by C.Setup.

Correctness of signing committed messages

Security properties

Mode indistinguishability: Let Gr ← BGGen(1 λ ); then the outputs of C.Setup(Gr) and the first output of C.SmSetup(Gr) are computationally indistinguishable.

Perfect zero-knowledge in hiding mode:

Let (ck, td) ← C.SmSetup(Gr), E ⊆ E and v 1 , . . . , v n ∈ V such that E(v 1 , . . . , v n ) = 1. For ρ 1 , . . . , ρ n $ ← -R the following are equivalently distributed: C.Cm(ck, v 1 , ρ 1 ), . . . , C.Cm(ck, v n , ρ n ), C.Prv ck, E, (v 1 , ρ 1 ), . . . , (v n , ρ n ) and C.ZCm(ck, ρ 1 ), . . . , C.ZCm(ck, ρ n ), C.SmPrv td, E, ρ 1 , . . . , ρ n .

Signature unforgeability (under chosen message attack):

No PPT adversary that is given vk output by S.KeyGen and an oracle for adaptive signing queries on messages M 1 , M 2 , . . . of its choice can output a pair (M, Σ), such that S.Verify(vk, M, Σ) = 1 and M / ∈ {M 1 , M 2 , . . . }.

Rerandomizable encryption schemes

In order to trace double-spenders, some information must be retrievable from the coin by the bank, so we encrypt it. Since coins must change appearance in order to achieve coin transparency (Def. 5.4), we must use rerandomizable encryption. In our e-cash scheme we will prove consistency of encrypted messages with values used elsewhere, and to produce such a proof, knowledge of part of the randomness is required; we therefore make this an explicit input of some algorithms, which thus are still probabilistic.

A rerandomizable encryption scheme consists of 4 poly-time algorithms:

E.KeyGen(Gr), on input the group description, outputs an encryption key ek and a corresponding decryption key dk.

E.Enc(ek, M, ν) is probabilistic and on input an encryption key ek, a message M and (partial) randomness ν outputs a ciphertext.

E.ReRand(ek, C, ν ), on input an encryption key, a ciphertext and some randomness, outputs a new ciphertext. If no randomness is explicitly given to E.Enc or E.ReRand then it is assumed to be picked uniformly.

E.Dec(dk, C), on input a decryption key and a ciphertext, outputs either a message or ⊥ indicating an error.

In order to prove statements about encrypted messages, we add two functionalities: E.Verify lets one verify that a ciphertext encrypts a given message M , for which it is also given partial randomness ν. This will allow us to prove that a commitment c M and a ciphertext C contain the same message.

For this, we require that the equations defining E.Verify are in the set E supported by C.Prv.

CHAPTER 2. PRELIMINARIES

This lets us define an equality proof π = (π, c ν ), where c ν is a commitment of the randomness ν, and π a proof that the values c M and c ν verify the equations of E.Verify(ek, •, •, C). In order to support rerandomization of ciphertexts, we define a functionality E.AdptPrf, which adapts a proof (π, c ν ) to a rerandomization. E.Verify(ek, M, ν, C), on input an encryption key, a message, randomness and a ciphertext, outputs a bit.

E.AdptPrf(ck, ek, c M , C, π = (π, c ν ), ν ), a probabilistic algorithm which, on input a commitment key, an encryption key, a commitment, a ciphertext, an equality proof (i.e., a proof and a commitment) and randomness, outputs a new equality proof.

Correctness properties

We require the scheme to satisfy the following correctness properties for all key pairs (ek, dk) ← E.KeyGen(Gr):

• For all M ∈ M and randomness ν we have:

E.Enc(ek, M, ν) = C if and only if E.Verify(ek, M, ν, C) = 1.
• For all M ∈ M and ν: E.Verify(ek, M, ν, C) = 1 implies E.Dec(dk, C) = M . (These two notions imply the standard correctness notion.)

• For all M ∈ M and randomness ν, ν , if C ← E.Enc(ek, M, ν) then the following are equally distributed: E.ReRand(ek, C, ν ) and E.Enc(ek, M, ν + ν ).

• For every ck ← C.Setup, every (ek, dk)

← E.KeyGen, M ∈ M and randomness ν, ν , ρ M , ρ ν , if we let c M ← C.Cm(ck, M, ρ M ) C ← E.Enc(ek, M, ν) c ν ← C.Cm(ck, ν, ρ ν ) π ← C.Prv ck, E.Verify(ek, •, •, C), (M, ρ M ), (ν, ρ ν )
then the following are equivalently distributed:

E.AdptPrf ck, ek, c M , ReRand(pk, C, ν ), (π, c ν ), ν and C.Prv(ck, E.Verify(ek, •, •, ReRand(ek, C, ν )), (M, ρ M ), (ν + ν , ρ ν )), c ν .

Security properties

We require two properties from rerandomizable encryption: the first one is the standard (strongest possible) variant of CCA security; the second one is a new notion, which is easier to achieve.

Replayable-CCA (RCCA) security. We use the definition from Canetti et al. [START_REF] Canetti | Relaxing chosen-ciphertext security[END_REF], formalized in Fig. 2.2.

Indistinguishability of adversarially chosen and randomized ciphertexts (IACR).

An adversary that is given a public key, chooses two ciphertexts and is then given the randomization of one of them cannot, except with a negligible advantage, distinguish which one it was given. The game is formalized in Fig. 2.2.

Definition 2.10.

For x ∈ {RCCA, IACR}, a rerandomizable encryption scheme is x-secure if Pr[Expt x A,1 (λ) = 1] -Pr[Expt x A,0 (λ) = 1] is negligible in λ for any PPT A. Expt RCCA A,b (λ): (ek, dk) ← E.KeyGen(1 λ ) (m 0 , m 1 ) ← A Dec(dk,•) (ek) C ← E.Enc(ek, m b ) b ← A GDec(•) (C) Return b GDec(C): m ← E.Dec(dk, C) If m ∈ {m 0 , m 1 } Return m Else return replay Expt IACR A,b (λ): (ek, dk) ← KeyGen(1 λ ) (C 0 , C 1 ) ← A(ek) C ← E.ReRand(ek, C b ) b ← A(ek, C) Return b

Double-spending tag schemes

We follow the general approach from [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF], in which the bank represents a coin in terms of its serial number sn = sn 0 . . . sn k , which grows with every transfer. In addition, a coin contains a tag tag = tag 1 . . . tag k , which enables tracing of double-spenders. The part sn i is chosen by a user when she receives the coin, while the tag tag i is computed by the sender as a function of sn i-1 and sn i and her secret key.

Baldimtsi et al. [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] show how to construct such tags in a way so they perfectly hide the user's identity, except when a user computes two tags with the same sn i-1 but different values sn i , in which case her identity can be computed from the two tags. Note that this precisely corresponds to double-spending the coin that ends in sn i-1 to two users that choose different values for sn i when receiving it.

We use the construction of [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF], which we first formally define and then show that its full strength had not been leveraged yet: in particular, we realize that the double-spending tag can also be used as method for users to authenticate the coin transfer. In earlier works [BCF + 11, BCFK15], at each transfer the spender computed a signature that was included in a coin, and that committed the user to the spending (and made her accountable in case of double spending). Our construction does not require any user signatures and thus gains in efficiency.

Furthermore, in [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] (there were no tags in [BCF + 11]), the malleable signatures took care of ensuring well-formedness of the tags, while we give an explicit construction. To be compatible with Groth-Sahai proofs, we define structure-preserving proofs of well-formedness for serial numbers and tags.

Syntax. An M-double-spending tag scheme is composed of the following 10 polynomial-time algorithms:

T.Setup(Gr), on input a group description, outputs the parameters par T (which is an implicit input to all of the following).

T.KeyGen(par T ), on input the parameters, outputs a tag key pair (sk, pk).

T.SGen(sk, n), the serial-number generation function, on input a secret key and a nonce n ∈ N (the nonce space), outputs a serial-number component sn and a proof sn-pf of well-formedness.

T.SGen init (sk, n) is a variant of T.SGen that also outputs a message M ∈ M. (SGen init is used for the first component of the serial number, which is signed by the bank using a signature scheme that requires messages to be in M.)

T.SVfy(pk, sn, sn-pf ), on input a public key, a serial number and a proof verifies that sn is consistent with pk by outputting a bit b.

T.SVfy init (pk, sn, M ), on input a public key, a serial number and a message in M, checks their consistency by outputting a bit b.

T.SVfy all , depending on the type of the input, runs T.SVfy init or T.SVfy.

CHAPTER 2. PRELIMINARIES

T.TGen(sk, n, sn), the double-spending tag function, takes as input a secret key, a nonce n ∈ N and a serial number, and outputs a double-spending tag tag ∈ T (the set of the double-spending tags) and a tag proof t-pf .

T.TVfy(pk, sn, sn , tag, t-pf ), on input a public key, two serial numbers, a double-spending tag, and a proof, checks consistency of tag w.r.t. the key and the serial numbers by outputting a bit b.

T.Detect(sn, sn , tag, tag , L), double-spending-detection, takes as input two serial numbers sn and sn , two tags tag, tag ∈ T and a list of public keys L and outputs a public key pk (of the accused user) and a proof Π.

T.VfyGuilt(pk, Π), the incrimination-proof verification function, takes as input a public key and a proof and outputs a bit b.

Correctness properties

For any double-spending tag scheme T = T.Setup, T.KeyGen, T.SGen, T.SGen init , T.SVfy, T.SVfy init , T.TGen, T.TVfy, T.Detect, T.VfyGuilt we require the following properties:

SN-identifiability: For all public tag keys pk 1 and pk 2 , all serial numbers sn and all X 1 and X 2 , which can be messages in M or SN proofs, if

T.SVfy all (pk 1 , sn, X 1 ) = T.SVfy all (pk 2 , sn, X 2 ) = 1 then pk 1 = pk 2 .

2-show extractability:

Let pk 0 , pk 1 and pk 2 be public tag keys, sn 0 , sn 1 and sn 2 be serial numbers, tag 1 and tag 2 be tags, sn-pf 1 and sn-pf 2 be SN proofs, t-pf 1 and t-pf 2 be tag proofs and X 0 be either an SN proof or a message in M. Let L be a set of tag public keys with pk 0 ∈ L. If

T.SVfy pk 1 , sn 1 , sn-pf 1 = T.SVfy pk 2 , sn 2 , sn-pf 2 = 1 T.TVfy pk 1 , sn 0 , sn 1 , tag 1 , t-pf 1 = 1 T.TVfy pk 2 , sn 0 , sn 2 , tag 2 , t-pf 2 = 1
T.SVfy all pk 0 , sn 0 , X 0 = 1 and sn 1 = sn 2 then T.Detect(sn 1 , sn 2 , tag 1 , tag 2 , L) efficiently extracts (pk 0 , Π) and we have T.VfyGuilt(pk 0 , Π) = 1.

Verifiability: For every n, n ∈ N , and after computing

• par T ← T.Setup(Gr)

• (sk, pk) ← T.KeyGen(Gr)

• (sk , pk ) ← T.KeyGen(Gr) • (sn, X) ← T.SGen(sk, n) or (sn, X) ← T.SGen init (sk, n) • (sn , sn-pf ) ← T.SGen(sk , n ) • (tag, t-pf ) ← T.TGen(sk, n, sn )
we have T.TVfy(pk, sn, sn , tag, t-pf ) = T.SVfy(pk, sn, X) = 1.

Bootability: It is impossible to find an SN message M and 2 different serial numbers sn 1 and sn 2 and two tag keys (distinct or not) pk

(1)

T , pk (2)
T such that:

T.SVfy init (pk (1)
T , sn 1 , M ) = T.SVfy init (pk (2)
T , sn 2 , M ) = 1.

2.5. PROOF OF LEMMA 2.9

27 Expt tag-anon A,b (λ): Gr ← BGGen(1 λ ) par T ← T.Setup(Gr) k := 0 (sk 0 , sk 1 ) ← A(par T ) b * ← A O 1 (sk b ),O 2 (sk b ,•,•) (par T , sk 0 , sk 1 ) Return (b = b * ) O 1 (sk): n $ ← -N ; T [k] := n; k := k + 1 (sn, sn-pf ) ← T.SGen(sk, n) Return sn. O 2 (sk, sn , i): If T [i] = ⊥, abort the oracle call n := T [i]; T [i] := ⊥ (tag, t-pf ) ← T.TGen(sk, n, sn ) Return tag

Security properties

Exculpability: This notion requires soundness of proofs, that is, one cannot produce a proof of a false statement. Let par T ← T.Setup and (sk, pk) ← T.KeyGen(par T ). Then we require that is computationally hard for an adversary given pk and black-box access to oracles O 1 (sk) and O 2 (sk, •, •) defined on the right of Fig. 2.3 to return a proof Π with T.VfyGuilt(pk, Π) = 1.

Tag anonymity: Finally, our anonymity notions for transferable e-cash should hold even against a malicious bank, which gets to see the serial numbers and double-spending tags for deposited coins, and the secret keys of the users. Thus, we require that as long as the nonce n is random and only used once, the serial numbers and tags reveal nothing about the user-specific values, such as sk and pk, that were used to generate them. The game is given in Fig. 2.3.

Definition 2.11 (Tag anonymity). A double-spending tag scheme is anonymous if

Pr[Expt tag-anon A,1 (λ) = 1] -Pr[Expt tag-anon A,0 (λ) = 1] is negligible in λ for any PPT A.

Proof of Lemma 2.9

We prove the statement for (q 1 , q 2 )-DLog; the proof for q-DLog follows analogously. We give a proof in Maurer's version of the GGM [START_REF] Ueli | Abstract models of computation in cryptography[END_REF], in which an adversary A gen can access elements from the groups G 1 , G 2 and G T only via abstract handles. These are maintained by the challenger in lists L 1 , L 2 , and L T , which correspond to the groups G 1 , G 2 , and G T , respectively. We define a slightly different model (the ideal one) in which one the challenger considers polynomials instead of group elements. For (q 1 , q 2 )-DLog, it means that the lists L 1 and L 2 initially contain the handles to the elements 1, Z, Z 2 , . . . , Z q 1 and 1, Z, Z 2 , . . . , Z q 2 ∈ Z p [Z], respectively, that correspond to the (q 1 , q 2 )-DLog challenge given to A gen . The challenger also samples z $ ← -Z * p , the solution, and we will argue that this value remains information-theoretically hidden from A gen .

The adversary is granted access to oracles of two types.

Oracles O i (•), for i ∈ {1, 2, T }, take as input two handles h 1 , h 2 ∈ L i for polynomials P 1 (Z), P 2 (Z) ∈ Z p [Z]
, respectively, and output a handle h for the polynomial P 1 (Z) + P 2 (Z); L i is accordingly updated with the handle h. Oracle O e (•), on input two handles h 1 ∈ L 1 and h 2 ∈ L 2 for P 1 (Z) and P 2 (Z), outputs the handle h T to the element P 1 (Z) • P 2 (Z) and updates L T accordingly.

In this game the adversary does not have access any information on z (z could be chosen at the end of the game), and thus has probability 1 p-1 .

CHAPTER 2. PRELIMINARIES

Following the standard argument in the generic group model proofs, we consider a so-called collision event E which occurs if there exist two distinct handles h 1 , h 2 ∈ L 1 ∪ L 2 ∪ L T that point to polynomials P 1 (Z) and P 2 (Z), respectively, such that P 1 (Z) = P 2 (Z), yet P 1 (z) = P 2 (z). Now have to determine how many this ideal game differs from the real one (in the generic group mode). We can upper bound the statistical disctance between these games by Pr(E).

Thus, to lower-bound the number of oracle interactions that are needed until A gen finds z, it suffices to lower-bound the time until E happens.

Analysis of Pr(E)

. Before E occurs, z is a uniformly random value and thus the probability that two computed elements are equal after t steps of computation (i.e., oracle calls) can be upper-bounded by the Schwartz-Zippel Lemma (Lemma 2.1). In particular, let P 1 (Z) and P 2 (Z) be distinct polynomials of degree at most 2q. Then Schwartz-Zippel upper-bounds the probability that P 1 (z) ≡ p P 2 (z) for a uniform element z ∈ Z * p by 2q/(p -1). As initially the set L 1 ∪ L 2 ∪ L T is of size q + 1 (where q := max{q 1 , q 2 }) and an oracle call by A gen adds at most one polynomial of degree at most q 1 + q 2 < 2q to one of the lists, there are at most t+q+1 2 such equations after t steps of computation. Thus, the probability of a collision occurring is at most

(t + q + 1) 2 • 2q/(2(p -1)) = (t + q + 1) 2 • q/(p -1).

Chapter 3

Classification of computational assumptions in the algebraic group model

This work was published in the proceedings of the 2020 CRYPTO Conference. It was completed with co-authors Georg Fuchsbauer, and Julian Loss.

Overview. In this chapter, we give a taxonomy of computational assumptions in the algebraic group model (AGM). We first analyze Boyen's Uber assumption family for bilinear groups and then extend it in several ways to cover assumptions as diverse as Gap Diffie-Hellman and LRSW. We show that in the AGM every member of these families is implied by the q-discrete logarithm (DL) assumption, for some q that depends on the degrees of the polynomials defining the Uber assumption.

Using the meta-reduction technique, we then separate (q + 1)-DL from q-DL, which yields a classification of all members of the extended Uber-assumption families. We finally show that there are strong assumptions, such as one-more DL, that provably fall outside our classification, by proving that they cannot be reduced from q-DL even in the AGM.

The Uber-Assumption Family

Boyen [START_REF] Boyen | The uber-assumption family (invited talk)[END_REF] extended the Uber-assumption framework he initially introduced with Boneh and Goh [START_REF] Boneh | Hierarchical identity based encryption with constant size ciphertext[END_REF]. We start with defining notions of independence for polynomials and rational fractions (of which polynomials are a special case):

Definition 3.1. Let - → R ∈ Z p (X 1 , . . . , X m ) r and W ∈ Z p (X 1 , . . . , X m ). We say that W is linearly dependent on - → R if there exist coefficients (a i ) r i=1 ∈ Z r p such that W = r i=1 a i R i .
We say that W is (linearly

) independent from - → R if it is not linearly dependent on - → R . Definition 3.2. Let - → R , - → S , - →
F and W be vectors of rational fractions from Z p (X 1 , . . . , X m ) of length r, s, f and 1, respectively. We say that W is ("bilinearly") dependent on (

- → R , - → S , - → F ) if there exist coefficients {a i,j }, {b i,j }, {c i,j } and {d k } in Z p such that W = r i=1 s j=1 a i,j R i S j + r i=1 r j=1 b i,j R i R j + s i=1 s j=1 c i,j S i S j + f k=1 d k F k .
We call the dependency of Type 2 if b i,j = 0 for all i, j and of Type 3 if b i,j = c i,j = 0 for all i, j. Else, it is of Type 1. We say that W is (Type-τ ) independent from (

- → R , - → S , - → F ) if it is not (Type-τ ) dependent on ( - → R , - → S , - → F ).
(Thus, W can be Type-3 independent but Type-2 dependent.)

Consider the Uber-assumption game in Fig. 3.1, which is parametrized by vectors of polynomials -→ R , -→ S and -→ F and polynomials R , S and F . For a random vector -→ x , the adversary receives the evaluation of the (vectors of) polynomials in the exponents of the generators g 1 , g 2 and g T ; its goal is to find the evaluation of the polynomials R , S and F at -→ x in the exponents. Note that we do not explicitly give the generators to the adversary. This is without loss of generality because we can always set

R 1 = S 1 = F 1 ≡ 1.
The game can be efficiently solved if one of the following conditions hold (where we distinguish the different types of bilinear groups and interpret all polynomials over Z p ):

(Type 1) If R is dependent on - → R and - → S , and S is dependent on - → R and - → S , and F is Type-1 dependent (Def. 3.2) on ( - → R , - → S , - → F ). (Type 2) If R is dependent on - → R and - → S , S is dependent on - → S , and F is Type-2 dependent (Def. 3.2) on ( - → R , - → S , - → F ). (Type 3) If R is dependent on - → R , S is dependent on - → S , and F is Type-3 dependent (Def. 3.2) on ( - → R , - → S , - → F ).
For example, in Type-2 groups, if R = i a i R i + i b i S i and S = 1, and

F = i j a i,j R i S i + i j c i,j S i S j , then from a challenge ( - → U, - → V, -→ W), one can easily compute a solution U := i U a i i • ψ( i V b i i ), V := g 2 , W := i j e(U i , V j ) a i,j • i j e(ψ(V i ), V j ) b i,j .
In our main theorem, we show that whenever the game in Fig. 3.1 cannot be trivially won, then for groups of Type τ ∈ {1, 2}, it can be reduced from q-dlog G 2 , and for Type-3 groups, it can be reduced from (q 1 , q 2 )-dlog G (for appropriate values of q, q 1 , q 2 ). To state the theorem for all types of groups, we first define the following non-triviality condition (which again we state for the more general case of rational fractions):

Definition 3.3 (Non-triviality). Let - → R ∈ Z p (X 1 , . . . , X m ) r , - → S ∈ Z p (X 1 , . . . , X m ) s , - → F ∈ Z p (X 1 , . . . , X m ) f , R , S , F ∈ Z p (X 1 , . . . , X m ). We say that the tuple ( - → R , - → S , - → F , R , S , F
) is non-trivial for groups of type τ , for τ ∈ {1, 2, 3}, if the following holds: R ,S ,F )-über problem is trivial to solve, even with a generic algorithm. In Theorem 3.5 we now show that if the tuple is non-trivial then the corresponding Uber assumption holds for algebraic algorithms, as long as a type of q-DLog assumption holds (whose type depends on the type of bilinear group).

• either R is linearly independent from - → R and - → S in case τ ∈ {1, 2}, R is linearly independent from - → R in case τ = 3; (τ .1) • or S is linearly independent from - → R and - → S in case τ = 1, S is linearly independent from - → S in case τ ∈ {2, 3}; (τ .2) • or F is Type-τ "bilinearly" independent (Def. 3.2) from ( - → R , - → S , - → F ). (τ .T) ( - → R , - → S , - → F , R , S , F )-über A alg G 01 (g 1 , g 2 ) $ ← -GenSamp ; g T ← e(g 1 , g 2 ) 02 - → x = (x 1 , . . . , x m ) $ ← -Z m p 03 - → U := (g R 1( -→ x ) 1 , . . . , g Rr( -→ x ) 1 ) 04 - → V := (g S 1( -→ x ) 2 , . . . , g Ss( -→ x ) 2 ) 05 -→ W := (g F 1( -→ x ) T , . . . , g F f ( -→ x ) T ) 06 (U , V , W ) ← A alg ( - → U, - → V, -→ W) 07 Return (U , V , W ) = (g R ( -→ x ) 1 , g S ( -→ x ) 2 , g F ( -→ x ) T ) Figure 3
- → R , - → S , - → F , R , S , F ) is trivial then the ( - → R , - → S , - → F ,
The (additive) security loss of the reduction depends on the degrees of the polynomials involved (as well as the group type and its order). E.g., in Type-3 groups, if R is independent of -→ R then the probability that the reduction fails is the maximum degree of R and the components of -→ R , divided by the order of G. In Type-1 and Type-2 groups, due to the homomorphism ψ, the loss depends on the maximum degree of R , -→ R and -→ S . Similar bounds hold when S is independent of -→ S (and -→ R for Type 1); and slightly more involved ones for the independence of F . If several of R , S and F are independent then the reduction chooses the strategy that minimizes the security loss.

Definition 3.4 (Degree of non-trivial tuple of polynomials). Let

( - → R , - → S , - → F , R , S , F ) be a non- trivial tuple of polynomials in Z p [X 1 , . . . , X m ]. Define d-→ R := max{deg R i } 1≤i≤r , d-→ S := max{deg S i } 1≤i≤s , d-→ F := max{deg F i } 1≤i≤f . We define the type-τ degree d τ of ( - → R , - → S , - → F , R , S , F ) as follows: • If (τ .1) holds, let d τ.1 := max{deg R , d-→ R , d-→ S } in case τ ∈ {1, 2} and d τ.1 := max{deg R , d-→ R } in case τ = 3. • If (τ .2) holds, let d τ.2 := max{deg S , d-→ R , d-→ S } in case τ = 1 and d τ.2 := max{deg S , d-→ S } in case τ ∈ {2, 3}. • If (τ .T) holds, let d τ.T := max{deg F , 2 d-→ R , 2 d-→ S , d-→ F } when τ = 1, d τ.T := max{deg F , d-→ R + d-→ S , 2 d-→ S , d-→ F } in case τ = 2 and d τ.T := max{deg F , d-→ R + d-→ S , d-→ F } in case τ = 3. If (τ, i) does not
- → R , - → S , - → F , R , S , F ) ∈ (Z p [X 1 , . . . , X m ]) r+s+f +3
be a tuple of polynomials that is non-trivial for type τ and

CHAPTER 3. CLASSIFICATION OF COMPUTATIONAL ASSUMPTIONS IN THE ALGEBRAIC GROUP MODEL define d-→ R := max{deg R i }, d-→ S := max{deg S i }, d-→ F := max{deg F i }. Let q, q 1 , q 2 be such that q ≥ max{d-→ R , d-→ S , d-→ F /2} as well as q 1 ≥ d-→ R , q 2 ≥ d-→ S and q 1 + q 2 ≥ d-→ F . If (Type 1) q-dlog G 1 or q-dlog G 2 is (ε, t)-secure in the AGM, (Type 2) q-dlog G 2 is (ε, t)-secure in the AGM, (Type 3) (q 1 , q 2 )-dlog G is (ε, t)-secure in the AGM, then ( - → R , - → S , - → F , R , S , F )-über G is (ε , t )-secure in the AGM with ε ≤ ε + dτ p-1 and t ≤ t + o 1 ,
where d τ is the maximal degree of (

- → R , - → S , - → F , R , S , F ), as defined in Def. 3.4, o 1 := o 0 + 2 + (2 log 2 (p) )((d-→ R + 1)r + (d-→ S + 1)s + (d-→ F + 1)f + d τ ) + rd-→ R + sd-→ S + f d-→ F with o 0 := d-→ R + d-→ F + 2
for Types 1 and 2, and o 0 := d-→ F + 1 for in Type 3.

Proof. We give a detailed proof for Type-2 bilinear groups and then explain how to adapt it to Types 1 and 3. For u ∈ Z p and i ∈ {1, 2, T } we let [u] i denote g u i . Let A alg be an algebraic algorithm against über G that wins with advantage ε in time t. We construct a generic reduction with oracle access to A alg , which yields an algebraic adversary B alg against q-dlog G 2 . There are three (non-exclusive) reasons for (

- → R , - → S , - → F , R
← -(Z * p ) m and - → v $ ← -Z m p , implicitly sets x i := y i z + v i mod p and computes - → U := [ - → R (x 1 , . . . , x m )] 1 , - → V := [ - → S (x 1 , . . . , x m )] 2 , -→ W := [ - → F (x 1 , . . . , x m )]
T from its q-DLog instance, the isomorphism ψ : G 2 → G 1 and the pairing e : G 1 × G 2 → G T . It can do so efficiently since the total degrees of the polynomials in -→ R , -→ S and -→ F are bounded by q, q and 2q respectively.

1 Next, B alg runs (U , V , W ) $ ← -A alg ( - → U, - → V, -→ W). Since A alg is algebraic, it also returns vectors and matrices - → µ , - → ν , - → ζ , - → δ , A = (α i,j ) i,j , Γ = (γ i,j ) i,j such that U = i U µ i i • i ψ(V i ) ν i (3.1a) V = i V η i i (3.1b) W = i j e U i , V j α i,j • i j e ψ(V i ), V j γ i,j • i W δ i i . (3.1c)
B alg then computes the following multivariate polynomial, which corresponds to the exponents of (3.1a):

P 1 ( - → X ) = R ( - → X ) -r i=1 µ i R i ( - → X ) -s i=1 ν i S i ( - → X ), (3.2) 1 E.g., B alg can compute [x q 1 ]1 = [(y1z + v1) q ]1 as i ψ(Zi) ( q i )y i 1 v q-i 1 and [x 2q 1 ]T as e i ψ(Zi) ( q i )y i 1 v q-i 1 , i Z ( q i )y i 1 v q-i 1 i
and similarly for terms in more variables.

which is non-zero because in Case (2.1) R is independent from -→ R and -→ S . From P 1 , it defines the univariate polynomial

Q 1 (Z) := P 1 (y 1 Z + v 1 , . . . , y m Z + v m ). (3.3) If Q 1 is
, then U = [R ( - → x )] 1 .
On the other hand,

U = i U µ i i • ψ( i V ν i i ) = i µ i R i ( - → x ) + i ν i S i ( - → x ) 1 .
Together, this means that P 1 ( -→ x ) ≡ p 0 and since

x i ≡ p y i z + v i , moreover Q 1 (z) ≡ p 0. By factoring Q 1 , reduction B alg finds thus the solution z.
It remains to bound the probability that B alg aborts in ( * ), that is, the event that 0

≡ Q 1 (Z) = P 1 (y 1 Z + v 1 , . . . , y m Z + v m ). Interpreting Q 1 as an element from (Z p [Y 1 , . . . , Y m , V 1 , . . . , V m ])[Z], Lemma 2.2 yields that its maximal coefficient is a polynomial Q max 1 in Y 1 , . . . , Y m
whose degree is the same as the maximal (total) degree d of P 1 . From P 1 ≡ 0 and P 1 ( -→ x ) = 0, we have d > 0.

We note that the values y 1 z, . . . , y m z are completely hidden from A alg because they are "onetime-padded" with v 1 , . . . , v m , respectively. This means that the values ( -

→ µ , - → ν ) returned by A alg are independent from - → y . Since - → y is moreover independent from R , - → R and - → S , it is also independent from P 1 , Q 1 and Q max 1 . The probability that Q 1 ≡ 0 is
d 2,1 p-1 . Case (2.2), that is, S is linearly independent from - → S , follows completely analogously, but with d = d 2.2 = max{d S , d-→ S }. Case (2.T), when F is type-2-independent of - → R , - → S and - →
F , is also analogous; we highlight the necessary changes: From A alg 's representation (A = (α i,j ), Γ = (γ i,j ),

- → δ ) ∈ Z r×s p × Z s×s p × Z f p for W (see (3.1c)), that is, W = i j e U i , V j α i,j • i j e ψ(V i ), V j γ i,j • i W δ i i = i j α i,j R i ( - → x )S j ( - → x ) + i j γ i,j S i ( - → x )S j ( - → x ) + i δ i F i ( - → x ) T . (3.4)
Analogously to (3.2) we define

P T ( - → X ) := F ( - → X ) -r i=1 s j=1 α i,j R i ( - → X )S j ( - → X ) -s i=1 s j=1 γ i,j S i ( - → X )S j ( - → X ) -f i=1 δ i F i ( - → X ), (3.5) which is of degree at most d 2.T := max{deg F , d-→ R + d-→ S , 2 • d-→ S , d-→ F }. Polynomial P T is non-zero by Type-2-independence of F (Def. 3.2). The reduction also computes Q T (Z) := P T (y 1 Z + v 1 , . . . , y m Z + v m ).
If A alg wins then W = [F ( -→ x )] T , which together with (3.4) implies that P T ( -→ x ) ≡ p 0 and thus Q T (z) ≡ p 0. Reduction B alg can find z by factoring Q T ; unless Q T (Z) ≡ 0, which by an analysis analogous to the one for case (2.1) happens with probability d2.T p-1 . (We detail the reduction for the case where W is independent in the proof of Theorem 3.9, which proves a more general statement.) Theorem 3.5 for Type-2 groups follows since Aq-dlog G 2 , B alg ≥ Aüber G, A alg -Pr[B alg aborts] and B alg follows the type of reduction that minimizes its abort probability to min

d 2.1 p-1 , d 2.2 p-1 , d 2.T p-1 = d 2 p-1 .
Groups of Type 1 and 3. The reduction for bilinear groups of Type 1 to q-dlog G 2 is almost the same proof. The only change is that for Case (1.T) the polynomial

P T in (3.5) has an extra term -r i=1 r j=1 β i,j R i ( - → X )R j ( - → X )
, because of the representation of W in Type-1 groups (see Def. 2.4); the degree of P T is then bounded by max{deg

F , 2 d-→ R , 2 d-→ S , d-→ F }. Analogously for Case (1.2), S can now depend on - → S as well as - → R .
The reduction for Type-1 groups to q-dlog G 1 is completely symmetric by swapping the roles of G 1 and G 2 and replacing ψ by φ.

The reduction for Type-3 groups relies on the (q 1 , q 2 )-dlog G assumption, as it requires

{[z i ] 1 } q 1 i=1 and {[z i ] 2 } q 2 i=1 to simulate {[R i ( - → x )] 1 } r i=1 and {[S i ( - → x )] 2 } s i=1
. without using any homomorphism φ or ψ. Apart from this, the proof is again analogous. (We treat the Type-3 case in detail in the proof of Theorem 3.9.) In Section 3.9 we detail the analysis of the running times of these reductions. Using Lemmas 2.5 and 2.9 we obtain the following corollary to Theorem 3.5:

Corollary 3.6. Let G be of type τ and ( - → R , - → S , - → F , R , S , F ) be non-trivial for τ of maximal degree d τ . Then ( - → R , - → S , - → F , R , S , F )-über G is (o+o 1 +1+q) 2 q p-1 + dτ p-1 , o -secure in the generic bilinear group model.
Comparison to previous GGM results. Boneh, Boyen and Goh [BBG05, Theorem A.2] claim that the decisional Uber assumption for the particular case r = s and f = 0 is (o+2r+2) 2 q 2p , o -secure in the generic group model, and with the same reasoning, one can obtain the more general bound

(o+r+s+f +2) 2 q 2p
, o . Note that the loss in their bound is only linear in the maximum degree while ours cubic. Our looser bound is a result of our reduction, whereas Boneh, Boyen and Goh prove their bound directly in the GGM. 2

The Flexible Uber Assumption

Boyen [START_REF] Boyen | The uber-assumption family (invited talk)[END_REF] generalizes the Uber assumption framework to flexible assumptions, where the adversary can define the target polynomials (R , S and F in Fig. 3.1) itself, conditioned on the solution not being trivially computable from the instance, for non-triviality as in Def. 3.3. In Sect. 3.4 we consider this kind of flexible Uber assumption in our generalization to rational fractions and thereby cover assumptions like q-strong Diffie-Hellman [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF].

For polynomials, we generalize this further by allowing the adversary to also (adaptively) choose the polynomials that constitute the challenge. The adversary is provided with an oracle that takes input a value i ∈ {1, 2, T } and a polynomial P ( -→ X ) of the adversary's choice, and returns g

P ( -→ x ) i
, where -→ x is the secret value chosen during the game. The adversary then wins if it returns polynomials (R * , S * , F * ), which are independent from its queries, and g

R * ( -→ x ) 1 , g S * ( -→ x ) 2
, g

F * ( -→ x ) T
. The game for this flexible Uber assumption is specified in Fig. 3.2. Theorem 3.7. Let m ≥ 1, let G be a bilinear-group of type τ ∈ {1, 2, 3} and consider an adversary

A alg in game m-f-über G . Let d 1 , d 2 , d T , d * 1 , d * 2 , d * T be such that A alg 's queries (i, P ( - → X )) satisfy 3.3. THE RUBER ASSUMPTION 35 m-f-über A alg G 01 Q 1 , Q 2 , Q T ← ∅ 02 (g 1 , g 2 ) $ ← -GenSamp ; g T ← e(g 1 , g 2 ) 03 - → x = (x 1 , . . . , x m ) $ ← -Z m p 04 ((U * , V * , W * ), (R * , S * , F * )) $ ← -A O(•,•) alg () 05 Return (U * , V * , W * ) = (g R * ( -→ x ) 1 , g S * ( -→ x ) 2 , g F * ( -→ x ) T ) ∧ (Q 1 , Q 2 , Q T , R * , S * , F * ) non-trivial for type of G O(i, P ( - → X )) 06 Q i = Q i ∪ {P } 07 Return g P ( -→ x ) i
* ≤ d * 1 , deg S * ≤ d * 2 , deg F * ≤ d * T . Let q, q 1 , q 2 be such that q ≥ max{d 1 , d 2 , d T /2} as well as q 1 ≥ d 1 , q 2 ≥ d 2 and q 1 + q 2 ≥ d T . If (Type 1) q-dlog G 1 or q-dlog G 2 is (ε, t)-secure in the AGM, (Type 2) q-dlog G 2 is (ε, t)-secure in the AGM, (Type 3) (q 1 , q 2 )-dlog G is (ε, t)-secure in the AGM, then m-f-über G is (ε , t )-secure in the AGM with ε ≤ ε + dτ p-1 and t ≈ t,
where d τ is as in Def. 3.4 after the following replacements:

d-→ R ← d 1 , d-→ S ← d 2 , d-→ F ← d F , deg R ← d * 1 , deg S ← d * 2 and deg F ← d * T .
Proof sketch. Inspecting the proof of Theorem 3.5, note that the values

[R i ( - → x )] 1 , [S i ( - → x )] 2 and
[F i ( -→ x )] T need not be known in advance and can be computed by the reduction at any point, as long as the degrees of R i and S i are bounded by q and those of F i by 2q. The adversary could thus specify the polynomials via oracle calls and the reduction can compute U i , V i and F i on the fly. Likewise, the polynomials P 1 , P 2 and P T (and their univariate counterparts which the reduction factors) are only defined after A alg stops; therefore, R , S and F , from which they are defined, need only be known then. The proof of Theorem 3.5 is thus adapted to prove Theorem 3.7 in a very straightforward way.

The Ruber Assumption

Reconsider the Uber assumption in Fig. 3.1, but now let

- → R , - → S , - → F , R , S
and F be rational fractions over Z p rather than polynomials. We will show that even this generalization of the Uber assumption is implied by q-DLog assumptions. We start with introducing some notation. We view a rational fraction as defined by two polynomials, its numerator and its denominator, and assume that the fraction is reduced. For a rational fraction R ∈ Z p (X 1 , . . . , X m ), we denote its numerator by R and its denominator by Ř. That is R, Ř ∈ Z p [X 1 , . . . , X m ] are such that R = R/ Ř. As rational fractions are not defined everywhere, we modify the game from Fig. 3.1 so the adversary wins should the experiment choose an input -→ x for which one of the rational fractions is not defined.

The rational-fraction uber game is given in Fig. 3.3.

CHAPTER 3. CLASSIFICATION OF COMPUTATIONAL ASSUMPTIONS IN THE ALGEBRAIC GROUP MODEL

( - → R , - → S , - → F , R , S , F )-rüber A alg G // R i = Ri / Ři , for Ri , Ři ∈ Z p [ - → X ], etc 01 (g 1 , g 2 ) $ ← -GenSamp ; g T ← e(g 1 , g 2 ) 02 - → x = (x 1 , . . . , x m ) $ ← -Z m p 03 If for some i: Ři ( - → x ) ≡ p 0 or Ši ( - → x ) ≡ p 0 or Fi ( - → x ) ≡ p 0 then return 1 04 If Ř ( - → x ) ≡ p 0 or Š ( - → x ) ≡ p 0 or F ( - → x ) ≡ p 0 then return 1 05 - → U := (g R 1( -→ x ) 1 , . . . , g Rr( -→ x ) 1 ) ; - → V := (g S 1( -→ x ) 2 , . . . , g Ss( -→ x ) 2
) ; -→ W := (g

F 1( -→ x ) T , . . . , g F f ( -→ x ) T ) 06 (U , V , W ) $ ← -A alg ( - → U, - → V, -→ W) 07 Return (U , V , W ) = (g R ( -→ x ) 1 , g S ( -→ x ) 2 , g F ( -→ x ) T ) Figure
(Type 1) • If (1.1) holds, let d 1.1 := d den + ďR + ď-→ R -→ S + max{d R , d-→ R , d-→ S } • if (1.2) holds, let d 1.2 := d den + ďS + ď-→ R -→ S + max{d S , d-→ R , d-→ S } • if (1.T) holds, d 1.T := d den + ďF + ď-→ R -→ S -→ F + ď-→ R -→ S + max{d F , 2d-→ S , 2d-→ R , d-→ F } (Type 2) • If (2.1) holds, let d 2.1 := d den + ďR + ď-→ R -→ S + max{d R , d-→ R , d-→ S } • if (2.2) holds, let d 2.2 := d den + ďS + ď-→ S + max{d S , d-→ S } • if (2.T) holds, d 2.T := d den + ďF + ď-→ R -→ S -→ F + ď-→ S + max{d F , 2d-→ S , d-→ R + d-→ S , d-→ F } (Type 3) • If (3.1) holds, let d 3.1 := d den + ďR + ď-→ R + max{d R , d-→ R } • if (3.2) holds, let d 3.2 := d den + ďS + ď-→ S + max{d S , d-→ S } • if (3.T) holds, d 3.T := d den + ďF + ď-→ R -→ F + ď-→ S + max{d F , d-→ R + d-→ S , d-→ F } 3
- → R , - → S , - → F , R , S , F ) ∈ (Z p (X 1 , . . . , X m )) r+s+f +3
be a tuple of rational fractions that is non-trivial for type τ (Def. 3.3). Let q, q 1 and q 2 be such that

q ≥ ď-→ R -→ S -→ F + max{d-→ R , d-→ S , d-→ F /2} and q 1 ≥ ď-→ R -→ F + d-→ R and q 2 ≥ ď-→ S + d-→ S as well as q 1 + q 2 ≥ ď-→ R -→ F + ď-→ S + d-→ F . If (Type 1) q-dlog G 1 or q-dlog G 2 is (ε, t)-secure in the AGM, (Type 2) q-dlog G 2 is (ε, t)-secure in the AGM, (Type 3) (q 1 , q 2 )-dlog G is (ε, t)-secure in the AGM, then ( - → R , - → S , - → F , R , S , F )-rüber G , as defined in Fig. 3.3, is (ε , t )-secure in the AGM with ε ≤ ε + dτ p-1 and t ≈ t,
where d τ is the maximal degree of (

- → R , - → S , - → F , R , S , F ), as defined in Def. 3.8.
The proof extends the ideas used to prove Theorem 3.5 by employing a technique from [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF]. Consider a group of Type 1 or 2. The reduction computes D := Den(

- → R - → S - → F )
, a least common multiple of the denominators of the instance. Given a q-DLog instance g 2 , g z 2 , g z 2 2 , . . ., it first implicitly sets x i := y i z + v i mod p, then it checks whether any denominator evaluates to zero at -→ x (this entails the additive loss d den ). Then it computes a new random generator

h 2 := g D(y 1 z+v 1 ,...,ymz+vm) 2
and h 1 := ψ(h 2 ). For rational fractions S i = Ŝi / Ši , it then uses h 1 , h 2 to compute the Uber challenge elements h

S i ( -→ x ) 2 as g S( -→ x ) 2
for the polynomial S( -→ X ) := ( Ŝi • D/ Ši )( -→ X ), and likewise for R i and F i . This explains the lower bound on q in the theorem statement. When the adversary returns a group element h R ( -→ x ) i so that R is non-trivial, then from the algebraic representations of this element we can define a polynomial (which with overwhelming probability is non-zero) that vanishes at z. The difference here is that we expand by the denominator of R in order to obtain a polynomial. The degree of this polynomial is bounded by the values in Def. 3.8, which also bound the failure probability of the reduction. In Type-3 groups, the reduction can set

h 1 := g Den( -→ R -→ F )( -→ x ) 1 and h 1 := g Den( -→ S )( -→ x ) 2
, which leads to better bounds. We detail this case in our proof of Theorem 3.9, which can be found in Section 3.10.

The Ruber Assumption for Flexible Targets

For rational fractions, we can also define a flexible generalization, where the adversary can choose the target polynomials R , S and F in Fig. 3.1 itself, conditioned on the tuple ( R ,S ,F ) being non-trivial. The game is specified in Fig. 3.4. This extension covers assumptions such as the q-strong DH assumption by Boneh and Boyen [START_REF] Boneh | Short signatures without random oracles and the SDH assumption in bilinear groups[END_REF], which they proved secure in the generic group model. A q-SDH adversary is given (g i , g z i , g z 2 i , . . . , g z q i ) for i = 1, 2 and must compute (g

- → R , - → S , - → F ,
(z+c) -1 1
, c) for any c ∈ Z p \ {-z} of its choice. This is an instance of the flexible game in Fig. 3.4 when setting m = 1, r = s = q + 1, f = 0 and R i (X) = S i (X) = X i-1 , and the adversary returns R * (X) = 1/(X + c), S * (X) = F * (X) = 0. Theorem 3.10 (DLog implies flexible-target Uber for rational fractions in the AGM). Let G be a bilinear group of type τ ∈ {1, 2, 3} and let

( - → R , - → S , - → F ) ∈ (Z p (X 1 , . . . , X m )
) r+s+f be a tuple of rational fractions.

( - → R , - → S , - → F )-f-rüber A alg G 01 (g 1 , g 2 ) $ ← -GenSamp ; g T ← e(g 1 , g 2 ) 02 - → x = (x 1 , . . . , x m ) $ ← -Z m p 03 If for some i: Ři ( - → x ) ≡ p 0 or Ši ( - → x ) ≡ p 0 or Fi ( - → x ) ≡ p 0 then return 1 04 - → U := (g R 1( -→ x ) 1 , . . . , g Rr( -→ x ) 1 ) ; - → V := (g S 1( -→ x ) 2 , . . . , g Ss( -→ x ) 2
) ; -→ W := (g

F 1( -→ x ) T , . . . , g F f ( -→ x ) T ) 05 ((U * , V * , W * ), (R * , S * , F * )) $ ← -A alg ( - → U, - → V, -→ W) 06 Return (U * , V * , W * ) = g R * ( -→ x ) 1
, g

S * ( -→ x ) 2
, g ), respectively. Proof sketch. Much in the way the proof of Theorem 3.5 is adapted to Theorem 3.7, Theorem 3.10 is proved similarly to Theorem 3.9. Since P 1 , P 2 and P T are only defined once the adversary returns its rational fractions R * , S * , F * , they need not be known in advance. (Note that, unlike for polynomials (Theorem 3.7), the instance (

F * ( -→ x ) T ∧ ( - → R , - → S , - → F ,
- → R , - → S , - → F )-f-rüber (Fig. 3.4) and let d * 1 , d * 2 , d * T , ď * 1 , ď * 2 , ď * T be such that A alg 's outputs R * , S * , F * satisfy deg R * ≤ d * 1 , deg S * ≤ d * 2 , deg F * ≤ d * T , deg Ř * ≤ ď * 1 , deg Š * ≤ ď * 2 and deg F * ≤ ď * T . Let q, q 1 and q 2 be such that q ≥ ď-→ R -→ S -→ F + max{d-→ R , d-→ S , d-→ F /2} and let q 1 ≥ ď-→ R -→ F + d-→ R and q 2 ≥ ď-→ S +d-→ S and q 1 +q 2 ≥ ď-→ R -→ F + ď-→ S +d-→ F , where ď-→ R = ď( R1 / Ř1 ,..., Rr/ Řr) = deg LCM{ Ř1 , . . . , Řr }. If (Type 1) q-dlog G 1 or q-dlog G 2 is (ε, t)-secure in the AGM, (Type 2) q-dlog G 2 is (ε, t)-secure in the AGM, (Type 3) (q 1 , q 2 )-dlog G is (ε, t)-secure in the AGM, then ( - → R , - → S , - → F )-f-rüber G is (ε , t )-
- → R , - → S , - → F
) does have to be fixed, as the reduction uses it to set up the generators h 1 and h 2 .) A difference to Theorem 3.10 is the value d den in the security loss, which is now smaller since the experiment need not check the denominators of the target fractions.

Uber Assumptions with Decisional Oracles

In this section we show that we can provide the adversary, essentially for free, with an oracle that checks whether the logarithms of given group elements satisfy any polynomial relation. In more detail, the adversary is given access to an oracle that takes as input a polynomial P ∈ Z p [X 1 , . . . , X n ] and group elements Y 1 , . . . , Y n (from any group G 1 , G 2 or G T ) and checks whether P (log Y 1 , . . . , log Y n ) ≡ p 0. Decisional oracles can be added to any type of Uber assumption;

3.5. UBER ASSUMPTIONS WITH DECISIONAL ORACLES 39 ( - → R , - → S , - → F )-f-drüber A alg G 01 (g 1 , g 2 ) $ ← -GenSamp ; g T ← e(g 1 , g 2 ) 02 - → x = (x 1 , . . . , x m ) $ ← -Z m p 03 If for some i: Ři ( - → x ) ≡ p 0 or Ši ( - → x ) ≡ p 0 or Fi ( - → x ) ≡ p 0 04 then return 1 05 - → U := (g R 1( -→ x ) 1 , . . . , g Rr( -→ x ) 1 ) 06 - → V := (g S 1( -→ x ) 2 , . . . , g Ss( -→ x ) 2 ) 07 -→ W := (g F 1( -→ x ) T , . . . , g F f ( -→ x ) T ) 08 ((U * , V * , W * ), (R * , S * , F * )) $ ← -A O(•,•) alg ( - → U, - → V, -→ W) 09 Return (U * , V * , W * ) = (g R * ( -→ x ) 1 , g S * ( -→ x ) 2 , g F * ( -→ x ) T ) ∧ ( - → R , - → S , - → F , R * , S * , F * ) non-trivial for type of G O(P ( - → X ), (Y 1 , . . . , Y n )) 10 For i = 1, . . . , n do 11 let ι i ∈ {1, 2, T } s.t. Y i ∈ G ι i 12 y i ← log gι i Y i
13 Return P ( -→ y ) ≡ p 0 Figure 3.5: Algebraic game for the flexible-targets Uber assumption with decisional oracles for concreteness, we extend the most general variant from the previous section. The game f-drüber ("d" for decisional oracles) is defined in Fig. 3.5. This extension covers assumptions such as Gap Diffie-Hellman (DH) [START_REF] Okamoto | The gap-problems: A new class of problems for the security of cryptographic schemes[END_REF], where the adversary must solve a DH instance while being given an oracle that checks whether a triple

(Y 1 , Y 2 , Y 3 ) is a DH tuple, i.e., Y log Y 2 1 = Y 3 .
This oracle is a special case of the one in Fig. 3.5, when called with P (X 1 , X 2 , X 3 ) := X 1 X 2 -X 3 . Theorem 3.11 (DLog implies flexible-target Uber for rational fractions with decisional oracles in the AGM). The statement of Theorem 3.10 holds when f-rüber is replaced by f-drüber.

Proof sketch. The reduction B alg from ( -→ R , -→ S , -→ F )-f-drüber to q-DLog (or (q 1 , q 2 )-DLog) works as for Theorem 3.10 (as detailed in the proof of Theorem 3.9), except that B alg must also answer A alg 's oracle queries, which we describe in the following for Type-3 groups.

As for Theorem 3.10, B alg , on input (

- → Y, - → Z ) with Y i = [z i ] 1 and Z j = [z j ] 2 , for 0 ≤ i ≤ q 1 and 0 ≤ j ≤ q 2 , computes LCMs of denominators D := Den( - → R - → S - → F ), D 1 := Den( - → R - → F )
and

D 2 := Den( - → S ). It picks - → y $ ← -(Z * p ) m and - → v $ ← -Z m p , implicitly sets x i := y i z + v i mod p and checks if D( - → x ) ≡ p 0.
If so, the reduction derives the corresponding univariate polynomial and finds z.

Otherwise it computes h

1 := [D 1 ( - → x )] 1 , h 2 := [D 2 ( - → x )] 2 (note that D 1 ( - → x ) and D 2 ( - → x ) are non-zero), U i = [(D 1 • R i )( - → x )] 1 , V i = [(D 2 • S i ( - → x )] 2 and W i = [(D 1 • D 2 • F i )( - → x )] T .
Consider a query O(P, (Y 1 , . . . , Y n )) for some n and P ∈ Z p [X 1 , . . . , X n ], and

Y i ∈ G ι i for ι i ∈ {1, 2, T }. Since A alg is algebraic, it provides representations of the group elements Y i with respect to its input ( - → U, - → V, -→ W); in particular, for each Y i , depending on the group, it provides - → µ i or - → η i or (A i , - → δ i ) such that: (Y i ∈ G 1 ) Y i = r j=1 U µ i,j j = r j=1 µ i,j (D 1 • R j )( - → x ) 1 =: Q i (z) 1 (Y i ∈ G 2 ) Y i = s j=1 V η i,j j = s j=1 η i,j (D 2 • S j )( - → x ) 2 =: Q i (z) 2 (Y i ∈ G T ) Y i = r j=1 s k=1 e(U j , V k ) α i,j,k • f j=1 W δ i,j j = r j=1 s k=1 α i,j,k (D 1 • R j )( - → x ) (D 2 • S j )( - → x ) + f j=1 δ i,j (D 1 • D 2 • F j )( - → x ) T =: Q i (z) T ,
where D 1 • R j as well as D 2 • S j and D 1 • D 2 • F j are multivariate polynomials (not rational fractions) and Q i is the polynomial defined by replacing X i by

y i Z + v i . Let D i (Z) be defined from D i ( - → X ) analogously. Then we have log gι i Y i = Q i (z) and furthermore log hι i Y i = Q i (z)/D ι i (z)
, where

D T := D 1 • D 2 .
To answer the oracle query, B alg must therefore determine whether the function P (Q 1 /D i 1 , . . . , Q n /D in ) vanishes at z. Since D 1 (z), D 2 (z) ≡ p 0, this is the case precisely when

P := D d 1 • D d 2 • P (Q 1 /D i 1 , . . . , Q n /D in ) vanishes at z,
where d is the maximal degree of P . Note that P is a polynomial. The reduction distinguishes 3 cases:

1. P ≡ 0: in this case, the oracle replies 1.

2. P ≡ 0: in this case, B alg factorizes P to find its roots z 1 , . . ., checks whether Z 1 = g z i for some i. If this is the case, it stops and returns the solution z i to its (q 1 , q 2 )-DLog instance.

3. Else, the oracle replies 0.

Correctness of the simulation is immediate, since the correct oracle reply is 1 if and only if P (z) ≡ p 0.

The Flexible Gegenuber Assumption

In this section, we show how to extend the Uber framework even further, by letting the adversary generate its own generators (for the outputs), yielding the GeGenUber assumption. Consider the LRSW assumption [START_REF] Lysyanskaya | Pseudonym systems[END_REF] in Type-1 bilinear groups: given (X = g x , Y = g y ) (which can be viewed as a signature verification key [START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF]) and an oracle, which on input (a message) m ∈ Z p returns (a signature) (g a , g ay , g a(x+mxy) ) for a random a $ ← -Z p , it is infeasible to return (a signature on a fresh message) (g a * , g a * y , g a * (x+m * xy) , m * ) for any a * and m * different from the queried values. Since the adversary need not return the value a * , this cannot be cast into the Uber framework. Associating the values a 1 , . . . , a chosen by the signing oracle to formal variables A 1 , . . . , A , in the Uber framework -→ X would correspond to (X, Y, A 1 , . . . , A ) and signing queries to the polynomials A i , A i Y and A i X + m i A i XY . Now the adversary can choose a fresh generator g * := g a * and must return ((g

* ) R * i ( -→ X ) ) 3 i=1 for R * 1 ≡ 1, R * 2 = Y and R * 3 = X + m * XY
for some m * ∈ Z * p of its choice. Our last generalization now extends the flexible Uber assumption from Sect. 3.2 by letting the adversary generate its own generators U, V and W of G 1 , G 2 and G T , resp., and return polynomials R * , S * and F * , as well as (U R * ( -→ x ) , V S * ( -→ x ) , W F * ( -→ x ) ). The game m-gegenüber is defined in Fig. 3.6. This additional freedom for the adversary induces a necessary change in the definition of non-triviality, as illustrated by the following simple (univariate) example: after the challenger chooses x $ ← -Z p , the adversary makes queries R 1 := X and R 2 := X 3 and receives U 1 and U 2 . For all Uber assumptions so far, the polynomial R * := X 2 would be considered non-trivial. However, in game gegenüber the adversary could return

U := U 1 = g x and U * := U 2 = g x 3 = U R * (x) .
Whereas until now the target polynomial R * was not allowed to be a linear combination of the queried polynomials P 1 , . . . , P (or of products of such polynomials, depending on the group types), for the Gegenuber assumption we also need to exclude fractions of such linear combinations (such as X 3 /X in the example above) to thwart trivial attacks.

For a family E of polynomials, we denote by Span(E) all linear combinations of elements of E, which we extend to fractions as FrSp(E) := P / P ( P , P ) ∈ Span(E) × (Span(E) \ {0}) .

Moreover, by

E 1 * E 2 we denote the set {P 1 • P 2 | (P 1 , P 2 ) ∈ E 1 × E 2 }.

THE FLEXIBLE GEGENUBER ASSUMPTION

m-gegenüber

A alg G 01 Q 1 , Q 2 , Q T ← ∅ 02 (g 1 , g 2 ) $ ← -GenSamp ; g T ← e(g 1 , g 2 ) 03 - → x = (x 1 , . . . , x m ) $ ← -Z m p 04 (U, V, W, U * , V * , W * ), (R * , S * , F * ) $ ← -A O(•,•) alg () 05 Return U = 1 ∧ V = 1 ∧ W = 1 ∧ (U * , V * , W * ) = (U R * ( -→ x ) , V S * ( -→ x ) , W F * ( -→ x ) ) ∧ (Q 1 , Q 2 , Q T , R * , S * , F * ) gegenuber-non-trivial for type of G O(i, P ( - → X )) 06 Q i = Q i ∪ {P } 07 Return g P ( -→ x ) i Figure 3
.6: Algebraic game for the flexible Gegenuber assumption Definition 3.12 (Non-triviality for Gegenuber assumption). Let Q 1 , Q 2 and Q T be sets of polynomials and let R * , S * and F * be polynomials. We say that

(Q 1 , Q 2 , Q T , R * , S * , F *
) is gegenubernon-trivial for groups of type τ , if the following holds: • If (τ.T ) holds, let d τ.T := max{1, deg

• Either R * / ∈ FrSp(Q 1 ∪ Q 2 ) for τ ∈ {1, 2} and R * / ∈ FrSp(Q 1 ) for τ = 3, (τ.1) • or S * / ∈ FrSp(Q 1 ∪ Q 2 ) for τ = 1 and S * / ∈ FrSp(Q 2 ) for τ ∈ {2, 3}, (τ.2) • or F * / ∈ FrSp(Q T ∪ (Q 1 ∪ Q 2 ) * (Q 1 ∪ Q 2 )) for τ = 1 (1.T ) F * / ∈ FrSp(Q T ∪ (Q 1 ∪ Q 2 ) * Q 2 ) for τ = 2 (2.T ) F * / ∈ FrSp(Q T ∪ (Q 1 * Q 2 )) for τ = 3. (3.
F * } • max{2 d 1 , 2 d 2 , d T } for τ = 1 d τ.T := max{1, deg F * } • max{d 1 + d 2 , 2 d 2 , d T } for τ = 2, d τ.T := max{1, deg F * } • max{d 1 + d 2 , d T } for τ = 3. If (τ, i) does not hold, set d τ,i := ∞. Define d τ := min{d τ.1 , d τ.2 , d τ.T }.
Note that for all Uber variants, the adversary only outputs one element per group G i , which is without loss of generality, as a vector of group elements would be non-trivial if at least one component is non-trivial. We defined the Gegenuber assumption analogously, so one might wonder how this covers LRSW, where the adversary must output group elements corresponding to two polynomials Y and X + m * XY . The reason is that LRSW holds even if the adversary only has to output the latter polynomial (the former is required to verify the validity of a solution using the pairing): In the GGM this follows from LRSW being an instance of Gegenuber, Theorem 3.14 (see below for both) and Lemmas 2.5 and 2.9.

To show that LRSW is gegenuber-non-trivial, consider the set of queries an adversary can make, namely:

Q := 1, X, Y, {A i , A i Y, A i X + m i A i XY } i=1 .

CHAPTER 3. CLASSIFICATION OF COMPUTATIONAL ASSUMPTIONS IN THE ALGEBRAIC GROUP MODEL

To prove that the stronger variant of LRSW satisfies non-triviality as defined in Def. 3.12, we show that for 0 = m * / ∈ {m 1 , . . . , m }: R * := X + m * XY / ∈ FrSp(Q). For the sake of contradiction, assume that for some P , P ∈ Span(Q), P ≡ 0: (X + m * XY ) P = P .

(3.6)

Since P ∈ Span(Q), its total degree in X and Y is at most 2, which implies that P must be of degree 0 in X and Y . We can thus write P as η + j=1 α j A j for some η and -→ α . Since X is a factor of the left-hand side of (3.6), P cannot have terms without X and must therefore be of the form P = ξX + j=1 µ j A j (X + m j XY ) for some ξ and -→ µ . Equation (3.6) becomes thus

(X + m * XY ) η + j=1 α j A j = ξX + j=1 µ j A j (X + m j XY ) .
By equating coefficients, we get: η = ξ (from coeff. X) and m * η ≡ p 0 (from XY ) and for all j ∈ [1, ]: α j = µ j (from A j X) and α j m * ≡ p µ j m j (from A j XY ). Since m * = 0, we have η = ξ = 0. Furthermore, if α j = 0 for some j, then m j = m * , meaning it was not a valid solution. If α j = 0 for all j then P ≡ 0, which shows such P and P do not exist and thus X + m * XY / ∈ FrSp(Q). Another assumption covered by this definition is the AWFCDH assumption 2.8 in type 2 (and therefore, it implies the hardness for the assumption in type 3): It corresponds to the case R = R * = S * = X and U * = ψ(V * ). Theorem 3.14. Let m ≥ 1, let G be a bilinear group of type τ ∈ {1, 2, 3} and let A alg be an adversary in game m-gegenüber

G . Let d 1 , d 2 , d T , d * 1 , d * 2 , d * T be such that A alg 's queries (i, P ( - → X )) satisfy deg P ≤ d i and its output satisfies deg R * ≤ d * 1 , deg S * ≤ d * 2 , deg F * ≤ d * T .
Let q, q 1 , q 2 be such that q ≥ max{d 1 , d 2 , d T /2}, as well as q 1 ≥ d 1 , q 2 ≥ d 2 and q 1 + q 2 ≥ d T . If (Type 1) q-dlog G 1 or q-dlog G 2 is (ε, t)-secure in the AGM, (Type 2) q-dlog G 2 is (ε, t)-secure in the AGM, The proof can be found in Section 3.11. It is an adaptation of the one for the flexible uberassumption, which adapts the proof of Theorem 3.5. We highlight the main difference for non-triviality of type (2.1). Recall that in the proof Theorem 3.5, the adversary returns a solution U and its algebraic representation so that (3.1a) holds. From this and the fact that U = [R ( -→ x )] 1 , we derived the polynomial P 1 in (3.2), which is non-zero by non-triviality.

(Type 3) (q 1 , q 2 )-dlog G is (ε, t)-secure in the AGM, then gegenüber G is (ε , t )-secure in the AGM with ε ≤ ε + dτ p-
In the proof of Theorem 3.14, the adversary also outputs a new generator U, whose algebraic representation yields a polynomial

Q ∈ Span(Q 1 ∪ Q 2 ) so that U = [Q( - → x )] 1 . For a valid solution U * , we thus have U * = [R * ( - → x ) • Q( - → x )] 1 .
On the other hand, the representation of U * yields

U * = [Q * ( - → x )] 1 for some Q * ∈ Span(Q 1 ∪ Q 2 ). We thus have that P 1 ( - → X ) := R * ( - → X ) • Q( - → X ) -Q * ( - → X ) vanishes at - → x . By non-triviality, R * / ∈ FrSp(Q 1 ∪ Q 2 )
, which implies P 1 ≡ 0, so the reduction can find the roots of P 1 (y 1 Z + x 1 , . . . , y n Z + x n ) and solve q-DLog.

3.7. SEPARATION OF (q + 1)-DL FROM q-DL 3.7 Separation of (q + 1)-DL from q-DL Now that we have shown that every Uber assumption falls into a (minimal) class of assumptions that are equivalent to q-DLog, we show that these classes can be separated according to their parameter q. We prove that, assuming that q-DLog is hard, there does not exist an algebraic reduction from q-DLog to (q + 1)-DLog. In particular, we show that if there exists a reduction R alg that has access to a (q + 1)-DLog (algebraic) adversary A alg and can solve q-DLog, then there exists a meta-reduction that uses R alg to break q-DLog. In the following, we use the notation R alg (A alg ) to denote that R alg has complete access to A alg 's internal state. In particular, R alg is allowed to rewind A alg to any point of an execution and run A alg on any choice of random coins as many times as it wants.

Theorem 3.15. Let G i be a group of prime order p. There exists an algorithm M such that the following holds. Let R alg be an algebraic algorithm s.t. for every algorithm A alg that (t, )-breaks (q + 1)-dlog

G i , B = R alg (A alg ) is an algorithm that (t , )-breaks q-dlog G i . If t ≥ 2 (2q + 1) log 2 p then M R alg (t , )-breaks q-dlog G i .
We start with a proof overview. Consider a reduction R alg , which on input a q-DLog instance (g, g x , . . . , g x q ) can run an algebraic adversary A alg multiple times on (q + 1)-DLog instances (Z, Z y , . . . , Z y q+1 ); that is, R alg can choose a new generator Z and a new problem solution y. Since R alg is algebraic, it outputs a representation of the group elements composing its (q + 1)-DLog instance in terms of the received q-DLog instance. We distinguish two cases: if (a) y is independent from x then the representation reveals y, which means that a meta-reduction M can simulate a successful A alg to R alg , and the latter must thus find x. On the other hand, if (b) y depends on x, then this yields a non-trivial equation in x, which the meta-reduction can solve and thereby (without needing to simulate A alg ) solve the q-DLog instance.

To simplify the probability analysis, we let M simulate A alg even when R alg behaves as in the second case (as it can compute y from x). To correctly argue about the probability distributions, we ensure that any malformed instance provided by the algebraic reduction R alg is detected. We will use the following lemma in the proof of Theorem 3.15: Lemma 3.16. Let q ≥ 1, let F ∈ Z p (X) and let 0 ≡ P ∈ Z p [X] be of degree at most q. If F q+1 •P is a polynomial and of degree at most q, then F is constant.

Proof. Let F , F ∈ Z p [X] be coprime such that F = F / F . Then F q+1 and F q+1 are coprime as well. From this and the premise that F q+1 • P/ F q+1 is a polynomial, we get that F q+1 divides P , and thus (q + 1) • deg F ≤ deg P . Since the latter is at most q, we have deg F = 0. Furthermore, we assumed that q ≥ deg(F q+1 • P ) = (q + 1) • deg F + deg P , and thus deg F = 0. Together, this means F is constant.

Proof of Theorem 3.15. Let R alg be an algebraic algorithm s.t. for every algorithm A alg that (t, )breaks (q + 1)-dlog G i , B = R alg (A alg ) is an algorithm that (t , )-breaks q-dlog G i . In the following, we describe a meta-reduction M s.t. M R alg (t , )-breaks q-dlog G i . M(g, X 1 , . . . , X q ): Run R alg on the received q-DLog instance (g, g x , . . . , g x q ). Whenever R alg runs adversary A alg on (q+1)-DLog input (Z 0 , Z 1 , . . . , Z q+1 ), do the following. Let -→ z i = (z i,0 , . . . , z i,q ) for 0 ≤ i ≤ q + 1 be the representation vectors for Z 0 , . . . , Z q+1 provided by R alg ; that is, Z i = q j=0 (g x j ) z i,j . If Z 0 = 1 then return ⊥.

( * )

CHAPTER 3. CLASSIFICATION OF COMPUTATIONAL ASSUMPTIONS IN THE ALGEBRAIC GROUP MODEL

Else define P i (X) := q j=0 z i,j X j for 0 ≤ i ≤ q + 1 and (3.7)

Q i := P i+1 P 0 -P i P 1 for 0 ≤ i ≤ q.

(3.8)

M now distinguishes two cases:

(a) Q i ≡ 0 for all i ∈ [0, q]: Then (as we argue below) P 1 /P 0 ≡ c, that is, a constant polynomial. M returns c as A alg 's output.

(b) For some k ∈ [0, q]: Q k ≡ 0: Compute the roots x 1 , . . . of Q k and check if for some j: g x j = X 1 . If not, then return ⊥ as A alg 's output. ( * * ) Else let y := P 1 (x j )/P 0 (x j ) mod p. (1 = Z 0 = g P 0 (x j ) , thus P 0 (x j ) ≡ p 0.) If for some i ∈ [1, q + 1] : Z i = Z y i 0 , return ⊥ as A alg 's output.

( * * * ) Else return y.

Correctness of simulation.

We now argue that M always correctly simulates an adversary A alg that solves (q + 1)-DLog if it received a correct instance, and returns ⊥ otherwise. Consider the case where R alg provides a valid (q + 1)-DLog instance, that is Z 0 = 1 and

∃ y ∈ Z * p ∀ i ∈ [1, q + 1] : Z i = Z y i 0 .
(3.9) By (3.7), we have Z i = g P i (x) for all i. Since Z 0 = 1, M does not stop in line ( * ) and P 0 (x) ≡ p 0. Moreover, from (3.9) we have y ≡ p P 1 (x)/P 0 (x) and

P i+1 (x) ≡ p P 1 (x)/P 0 (x) • P i (x), (3.10)
in other words, Q i (x) ≡ p 0 for all i ∈ [0, q]. In case (a), Q i ≡ 0, and thus, letting F := P 1 /P 0 , we have (by definition (3.8)) P i+1 = F • P i for all i, and by induction:

∀ i ∈ [0, q + 1] :

P i = F i • P 0 ,
and in particular P q+1 = F q+1 • P 0 . Since P q+1 and P 0 are polynomials of degree at most q, by Lemma 3.16 we get F ≡ c for c ∈ Z p . The meta-reduction M thus returns c ≡ p F (x) ≡ p P 1 (x)/P 0 (x) ≡ p y.

In case (b), since Q k ≡ 0 but, by (3.10), Q k (x) ≡ p 0, the meta-reduction finds x and M does not stop in line ( * * ) and neither in line ( * * * ), since y ≡ p P 1 (x)/P 0 (x). Now consider the case that R alg sends a malformed instance: if Z 0 is not a generator then A alg returns ⊥ in line ( * ). Assume Z 0 is a generator (and thus P 0 (x) ≡ p 0), but (3.9) is not satisfied. Using the algebraic representations of Z 0 , . . . , Z q+1 , this is equivalent to

∀ y ∈ Z * p ∃ k ∈ [1, q + 1] : P k (x) ≡ p y k P 0 (x). ( 3

.11)

We first show that the meta-reduction M goes to case (b): Indeed, if Q i ≡ 0 for all i ∈ [0, q], then P i+1 (x) ≡ p P 1 (x)/P 0 (x) • P i (x) for all i and, by induction, P i (x) ≡ p (P 1 (x)/P 0 (x)) i • P 0 (x), which, setting y := P 1 (x)/P 0 (x) mod p, contradicts (3.11).

Let k ∈ [0, q] be such that Q k ≡ 0. If x is not among the roots of Q k , then M returns ⊥ in line ( * * ). Otherwise, it sets y := P 1 (x)/P 0 (x) mod p. If for some i ∈ [1, q + 1]: P i (x) ≡ p y i P 0 (x) then M returns ⊥ in line ( * * * ). If not then this contradicts (3.11). Therefore, the simulation will return ⊥ on invalid inputs.

For the simulation of A alg the meta-reduction needs to compute at most 2q + 1 exponentiations, each of which require at most 2 log 2 p group operations using square and multiply. The simulation of A alg is thus perfect and takes at most t steps. The meta-reduction M succeeds in winning q-dlog G i whenever B = R alg (A alg ) wins q-dlog G i . Therefore, we obtain

Pr q-dlog M G i = 1 = Pr q-dlog B G i = 1 ≥ ε .
Moreover, the running time of M is that of B, i.e., t . This completes the proof.

A similar result can be shown for (q 1 , q 2 )-dlog G , that is, (q 1 , q 2 )-dlog G is not implied by (q 1 , q 2 )-dlog G if q 1 > q 1 or q 2 > q 2 .

Separation of 2-One-More DL from q-DL

We conclude with showing that "one-more"-discrete logarithm (OMDL) assumptions fall outside of our q-DLog taxonomy. While it is known that there is no black-box reduction from DLog to OMDL [START_REF] Bresson | Separation results on the "one-more" computational problems[END_REF], we show that there is no algebraic reduction either, even one for algebraic adversaries.

To obtain the strongest possible impossibility result, we show that for no q ∈ N, there exists an algebraic reduction from q-DLog (a stronger assumption than DLog) to 2-OMDL (the weakest variant of OMDL assumptions), unless q-DLog is easy. The game for 2-OMDL is depicted in Fig. 3.7. The proof uses the same high-level idea as for Theorem 3.17. If the representation of the group elements the reduction gives to the adversary is independent of its own q-DLog challenge, then the meta-reduction can directly simulate the adversary. Else, they depend on the q-DLog challenge in a way that allows the meta-reduction to derive a q-DLog solution. Compared to the previous section, we now restrict the algebraic reduction to only have black-box access (according to our notion of black-box) to the adversary. This is because a reduction that can choose the random coins of the adversary in a non-uniform (adaptive) way can make the simulation of the adversary by our meta-reduction fail.

We need to define the adversary's behavior, that is, its oracle call, beforehand; in particular, it must not depend on the type of representations obtained from the reduction, which makes the proof more complicated and restricts the simulation to adversaries that can fail with negligible probability. The adversary, after receiving a 2-OMDL challenge (Y 0 , Y 1 , Y 2 ), makes a query (Y r 1 1 Y r 2 2 ) for random r 1 , r 2 to its DLog oracle and then returns the 2-OMDL solution (log Y 0 Y 1 , log Y 0 Y 2 ). We now show how the meta-reduction simulates this adversary.

Since the reduction is algebraic, it provides with its 2-OMDL instance representations -→ z i = (z i,0 , . . . , z i,q ) in terms of its q-DLog challenge (g, g x , . . . , g x q ), such that log g Y i ≡ p q j=0 z i,j x j . From the reply y to the adversary's single oracle query, we get the following equation: 0

= log g (Y r 1 1 Y r 2 2
) -log g Y y 0 ≡ p q j=0 r 1 z 1,j + r 2 z 2,j -yz 0,j x j . The q-DLog challenge x is thus the root of the polynomial with coefficients a j := (r 1 z 1,j + r 2 z 2,j -yz 0,j ) mod p, and the meta-reduction can find x if one of these coefficients is non-zero. Using x, it can then compute log g Y i for all i from the representations and from that the OMDL solution (log

Y 0 Y 1 , log Y 0 Y 2 ).
If, on the other hand, a j = 0 for some j then by plugging in the definition of y, we get another polynomial which vanishes at x. We then show that, due to the randomizers r 1 and r 2 , with overwhelming probability, the coefficients of this polynomial are non-zero -unless for some c 1 , c 2 we have -

→ z 1 = c 1 - → z 0 and - → z 2 = c 2 - → z 0 . But in this case (c 1 , c 2 )
is the solution to the 2-OMDL instance and the meta-reduction can therefore finish the simulation of the adversary.

Theorem 3.17. Let G i be a group of prime order p. There exists an algorithm M such that the following holds: Let R alg be an algebraic reduction s.t. for every algorithm A alg that (t, )-breaks 2-omdl

G i , B = R A alg
alg is an algorithm that (t , )-breaks q-dlog G i . If t ≥ (6 + 2q) log 2 p + 1 and ≤ 1 -1/p then M R alg (t , )-breaks q-dlog G i .

2-omdl

A alg G i 00 Q ← 0 01 g $ ← -GenSamp i 02 y 1 , y 2 $ ← -Z * p 03 (y * 1 , y * 2 ) $ ← -A O(•) alg g, g y 1 , g y 2 04 Return (y * 1 , y * 2 ) = (y 1 , y 2 ) O(Z) 05 if Q = 0 then 06 Q ← 1
B = R A alg
alg is an algorithm that (t , )-breaks q-dlog G i . We first specify a hypothetical algebraic adversary A alg which (t = (6 + 2q)

• log 2 p + 1, = 1 -1/p)-breaks 2-OMDL: on input (Y 0 , Y 1 , Y 2 ), if Y 0 is not a generator, it returns ⊥.
Else, it chooses two uniform values r 1 , r 2 $ ← -Z p and queries its oracle

O(•) on Y r 1 1 Y r 2 2 , providing representation (0, r 1 , r 2 ) in basis (Y 0 , Y 1 , Y 2 ). If it does not obtain the correct answer log Y 0 Y r 1 1 Y r 2 2 , it returns ⊥. Else it returns the 2-OMDL solution log Y 0 Y 1 and log Y 0 Y 2 with probability 1 -1/p.
We now construct a meta-reduction M, s.t. M R alg (t , )-breaks q-dlog G i , as follows. On input a q-dlog G i instance (g, g x , . . . , g x q ), the meta-reduction runs R alg on (g, g x , . . . , g x q ). Every time R alg invokes 2-OMDL adversary A alg on a challenge (Y 0 , Y 1 , Y 2 ), M simulates A alg as follows.

If Y 0 is not a generator, it returns ⊥. Since R alg is algebraic, along with (Y 0 , Y 1 , Y 2 ), it provides corresponding representation vectors -→ z i = (z i,0 , . . . , z i,q ) ∈ Z q+1 p for i ∈ [0, 2] such that

Y i = q j=0 (g x j ) z i,j = g q j=0 z i,j x j for i ∈ [0, 2] . (3.12)
Let k be such that z 0,k = 0 (which exists, since Y 0 = 1). The meta-reduction chooses

r 1 , r 2 $ ← -Z p and queries O(Y r 1 1 Y r 2 2 ) to obtain y. If Y y 0 = Y r 1 1 Y r 2 2 then M returns ⊥.
Otherwise, let d i,j := z i,k z 0,j -z i,j z 0,k mod p a j := yz 0,j -r 1 z 1,j -r 2 z 2,j mod p for 1 ≤ i ≤ 2 and 1 ≤ j ≤ q .

M distinguishes three cases and simulates A alg accordingly:

(a) d i,j = 0 for all i, j: in this case, M computes (modulo p) z 1,k z -1 0,k and z 2,k z -1 0,k , which A alg returns as the OMDL solution (we argue correctness below).

(b) a j = 0 for some j: in this case, M factors the polynomial with coefficients a 0 , . . . , a q . If x is among its roots then M computes the following modulo p and lets A alg return it: q j=0 z 1,j x j q j=0 z 0,j x j -1 and q j=0 z 2,j x j q j=0 z 0,j x j -1 (3.13)

(since (log g Y 1 )(log g Y 0 ) -1 , (log g Y 2 )(log g Y 0 ) -1 ≡ p (log Y 0 Y 1 , log Y 0 Y 2 )
, by (3.12), this is thus the OMDL solution).

(c) For the remaining case, let i * , j * be such that d i * ,j * = 0. In this case, M factors the polynomial with coefficients d i * ,0 , . . . , d i * ,q . If x is among its roots then A alg returns the values from (3.13). Otherwise M returns ⊥.

3.9. RUNNING TIME OF THE GENERIC REDUCTION OF THEOREM 3.5

47

When R alg stops and returns x then M also stops and returns x.

We now show that the meta-reduction M correctly simulates every run of A alg that R alg invokes, in particular, that A alg solves the OMDL instance with probability at least 1 -1/p. First note that

Y y 0 = Y r 1 1 Y r 2 2
, which together with (3.12) yields: 0 ≡ p q j=0 (yz 0,j -r 1 z 1,j -r 2 z 2,j )x j ≡ p q j=0 a j x j =: P-→ a (x) .

(3.14) (where P-→ a is the polynomial with coefficients (a 0 , . . . , a q )).

In Case (a), we have that (z 1,k z -1 0,k , z 2,k z -1 0,k ) is the OMDL solution since for i = 1, 2:

Y z i,k z -1 0,k 0 (3.12) = g q j=0 z i,k z -1 0,k z 0,j x j d i,j =0 = g q j=0 z i,j x j (3.12) = Y i .
In Case (b), the polynomial P-→ a defined in (3.14) is non-zero. Since by (3.14), x is one of its roots, M can find it and use it to compute log Y 0 Y i via (3.13).

In Case (c), we have a k = 0 and thus (by definition of a k ):

yz 0,k ≡ p r 1 z 1,k + r 2 z 2,k . (3.15)
Multiplying (3.14) by z 0,k we get q j=0 (yz 0,k z 0,j -r 1 z 1,j z 0,k -r 2 z 2,j z 0,k )x j ≡ p 0 , which, when substituting yz 0,k by the right-hand side of (3.15), yields

r 1 q j=0 (z 1,k z 0,j -z 1,j z 0,k )x j + r 2 q j=0 (z 2,k z 0,j -z 2,j z 0,k )x j ≡ p 0 .
Using d i,j ≡ p z i,k z 0,j -z i,j z 0,k , this can be written as

r 1 q j=0 d 1,j x j + r 2 q j=0 d 2,j x j ≡ p 0 . (3.16)
Recall that in Case (c), for some i * , j * : d i * ,j * = 0. If D := q j=0 d i * ,j x j ≡ p 0, then M finds x by factoring P-→ d i * and thus finishes the simulation. In the remaining case we have D ≡ p 0; moreover, the values x and -→ d i * are independent of r i * , which was chosen after the reduction (implicitly) defined -→ d i * . Equation (3.16), that is, r i * D ≡ p -r 3-i * q j=0 d 3-i * ,j x j , thus only holds with probability 1/p. The meta-reduction therefore makes A alg return ⊥ on correct inputs with probability at most 1/p.

Finally, we show that the simulation of A alg takes at most t steps. Computing Y y 0 , Y r 1 1 , and Y r 2 2 via square and multiply requires 3 • 2 log 2 (p) group operations, and computing Y r 1 1 • Y r 2 2 takes one. Checking if the roots of the polynomial q i=0 a i X i (in Case (b)) or q j=0 d i * ,j X j (in Case (c)) are equal to x requires q • 2 log 2 (p) group operations.

M succeeds in winning q-dlog G i whenever B alg = R A alg alg wins q-dlog G i . Therefore, we obtain

Pr q-dlog M G i = 1 = Pr q-dlog B G i = 1 ≥ ε .
Moreover, the running time of M is that of B, i.e., t . This completes the proof.

Running Time of the Generic Reduction of Theorem 3.5

Fact 3.18. Let G a group of order p. The square-and-multiply algorithm in G takes as input a group element X ∈ G and a scalar a ∈ Z p and returns X a after computing at most 2 log(p) group operations.

Analysis. We give an upper bound on the running time of computation, in terms of bilinear group operations, of the reduction B in Theorem 3.5. Let o exp denote the number of group operations required to compute an exponentiation. First, B computes the "core" elements, that is,

g z k T for 0 ≤ k ≤ d-→ T and g z k 1 for 0 ≤ k ≤ d-→ R
in Types 1 and 2, which requires d-→ T + 1 computations of e and (for Types 1 and 2) d-→ R + 1 computations of the morphism ψ.

Let i ∈ {1, . . . , r}, j ∈ {1, . . . , s}, and k ∈ {1, . . . , f }. Then we denote

R i (y 1 Z + x 1 , . . . , y m Z + x m ) = d-→ R =0 λ R i , Z , S j (y 1 Z + x 1 , . . . , y m Z + x m ) = d-→ S =0
λ S j , Z , and

F k (y 1 Z + x 1 , . . . , y m Z + x m ) = d-→ F =0 λ F k , Z .
Next, B computes the monomials g z

1 λ R i , = g λ R i , z i 1
, for all ∈ {0, . . . , d-→ R }, as well as g z

2 λ S j , = g λ S j , z 2
for ∈ {0, . . . , d-→ S }, and

g z T λ F k , = g λ F k , z T for ∈ {0, . . . , d-→ F }. This requires at most rd-→ R + sd-→ S + f d-→ F + 3 o exp group operations.
Finally, B computes, for all i ∈ {0, . . . , r}, all j ∈ {1, . . . , s}, and k ∈ {1, . . . , f }:

d-→ R =0 g λ R i , z 1 = g R i (y 1 z+x 1 ,...,ymz+xm) 1 , d-→ S =0 g λ S j , z 2 = g S j (y 1 z+x 1 ,...,ymz+xm) 2
, and

d-→ F =0 g λ F k , z T = g F k (y 1 z+x 1 ,...,ymz+xm) T , which requires rd-→ R + sd-→ S + f d-→ F group operations.
This concludes the computation of A alg 's input. After computing Q 1 (or Q 2 or Q T depending on the case) from A alg 's output, and its roots z 1 , . . . , reduction B verifies g z i ?

= g z . Since the polynomial has at most d τ roots, this last step requires at most d τ • o exp group operations.

We can therefore upper-bound the number of group operations performed by

B A by t + o 1 with o 1 := o 0 + 2 + (d-→ R + 1)r + (d-→ S + 1)s + (d-→ F + 1)f + d τ o exp + rd-→ R + sd-→ S + f d-→ F with o 0 := d-→ R + d-→ F + 2
for Types 1 and 2, and o 0 := d-→ F + 1 for Type 3. By applying Fact 3.18, we obtain the time bound claimed in Theorem 3.5.

Proof of Theorem 3.9

We will use the following lemma in the proof of Theorem 3.9. Whereas in the proof of Theorem 3.5 we focused on Type-2 groups, for the sake of variation, we give the details for Type-3 groups, and then explain what changes for Types 1 and 2. Again, for i ∈ {1, 2, T }, we denote g u i by [u] i for u ∈ Z p . Let A alg be an algebraic algorithm against rüber G , defined by a tuple (

Lemma 3.19. Let n be an integer, (P

i ) n i=1 ∈ (Z p [X 1 , . . . , X m ]) n and - → x ∈ Z m p . Then P i ( - → x ) ≡ p 0 for some i ∈ [1, n] if
- → R , - → S , - → F , R , S , F
) of (vectors of) rational fractions, that wins with advantage ε in time t. We construct an algebraic adversary B alg against (q 1 , q 2 )-dlog G . Depending on why the tuple is non-trivial (conditions (3.1), (3.2) and/or (3.T) in Def. 3.3), B alg uses a different strategy, minimizing d 3 in Def. 3.8.

We detail the most complex case, which is (3.T); that is,

F is Type-3 independent from ( - → R , - → S , - → F ). Adversary B alg (g 1 , Y 1 , . . . , Y q 1 , g 2 , Z 1 , . . . , Z q 2 ): On input a (q 1 , q 2 )-DLog instance with Y i = [z i ] 1 and Z i = [z i ] 2 , reduction B alg simulates rüber G for A alg .
It first computes a least common multiple

D := Den( - → R - → S - → F R S F ) of the denominators of - → R , - → S , - → F , R , S , F . It then picks random values - → y $ ← -(Z * p ) m and - → v $ ← -Z m p and uses them to implicitly define x i := y i z + v i mod p. If D (Z) := D(y 1 Z + v 1 , . . . , y m Z + v m ) is the zero polynomial, it aborts. ( * )
Else, for each root z i of D , the reduction checks whether g z i 1 = Y 1 ; if such z i exists, it stops the simulation and outputs z i .

( )

If B alg has not stopped then D( -→ x ) ≡ p 0. It now computes a least common multiple

D 1 := Den( - → R - → F ) of the denominators of - → R and - → F and D 2 := Den( - → S ).
From its (q 1 , q 2 )-DLog instance, it then computes h 1 := g

D 1 ( -→ x ) 1 , h 2 := g D 2 ( -→ x ) 2
. Note that for all i ∈ {1, 2}, h i = 1 (since D i is a divisor of D, and D( -→ x ) ≡ p 0).

For 1 ≤ i ≤ r, B alg computes

U i := [( Ri •D 1 / Ři )( - → x )] 1 = h R i ( -→ x ) 1
(where D 1 / Ři is a polynomial by construction of D 1 ). This can be computed from Y 1 , . . . , Y q 1 , since

q 1 ≥ deg(D 1 ) + d-→ R . Likewise, for 1 ≤ i ≤ s, B alg computes V i := [( Ŝi • D 2 / Ši )( - → x )] 2 = h S i ( -→ x ) 2
from Z 1 , . . . , Z q 2 . Finally, B alg computes e(g 1 , g 2 ) z i = [z i ] T for 1 ≤ i ≤ q 1 + q 2 from its instance, from which it then computes

W i := [D 2 • Fi • D 1 / Fi ( - → x )] T = e(h 1 , h 2 ) F i ( -→ x ) for 1 ≤ i ≤ f . With these values, B alg runs (U , V , W ) $ ← -A alg ( - → U, - → V, -→ W), which also returns representa- tions - → µ for U , - → η for V and (A, - → δ )
for W (so that (3.1) holds with ν i = γ i,j = 0 for all i, j).

B alg defines the following polynomial:

P T := F • D 1 • D 2 • F -r i=1 s j=1 α i,j R i S j -f i=k δ k F k . (3.17)
Note that P T is indeed a polynomial, because F • F , as well as

D 1 • R i , D 2 • S j and D 1 • F k
for all i, j, k are all polynomials.

From P T , the reduction defines P T (Z) := P T (y 1 Z + v 1 , . . . , y m Z + v m ). If P T is the zero polynomial then B alg aborts. ( * * )

Else, it factors P T to obtain its roots z 1 , . . . If for one of them we have

g z i 1 = Y 1 , then B alg returns z i . ( )
We analyze B alg 's success probability. First note that B alg solves the DLog challenge if it stops in line ( ) and it fails if it aborts in line ( * ). Otherwise, B alg perfectly simulates game rüber (Fig. 3.3), as the values x i are uniformly distributed in Z p , and the tests in lines 03 and 04 in rüber are all done: For some i:

Ři ( - → x ) ≡ p 0 or Ši ( - → x ) ≡ p 0 or Fi ( - → x ) ≡ p 0, or Ř ( - → x ) ≡ p 0 or Š ( - → x ) ≡ p 0 or F ( - → x ) ≡ p 0 if
W = e(h 1 , h 2 ) F ( -→ x ) = D 1 ( - → x )D 2 ( - → x )F ( - → x ) T . (3.18)
On the other hand, from A alg 's representation (A, -→ δ ) of W and from the definitions of U i , V j and W k we have:

W = i j e U i , V j α i,j • k W δ k k = i j α i,j ( Ri • D 1 / Ři )( - → x ) ( Ŝj • D 2 / Šj )( - → x ) + k δ k (D 2 • Fk • D 1 / Fk )( - → x ) T . (3.19)
Equating the representations of W in (3.18) and (3.19) in base e(g 1 , g 2 ) yields

D 1 • D 2 • F -i j α i,j Ri • D 1 / Ři • Ŝj • D 2 / Šj + k δ k D 2 • Fk • D 1 / Fk ( - → x ) ≡ p 0 . (3.20)
Multiplying the above by F ( -→ x ) yields P T ( -→ x ) ≡ p 0 and since x i ≡ p y i z + v i , we have P T (z) ≡ p 0 as well. By factoring P T , reduction B alg finds thus the solution z.

We have shown that unless B alg aborts in lines ( * ) or ( * * ), it finds the (q 1 , q 2 )-DLog solution whenever A alg wins rüber. In the remainder of the proof we bound the probability that B alg aborts. It aborts if and only if the following polynomial is zero:

Q(Z) := (D • P T )(Z) = (D•P T ) (y 1 Z + v 1 , . . . , y m Z + v m ).
It thus suffices to upper-bound the probability that the coefficient of maximal degree of this polynomial is zero. By Lemma 2.2, this coefficient can be represented as a polynomial Q max in variables (Y 1 , . . . , Y m ) that is of the same degree as D • P T , which we bound as follows (recall that d den = deg D; cf. Def. 3.8):

deg(D • P T ) ≤ d den + deg F + deg D 1 + deg D 2 + max{deg F , deg R i + deg S j , deg F k } 1≤i≤r,1≤j≤s,1≤k≤f = d den + ďF + ď-→ R -→ F + ď-→ S + max{d F , d-→ R + d-→ S , d-→ F } = d 3.T
As the values y 1 z, . . . , y m z are completely hidden from A alg (they are "one-time-padded" with

v 1 , . . . , v m , resp.), the values (A, - → δ ) returned by A alg are independent from - → y . Since - → y is moreover independent from F , - → R , - → S and - →
F , it is also independent from P T , D, Q and Q max . The probability that Q ≡ 0 is thus upper-bounded by the probability that Q max ( -→ y ) ≡ p 0 when evaluated at the random point -→ y . By Lemma 2.1 (Schwartz-Zippel), the probability that Q max ( -→ y ) ≡ p 0 is thus upper-bounded by d 3.T p-1 . We turn to the remaining cases (3.1) and (3.2), which follow similarly, except that P T in (3.17) is replaced by different polynomials P . Moreover, we can optimize the loss of the security reduction, by reducing the degree of P . Note that the two properties which are used in the proof are:

• P is a non-zero polynomial, and • if A alg wins the game then P ( -→ x ) ≡ p 0.

3.10. PROOF OF THEOREM 3.9

51

In Case (3.1), that is, when R is linearly independent from

- → R , from A alg 's output U = h R ( -→ x ) 1 = [D 1 ( - → x ) R ( - → x )] 1 and its representation - → µ of U = i U µ i i = [ i ( Ri • D 1 / Ři )( - → x )
] 1 , we get that the following function vanishes at -→ x (which corresponds to (3.20) above):

D 1 • R -i µ i Ri • D 1 / Ř .
Multiplying this by Ř yields a polynomial. In contrast to case (3.T), we can moreover divide by D 1 /Den( -→ R ) and still obtain a polynomial. We thus define:

P 1 := Ř • Den( - → R ) • R -r i=1 µ i R i .
Since P 1 is of degree at most ďR + ď-→ R + max{d R , d-→ R }, the probability of B alg aborting is d 3.1 p-1 . For Case (3.2), from A alg 's representation -→ η of V , we analogously define

P 2 := Š • Den( - → S ) • S -s i=1 η i S i ,
which is of degree at most ďS + ď-→ S + max{d S , d-→ S } = d 3.2 . The theorem for Type-3 groups now follows because

Adv (q 1 , q 2 )-dlog G,B alg ≥ Adv rüber G,A alg -Pr[B alg aborts]
and B alg follows the strategy that minimizes its abort probability to min

d 3.1 p-1 , d 3.2 p-1 , d 3.T p-1 = d 3 p-1 .
Groups of Type 1 and 2. The reductions for bilinear groups of Types 1 and 2 to q-dlog G 2 work analogously; the main difference is that we can only redefine g 2 as h 2 , since h 2 defines h 1 = ψ(h 2 ). This means that instead of D 1 and D 2 as in the proof above, we define D 1,2 := Den(

- → R - → S - → F ) and set h 2 := g D 1,2 ( -→ x ) 2
. For Type-2 groups, let ( -→ µ , -→ ν ), -→ η and (A, Γ, -→ δ ) be A alg 's representations of U , V and W , respectively. Then B alg defines the polynomials P 1 , P 2 and P T as follows:

P 1 := Ř • Den( - → R - → S ) • R -r i=1 µ i R i -s i=1 ν i S i P 2 := Š • Den( - → S ) • S -s i=1 η i S i P T := F • Den( - → R - → S - → F ) • Den( - → S ) • F -r i=1 s j=1 α i,j R i • S j -s i=1 s j=1 γ i,j S i • S j -f i=1 δ i F i .
As for the case (3.T ) above, by applying Lemmas 2.2 and 2.1 to D • P 1 , D • P 2 , and D • P T , we deduce that the probability of aborting is bounded by

d 2 p-1 . For Type-1 groups, let ( - → µ , - → ν ), ( - → η , - → ζ ) and (A, B, Γ, - → δ ) be A alg 's representations of U , V and
W , respectively. Then B alg defines the polynomials P 1 , P 2 and P T as follows:

P 1 := Ř • Den( - → R - → S ) • R -r i=1 µ i R i -s i=1 ν i S i P 2 := Š • Den( - → R - → S ) • S -r i=1 ζ i R i -s i=1 η i S i P T := F • Den( - → R - → S - → F ) • Den( - → R - → S ) • F -r i=1 s j=1 α i,j R i • S j -r i=1 r j=1 β i,j R i • R j -s i=1 s j=1 γ i,j S i • S j -f i=1 δ i F i .
By an analysis analogous to the above, the abort probability is bounded by d 1 p-1 .

Proof of Theorem 3.14

We give a detailed proof for Type-2 bilinear groups. Let A alg be an algebraic algorithm against gegenüber G that wins with advantage in time t. We construct a generic reduction with oracle access to A alg , which yields an algebraic adversary B alg against q-dlog G 2 . There are three (nonexclusive) types of reasons that (Q 1 , Q 2 , Q T , R * , S * , F * ) is non-trivial; that is (2.i) from Def. 3.12 holds for some i ∈ {1, 2, T }. Each condition enables a different type of reduction, of which B alg runs the one that minimizes d τ . We start with Case (2.1), that is,

R * / ∈ FrSp(Q 1 ∪ Q 2 ).
Adversary B alg (g 2 , Z 1 , . . . , Z q ): On input a problem instance of game q-dlog G 2 with

Z i = [z i ] 2 ,
B alg defines g 1 ← ψ(g 2 ) and g T ← e(g 1 , g 2 ). Then, it picks random values -→ y

$ ← -(Z * p ) m and - → v $ ← -Z m p , sets x i := y i z + v i mod p (implicitly), and runs (U 1 , V 1 , W 1 , U 2 , V 2 , W 2 ), (R * , S * , F * ) $ ← -A alg O(•,•) (). Oracle calls O(i, P ( - → X
)) are answered by computing and returning Y P,i := [P (x 1 , . . . , x m )] i from the q-DLog instance, the morphism ψ : G 2 → G 1 and the pairing e : G 1 × G 2 → G T . B alg can do so efficiently since the total degree of the polynomials in Q 1 , Q 2 and Q T are bounded by q, q and 2q, respectively.

Since A alg is algebraic, for all k 1 , k 2 , k 3 ∈ {1, 2} it also returns vectors and matrices -

→ µ (k 1 ) , - → ν (k 1 ) , - → ζ (k 2 ) , - → δ (k 3 ) , A (k 3 ) = (α (k 3 ) j,k ) j,k , Γ (k 3 ) = (γ (k 3 ) j,k ) j,k respectively indexed by Q 1 , Q 2 , Q 1 , Q T , Q 1 × Q 2 and Q 2 × Q 2 such that U k 1 = R∈Q 1 Y µ (k 1 ) R R,1 • R∈Q 2 ψ(Y R,2 ) ν (k 1 ) R (3.21a) V k 2 = R∈Q 2 Y ζ (k 2 ) R R,2 (3.21b) W k 3 = R∈Q 1 S∈Q 2 e Y R,1 , Y S,2 α (k 3 ) R,S (3.21c) • R∈Q 2 S∈Q 2 e ψ(Y R,2 ), Y S,2 γ (k 3 ) R,S • R∈Q T Y δ (k 3 ) R R,T .
(3.21d)

B alg then computes the following multivariate polynomial, which corresponds to the logarithm of U R * ( -→ x ) 1

• U -1 2 in base g 1 :

P 1 ( - → X ) := R * ( - → X ) R∈Q 1 µ (1) R R( - → X ) + R∈Q 2 ν (1) R R( - → X ) -R∈Q 1 µ (2) R R( - → X ) -R∈Q 2 ν (2) R R( - → X ). Since in Case (2.1) we have R * / ∈ FrSp (Q 1 ∪ Q 2 ), the polynomial P 1 is non-zero. From P 1 , the reduction defines Q 1 (Z) := P 1 (y 1 Z + v 1 , . . . , y m Z + v m ). If Q 1 is the zero polynomial then B alg aborts. ( * )
Else, it factors Q 1 to obtain its roots z 1 , . . . (of which there are at most max{deg R * , 1} • max{d 1 , d 2 }). If for one of them we have

g z i 2 = Z, then B alg returns z i .
We analyze B alg 's success probability. First note that B alg perfectly simulates game gegenüber G , as the values x i are uniformly distributed in Z p and oracle calls are correctly computed.

Moreover, if B alg does not abort in ( * ) and A alg wins game gegenüber G , then U R * ( -→ x ) 1

• U -1 2 = 1. Substituting the right-hand side of (3.21a) for U 1 and U 2 in this equation and considering the discrete logarithm in base g 1 , this yields P 1 ( -→ x ) ≡ p 0. Since x i = y i z + v i , we moreover have Q 1 (z) = 0. By factoring Q 1 , reduction B alg finds thus the solution z.

It remains to bound the probability that B alg aborts in ( * ), that is, the probability that 0 ≡ Q 1 (Z) = P 1 (y 1 Z + v 1 , . . . , y m Z + v m ). The analysis is analogous to all previous theorems: 3.11. PROOF OF THEOREM 3.14

53

We upper-bound the probability that the coefficient of maximal degree, say d, is zero. By Lemma 2.2, this coefficient can be represented as a polynomial Q max 1 in variables (Y 1 , . . . , Y m ) of the same degree d. The values y 1 z, . . . , y m z are completely hidden from A alg because they are "one-time-padded" with v 1 , . . . , v m , respectively. This means that the values -→ µ (1) , -→ µ (2) , -→ ν (1) nad -→ ν (2) returned by A alg are independent from -→ y . Since -→ y is moreover independent from

-→ R * , Q 1 and Q 2 , Q T , it is also independent from P 1 , Q 1 and Q max 1
. The probability that Q 1 ≡ 0 is thus upper-bounded by the probability that Q max 1 ( -→ y ) ≡ p 0 when evaluated at the random point -→ y .

By the Schwartz-Zippel lemma, the probability that Q 1 (Z) ≡ 0 is thus upper-bounded by d p-1 . The degree d of Q 1 (and thus of Q max 1 ) is upper-bounded by the total degrees of P 1 , which is max{1, deg

R * } • max{d 1 , d 2 } = d 2.
q-dlog G 2 ,B alg ≥ Adv gegenüber G,A alg -Pr[B alg aborts]
and B alg follows the strategy that minimizes its abort probability to min

d 2.1 p-1 , d 2.2 p-1 , d 2.T p-1 = d 2 p-1 .
The proofs for groups of Type 1 and Type 3 are done by analogous adaptations of Theorem 3.5 as just shown for Type 2.

Chapter 4

Signatures on randomizable ciphertexts

This work was published in the proceedings of the 2020 SCN Conference. It was completed with co-author Georg Fuchsbauer.

For clarity reasons, we are using additive notations for the group operations (except for the group target).

Overview. We observe in this chapter that SoRC can be seen as signatures on equivalence classes (JoC'19), another primitive with many applications to anonymous authentication, and that SoRC provide better anonymity guarantees. We first strengthen the unforgeability notion for SoRC and then give a scheme that provably achieves it in the generic group model. Signatures in our scheme consist of 4 bilinear-group elements, which is considerably more efficient than prior schemes.

Definitions

We start with the definition of a signatures on randomizable ciphertexts scheme, which consists of a randomizable public-key encryption scheme and a signature scheme, whose signatures are computed and verified on pairs (encryption key, ciphertext). In addition, there is an algorithm Adapt, which lets one adapt a signature on a ciphertext to any randomization of the latter.

Syntax

Definition 4.1. We denote by PP the set of public parameters, and for p ∈ PP we let M p be the set of messages, DK p the set of decryption keys, EK p , the set of encryption keys, C p the set of ciphertexts, R p the set of ciphertext randomness, SK p the set of signature keys, VK p the set of verification keys and S p the set of signatures.

A scheme of signatures on randomizable ciphertexts S consists of the following probabilistic algorithms, of which all except Setup are implicitly parameterized by an element p ∈ PP.

Setup : N → PP (4.1)

KeyGen : ∅ → DK p × EK p SKeyGen : ∅ → SK p × VK p (4.2) Enc : EK p × M p × R p → C p Sign : SK p × EK p × C p → S p (4.3) Rndmz : EK p × C p × R p → C p Verify : VK p × EK p × C p × S p → {0, 1} (4.4)
Dec : DK p × C p → M p Adapt : S p × R p → S p (4.5) IND-CPA A SRC (λ, b) : 01 p $ ← -Setup(1 λ ) 02 (dk, ek) $ ← -KeyGen(p) 03 (m 0 , m 1 , st) $ ← -A(ek) 04 r $ ← -R p 05 c := Enc(ek, m b , r) 06 b $ ← -A(st, c) 07 Return b CL-HID A SRC (λ, b) : 01 p $ ← -Setup(λ) 02 (dk, ek) $ ← -KeyGen(p) 03 (c, st) $ ← -A(ek) 04 c 0 $ ← -C p 05 r $ ← -R p ; c 1 := Rndmz(ek, c, r) 06 b $ ← -A(st, c b ) 07 Return b
sk := (x 0 , x 1 ) $ ← -(Z * p ) 2 ; vk := ( X0 = x 0 Ĝ, X1 = x 1 Ĝ) ; return (sk, vk) Sign((x 0 , x 1 ), P, (C 0 , C 1 )): s $ ← -Z * p ; return (Z, S, Ŝ, T ) with Z := 1 s G + x 0 C 0 + x 1 C 1 S := sG Ŝ := s Ĝ T := 1 s x 0 G + x 1 P (4.8) Adapt (Z, S, Ŝ, T ), r : s $ ← -Z * p ; return (Z , S , Ŝ , T ) with Z := 1 s Z + r T S := s S Ŝ := s Ŝ T := 1 s T (4.9)
Verify(( X0 , X1 ), P, (C 0 , C 1 ), (Z, S, Ŝ, T )): Return 0 if P = 0 or S = 0; return 1 if the following equations hold and 0 otherwise: ← -G 2 . Let A be an adversary against CL-HID. We define an adversary B against DDH, which upon receiving a challenge (P, R, S), sends P to A to get c and then sends c + (R, S) to A. Finally, B returns A's output b .

e(Z, Ŝ) = e(G, Ĝ)e(C 0 , X0 )e(C 1 , X1 ) e(G, Ŝ) = e(S,
DDH B BGGen (λ, b) : 01 (p, G, G, Ĝ, Ĝ, G T , e) $ ← -BGGen(λ) 02 P $ ← -G 03 r $ ← -Z p 04 S 1 := rP 05 S 0 $ ← -G 06 b $ ← -B(p, (P, rG, S b )) ; Return b CL-HID A SRC (λ, b) : 01 p $ ← -Setup(λ) 02 (d, P ) $ ← -KeyGen(p) 03 (c, st) $ ← -A(P ) 04 c 0 $ ← -G × G 05 r $ ← -R p ; c 1 := (rG, rP ) 06 b $ ← -A(st, c + c b ) ; Return b
Proof. Let p = (p, G, G, Ĝ, Ĝ, G T , e) ∈ PP, let vk = (x 0 Ĝ, x 1 Ĝ), ek = dG, C 0 = c 0 G, C 1 = c 1 G
and sig = (Z = zG, S = sG, Ŝ = ŝ Ĝ, T = tG) be such that Verify(vk, ek, (C 0 , C 1 ), sig) = 1. Taking the logarithms in basis e(G, Ĝ) of the verification equations yields ŝ = s and, using this,

zs = zŝ = 1 + c 0 x 0 + c 1 x 1 (4.12) ts = tŝ = x 0 + dx 1 (4.13)
Let us now consider a uniform random element sig = (Z = z G, S = s G, Ŝ = ŝ Ĝ, T = t G) from the set sig ∈ S p Verify vk, ek, Rndmz(ek, c, r), sig = 1 . Again considering logarithms of the verification equation yields ŝ = s and

z s = 1 + (c 0 + r)x 0 + (c 1 + rd)x 1 = 1 + c 0 x 0 + c 1 x 1 + r(x 0 + dx 1 )
(4.12),(4.13) = zs + rts (4.14)

t s = x 0 + dx 1 (4.13) = ts (4.15)
Moreover, by signature validity, we have s = 0 and s = 0. We thus have Z = s s (Z + rT ) and T = s s T , as well as S = s s S and Ŝ = s s Ŝ (since ŝ = s and ŝ = s ). In other words, sig is a uniform element from the set

1 s * (Z + rT ), s * S, s * Ŝ, T = 1 s * T | s * ∈ Z * p .
Since Adapt(sig, r) outputs a uniform random element from that set, this concludes the proof.

Proof of unforgeability

Our main technical result is to prove that our scheme satisfies unforgeability (Def. 4.6) in the generic group model [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] for asymmetric ("Type-3") bilinear groups (for which there are no efficiently computable homomorphisms between G and Ĝ). In this model, the adversary is only given handles of group elements, which are just uniform random strings. To perform group operations, it uses an oracle to which it can submit handles and is given back the handle of the sum, inversion, etc of the group elements for which it submitted handles. Theorem 4.9. A generic adversary A that computes at most q group operations and makes up to k queries to its signature oracle cannot win the game EUF A S (λ) from Fig. 4.2 for S defined in Fig. 4.3 with probability greater than 2 -λ (2k + 1) (q + 3k + 3) 2 .

Proof. We consider an adversary that only uses generic group operations on the group elements it receives. After getting a verification key X0 = x 0 Ĝ, X1 = x 1 Ĝ and signatures Z i , S i , Ŝi , T i k i=1 computed with randomness s i on queries P (i) , (C

(i) 0 , C (i) 1 ) k i=1
, the adversary outputs an encryption key

P (k+1) , a ciphertext C (k+1) 0 , C (k+1) 1
and a signature Z * , S * , Ŝ * , T * for them. As it must compute any new group element by combining received group elements, it must choose coefficients ψ (i) , ψ

(i) z,1 , . . . , ψ (i) z,i-1 , ψ (i) s,1 , . . . , ψ (i) s,i-1 , ψ (i) t,1 , . . . , ψ (i) t,i-1 , γ (i) , γ (i) z,1 , . . . , γ (i) z,i-1 , γ (i) s,1 , . . . , γ (i) s,i-1 , γ (i) t,1 , . . . , γ (i) t,i-1 , κ (i) , κ (i) z,1 , . . . , κ (i) z,i-1 , κ (i) s,1 , . . . , κ (i) s,i-1 , κ (i) t,1 , . . . , κ (i) t,i-1 for all i ∈ {1, . . . , k + 1}, as well as σ, σ z,1 , . . . , σ z,k , σ s,1 , . . . , σ s,k , σ t,1 , . . . , σ t,k , τ, τ z,1 , . . . , τ z,k , τ s,1 , . . . , τ s,k , τ t,1 , . . . , τ t,k , ζ, 60 CHAPTER 4. SIGNATURES ON RANDOMIZABLE CIPHERTEXTS ζ z,1 , . . . , ζ z,k , ζ s,1 , . . . , ζ s,k , ζ t,1 , . . . , ζ t,k , φ, φ 0 , φ 1 , φ s,1 , . . . , φ s,k , which define P (i) = ψ (i) G + i-1 j=1 ψ (i) z,j Z j + ψ (i) s,j S j + ψ (i) t,j T j Z * = ζG + k j=1 ζ z,j Z j + ζ s,j S j + ζ t,j T j (4.16) C (i) 0 = γ (i) G + i-1 j=1 γ (i) z,j Z j + γ (i) s,j S j + γ (i) t,j T j S * = σG + k j=1
σ z,j Z j + σ s,j S j + σ t,j T j (4.17)

C (i) 1 = κ (i) G + i-1 j=1 κ (i) z,j Z j + κ (i) s,j S j + κ (i) t,j T j T * = τ G + k j=1 τ z,j Z j + τ s,j S j + τ t,j T j (4.18) Ŝ * = φ Ĝ + φ 0 X0 + φ 1 X1 + k j=1 φ s,j Ŝj (4.19)
Using this, we can write, for all 1 ≤ i ≤ k, the discrete logarithms z i and t i in basis G of the elements

Z i = 1 s i G + x 0 C (i) 0 + x 1 C (i) 1
and

T i = 1 s i x 0 G + x 1 P (i)
from the oracle answers.

z i = 1 s i 1 + x 0 γ (i) + i-1 j=1 γ (i) z,j z j + γ (i) s,j s j + γ (i) t,j t j + x 1 κ (i) + i-1 j=1 κ (i) z,j z j +κ (i) s,j s j +κ (i)
t,j t j (4.20)

t i = 1 s i x 0 + x 1 ψ (i) + i-1 j=1 ψ (i) z,j z j + ψ (i) s,j s j + ψ (i) t,j t j (4.21)
We interpret these values as multivariate rational fractions in variables x 0 , x 1 , s 1 , . . . , s k . A successful forgery (Z * , S * , Ŝ * , T * ) on P (k+1) , (C

) satisfies the verification equations Using the coefficients defined above and considering the logarithms in base e(G, Ĝ) we obtain:

e(Z * , Ŝ * ) = e(G, Ĝ)e(C (k+1) 0 , X0 )e(C (k+1)
ζ + k j=1 ζ z,j z j + ζ s,j s j + ζ t,j t j φ + φ 0 x 0 + φ 1 x 1 + k i=1 φ s,i s i = 1 + x 0 c (k+1) 0 + x 1 c (k+1) 1 (4.24) φ + φ 0 x 0 + φ 1 x 1 + k i=1 φ s,i s i = σ + k j=1 σ z,j z j + σ s,j s j + σ t,j t j (4.25) τ + k j=1 τ z,j z j + τ s,j s j + τ t,j t j φ + φ 0 x 0 + φ 1 x 1 + k i=1 φ s,i s i = x 0 + x 1 d (k+1) (4.26)
where for all i ∈ {1, . . . , k + 1} : c

(i) 0 = log C (i) 0 = γ (i) + i-1 j=1 γ (i) z,j z j + γ (i) s,j s j + γ (i) t,j t j , (4.27) c (i) 1 = κ (i) + i-1 j=1 κ (i) z,j z j + κ (i) s,j s j + κ (i) t,j t j and d (i) = log P (i) = ψ (i) + i-1 j=1 ψ (i) z,j z j + ψ (i) s,j s j + ψ (i) t,j t j .
We follow the standard proof technique for results in the generic group model and now consider an "ideal" game in which the challenger treats all the (handles of) group elements as elements of Z p (s 1 , . . . , s k , x 0 , x 1 ), that is, rational fractions whose indeterminates represent the secret values chosen by the challenger.

We first show that in the ideal game if the adversary's output satisfies the verification equations, then the second winning condition, P (k+1) , (C

(k+1) 0 , C (k+1) 1
) ∈ Q, is not satisfied, which demonstrates that the ideal game cannot be won. We then compute the statistical distance from the adversary's point of view between the real and the ideal game at the end of the proof.

In the ideal game we thus interpret the three equalities (4.24), (4.25) and (4.26) as polynomial equalities over the field Z p (s 1 , . . . , s k , x 0 , x 1 ). More precisely, we consider the equalities in the ring Z p (s 1 , . . . , s k )[x 0 , x 1 ], that is, the polynomial ring with x 0 and x 1 as indeterminates over the field Z p (s 1 , . . . , s k ). (Note that this interpretation is possible because x 0 and x 1 never appear in the denominators of any expressions.) As one of our proof techniques, we will also consider the equalities over the ring factored by (x 0 , x 1 ), the ideal generated by x 0 and x 1 :

1 Z p (s 1 , . . . , s k )[x 0 , x 1 ]/(x 0 , x 1 ) ∼ = Z p (s 1 , . . . , s k ) .
From (4.20) and (4.21), over this quotient we have z i =1 s i and t i = 0 and thus (4.24)-(4.26) become

ζ + k j=1 ζ z,j 1 s j + ζ s,j s j φ + k i=1 φ s,i s i = 1 (4.28) φ + k i=1 φ s,i s i = σ + k i=1 σ z,i 1 s i + σ s,i s i (4.29) τ + k i=1 τ z,i 1 s i + τ s,i s i φ + k i=1 φ s,i s i = 0 (4.30)
We first consider (4.29). By equating coefficients, we deduce:

φ = σ ∀i ∈ {1, . . . , k} : φ s,i = σ s,i and σ z,i = 0 (4.31)
We now turn to (4.28) and first notice that

φ + k i=1 φ s,i s i = 0 , (4.32)
because it is a factor of a non-zero product in (4.28). We next consider the degrees of the factors in (4.28), using the fact that the degree of a product is the sum of the degrees of the factors. Let i ∈ {1, . . . , k}. Since deg s i (1) = 0 and deg

s i φ + k i=1 φ s,i s i ≥ 0, we have deg s i ζ + k j=1 (ζ z,j 1 s j + ζ s,j s j ) ≤ 0, from which we get ∀ i ∈ {1, . . . , k} : ζ s,i = 0 . (4.33) (Note that deg s i 1 s i + s i = deg s i 1+s 2 i s i = 1.
) We next show that there is at most one φ s,i that is non-zero. Suppose there exist i 1 = i 2 ∈ {1, . . . , k} such that φ s,i 1 = 0 and φ s,i 2 = 0. This implies that deg

s i 1 φ + k i=1 φ s,i s i = deg s i 2 φ + k i=1 φ s,i s i = 1.
By considering these degrees in (4.28), the left factor must be of degree -1, that is (recall that ζ s,i = 0 for all i by (4.33)):

deg s i 1 ζ + k j=1 ζ z,j 1 s j = -1 and deg s i 2 ζ + k j=1 ζ z,j 1 s j = -1 . (4.34)
This is a contradiction since the former implies that ζ z,i 1 = 0, while the latter implies that ζ z,i 1 = 0, as we show next. Consider the expression deg

s i 2 ζ + k j=1,j =i 2 ζ z,j 1 s j s i 2 + ζ z,i 2 = deg s i 2 ζ + 62 CHAPTER 4. SIGNATURES ON RANDOMIZABLE CIPHERTEXTS k j=1 ζ z,j 1 s j s i 2 = -1 + deg s i 2 (s i 2 ) = 0 , by using (4.34). This implies ζ + k j=1,j =i 2 ζ z,j
1 s j = 0 and thus ζ z,i 1 = 0, which was our goal.

Therefore, there exists i 0 such that, for all i = i 0 , φ s,i = 0 and by (4.31):

∀ i ∈ {1, . . . , k} \ {i 0 } : σ s,i = φ s,i = 0 . (4.35)
Together with (4.33), this means that we can rewrite (4.28

) as ζ + k j=1 ζ z,j 1 s j (φ + φ s,i 0 s i 0 ) = 1
. Since for all i = i 0 , s i does not appear in 1, we have

∀ i ∈ {1, . . . , k} \ {i 0 } : ζ z,i = 0 .
(4.36)

We now consider equation (4.25) modulo (x 1 ). Since, by (4.31), φ = σ and φ s,i = σ s,i for all i, two terms cancel on both sides. Moreover, by (4.31), σ z,i = 0 for all i and thus, using t i mod (x 1 ) = x 0 s i for all i, yields

φ 0 x 0 = k i=1 σ t,i x 0 s i . (4.37)
By identifying coefficients, we deduce that

∀ i ∈ {1, . . . , k} : σ t,i = φ 0 = 0 . (4.38)
Using all of this in the original equation (4.25) (that is, "putting back" x 1 in (4.37) and applying (4.38)) yields φ 1 x 1 = 0 and thus φ 1 = 0 . (

We now turn to (4.30), in which by (4.32) we have τ

+ k i=1 (τ z,i 1 s i + τ s,i s i ) = 0.
From this we get by equating coefficients:

∀ i ∈ {1, . . . , k} : τ z,i = τ s,i = τ = 0 . (4.40)
Going back to equation (4.26) and applying the latter, as well as (4.38), (4.39) and (4.35) yields

k i=1 τ t,i t i (φ + φ s,i 0 s i 0 ) = x 0 + x 1 ψ (k+1) + k j=1 ψ (k+1) z,j z j + ψ (k+1) s,j s j + ψ (k+1) t,j t j . (4.41)
Computing this modulo (x 1 ) and recalling t i mod (x 1 ) = x 0 s i yields

k i=1 τ t,i x 0 s i (φ + φ s,i 0 s i 0 ) = x 0 , and thus k i=1 φτ t,i x 0 s i + k i=1,i =i 0 φ s,i 0 τ t,i s i 0 x 0 s i + φ s,i 0 τ t,i 0 x 0 = x 0 . (4.42)
By equating the coefficients for x 0 , we deduce that φ s,i 0 τ t,i 0 = 1 (and thus φ s,i 0 = 0 and τ t,i 0 = 0) . (4.43)

Moreover, for all i ∈ {1, . . . , k} \ {i 0 }, we deduce φ s,i 0 τ t,i = 0 and φτ t,i 0 = 0, which by applying (4.43) to both yields

∀ i ∈ {1, . . . , k} \ {i 0 } : τ t,i = 0 and φ = 0 . (4.44)
Using this, the left-hand side of (4.41) becomes φ s,i 0 τ t,i 0 t i 0 s i 0 , which, applying (4.43) and (4.21), becomes 1

s i 0 (x 0 + x 1 d (i 0 )
)s i 0 . This means that (4.41) becomes

x 0 + x 1 d (i 0 ) = x 0 + x 1 d (k+1) , which 4.3. SECURITY OF OUR SCHEME 63 implies x 1 (d (i 0 ) -d (k+1
) ) = 0. Since a polynomial ring over a integral domain such as Z p (s 1 , . . . , s k ) is an integral domain, and x 1 = 0, the last equality implies d (i 0 ) = d (k+1) . This means

P (i 0 ) = P (k+1) , (4.45)
that is, the encryption key of the forgery is the same as used in the i 0 -th query. We next show that the ciphertext

C (k+1) 0 , C (k+1) 1
of the forgery is a randomization of the one from the i 0 -th query. Consider equation (4.28). Since ζ z,i = 0 for i = i 0 (by (4.36)), all ζ s,i = 0 (by (4.33)), φ = 0 (by (4.44)) and φ s,i = 0 for i = i 0 (by (4.35)), it simplifies to

ζ + ζ z,i 0 1 s i 0 φ s,i 0 s i 0 = ζφ s,i 0 s i 0 + ζ z,i 0 φ s,i 0 = 1 , ( 4
z i 0 s i 0 + k j=1 ζ t,j t j φ s,i 0 s i 0 mod (x 1 ) = 1 + x 0 γ (k+1) + k j=1 γ (k+1) z,j z j + γ (k+1) s,j s j + γ (k+1) t,j
t j mod (x 1 ) , (4.48) and using z i mod (x 1 ) = 1+c (i) 0 x 0 s i mod (x 1 ) and t i mod (x 1 ) = x 0 s i for all i (cf. (4.20) and (4.21)) we get 1 + c

(i 0 ) 0 x 0 + k j=1 ζ t,j x 0 s j φ s,i 0 s i 0 mod (x 1 ) = 1 + x 0 γ (k+1) + k j=1 γ (k+1) z,j 1 + c (j) 0 x 0 s j + γ (k+1) s,j s j + γ (k+1) t,j
x 0 s j mod (x 1 ) . (4.49)

Let i > i 0 and let us consider the monomials of degree -1 in s i and degree 0 in s j , for all j > i.

Note that all monomials of c

(j) 0 = γ (j) + j-1 =1 γ (j) z, z + γ (j) s, s + γ (j)
t, t are of degree 0 in s , for ≥ j.

Therefore, we do not consider any c (j) 0 s j for j < i (because they do not contain the term s i ) nor c (j) 0 s j for j > i (since the contained monomials are of degree -1 in s j for j > i). For the monomials of degree -1 in s i and degree 0 in s j for j > i in (4.49) we thus have

∀ i > i 0 : ζ t,i x 0 φ s,i 0 s i 0 s i = x 0 γ (k+1) z,i 1 + c (i) 0 x 0 s i + γ (k+1) t,i
x 0 s i mod (x 1 ) = 0 .

Multiplying by

s i yields ζ t,i x 0 φ s,i 0 s i 0 -x 0 γ (k+1) z,i (1 + x 0 c (i) 0 ) + γ (k+1) t,i
x 0 mod (x 1 ) = 0 and after reordering the monomials according to their degree in x 0 we get mod (x 1 ) = 0 for all i > i 0 , and therefore

∀ i > i 0 : -x 2 0 γ (k+1) z,i c (i) 0 + γ (k+1) t,i + x 0 ζ t,i φ s,i 0 s i 0 -γ (k+1) z,i mod (x 1 ) = 0 . ( 4
∀ i > i 0 : γ (k+1) t,i = 0 . (4.52)
Since by (4.51) and (4.52) for all i > i 0 :

ζ t,i = γ (k+1) z,i = γ (k+1) t,i
= 0, we can rewrite (4.48) as

z i 0 s i 0 + i 0 i=1 ζ t,i t i φ s,i 0 s i 0 mod (x 1 ) = 1 + x 0 γ (k+1) + i 0 i=1 γ (k+1) z,i z i + γ (k+1) t,i t i + k i=1 γ (k+1) s,i s i mod (x 1 ) . (4.53)
For i > i 0 , from the coefficients of x 0 s i we get γ (k+1) s,i = 0. Applying this, (4.51) and (4.52) to (4.27) yields

c (k+1) 0 = γ (k+1) + i 0 i=1 γ (k+1) z,i z i + γ (k+1) s,i s i + γ (k+1) t,i t i ; (4.54)
and the right-hand side of (4.53) becomes 1+x 0 γ (k+1)

+ i 0 i=1 γ (k+1) z,i z i +γ (k+1) s,i s i +γ (k+1) t,i x 0 s i mod (x 1 ). Since z i mod (x 1 ) = 1+x 0 c (i) 0 s i mod (x 1
) and t i mod (x 1 ) = x 0 s i , for all i, (4.53) becomes 1 + x 0 c

(i 0 ) 0 + i 0 i=1 ζ t,i x 0 s i φ s,i 0 s i 0 mod (x 1 ) = 1 + x 0 γ (k+1) + i 0 i=1 γ (k+1) z,i 1 + x 0 c (i) 0 s i + γ (k+1) s,i s i + γ (k+1) t,i
x 0 s i mod (x 1 ) . (4.55)

We will now look at the coefficients of s i 0 and of 1 s i 0

. For this, we first note that for j ≥ i no s j appears in c (i) 0 (cf. (4.27)) and therefore for all i ≤ i 0 : c (i) 0 is constant in s i 0 . From the coefficients of s i 0 and of 1 s i 0 we thus get, respectively:

φ s,i 0 i 0 -1 i=1 ζ t,i x 0 s i = x 0 γ (k+1) s,i 0 (4.56) 0 = x 0 γ (k+1) z,i 0 (1 + x 0 c (i 0 ) 0 ) + γ (k+1)
= γ (k+1) + i 0 -1 i=1 γ (k+1) z,i z i + γ (k+1) s,i s i + γ (k+1) t,i t i ) . ( 4
(ζ z,i 0 z i 0 + ζ t,i 0 t i 0 )(φ s,i 0 s i 0 ) = 1 + x 0 c (k+1) 0 + x 1 c (k+1) 1 .
Since, by (4.47), ζ z,i 0 φ s,i 0 = 1 and plugging in the definitions of z i 0 and t i 0 , this yields 1 + x 0 c

(i 0 ) 0 + x 1 c (i 0 ) 1 + ζ t,i 0 φ s,i 0 x 0 + x 1 d (i 0 ) = 1 + x 0 c (k+1) 0 + x 1 c (k+1) 1
, and thus

x 0 c (i 0 ) 0 + ζ t,i 0 φ s,i 0 -c (k+1) 0 = -x 1 c (i 0 ) 1 + ζ t,i 0 φ s,i 0 d (i 0 ) -c (k+1) 1 . (4.60)
By considering the above modulo (x 1 ), plugging in the definition of c (i) 0 from (4.27) and using (4.59), we get

0 = ζ t,i 0 φ s,i 0 + c (i 0 ) 0 -c (k+1) 0 mod (x 1 ) = ζ t,i 0 φ s,i 0 + γ (i 0 ) -γ (k+1) + i 0 -1 j=1 (γ (i 0 ) z,j -γ (k+1) z,j )z j + (γ (i 0 ) s,j -γ (k+1) s,j )s j + (γ (i 0 ) t,j -γ (k+1) t,j )t j mod (x 1 ) = ζ t,i 0 φ s,i 0 + γ (i 0 ) -γ (k+1) + i 0 -1 j=1 (γ (i 0 ) z,j -γ (k+1) z,j ) (1 + x 0 c (j) 0 ) s j + (γ (i 0 ) s,j -γ (k+1) s,j
)s j + (γ

(i 0 ) t,j -γ (k+1) t,j )
x 0 s j mod (x 1 ) .

(4.61)

Taking the above modulo (x 0 ) we get

ζ t,i 0 φ s,i 0 + γ (i 0 ) -γ (k+1) + i 0 -1 j=1 ((γ (i 0 ) z,j -γ (k+1) z,j ) 1 s j + (γ (i 0 ) s,j -γ (k+1) s,j
)s j ) mod (x 0 , x 1 ) = 0 .

By looking at the coefficients of the constant monomial and of 1 s i and s i for all i < i 0 , we deduce the following:

ζ t,i 0 φ s,i 0 + γ (i 0 ) -γ (k+1) = 0 (4.62) ∀i < i 0 : γ (i 0 ) z,i -γ (k+1) z,i = 0 and γ (i 0 ) s,i -γ (k+1) s,i = 0 (4.63)
This lets us rewrite (4.61) as

i 0 -1 j=1 (γ (i 0 ) t,j -γ (k+1) t,j
) x 0 s j mod (x 1 ) = 0, and equating the coefficients of

x 0
s j for all j < i 0 yields ∀i < i 0 : γ

(i 0 ) t,i = γ (k+1) t,i . ( 4
= ζ t,i 0 φ s,i 0 + γ (i 0 ) + i 0 -1 i=1 γ (i 0 ) z,i z i + γ (i 0 ) s,i s i + γ (i 0 ) t,i t i ) . (4.65)
Recalling the definition of c (i 0 ) 0 form (4.27), we can conclude that:

c (k+1) 0 = ζ t,i 0 φ s,i 0 + c (i 0 ) 0 . (4.66)
Therefore (4.60) becomes 0 = -x 1 c

(i 0 ) 1 + ζ t,i 0 φ s,i 0 d (i 0 ) -c (k+1) 1
, in other words

c (k+1) 1 = ζ t,i 0 φ s,i 0 d (i 0 ) + c (i 0 ) 1 . (4.67)
The last two equations mean that C

(k+1) 0 , C (k+1) 1 = C (i 0 ) 0 + rG, C (i 0 ) 1
+ rP (i 0 ) , for r = ζ t,i 0 φ s,i 0 , which together with (4.45) means that

P (k+1) , (C (k+1) 0 , C (k+1) 1 ) ∈ P (i 0 ) × (C (i 0 ) 0 , C (i 0 ) 1 ) P (i 0 ) ⊆ Q .
We have thus shown that in the "ideal" model, the attacker cannot win the game. It remains to upper-bound the statistical distance from the adversary point of view between these two models.

Difference between ideal and real game. We start with upper-bounding the degree of the denominators and numerators of the rational fractions that can be generated by the adversary.

We first show that by induction on the number of queries k, that all the elements returned by the challenger in the ideal game are divisors of k i=1 s i . In the base case, when no queries are made, no s i appears and the elements returned by the adversary are polynomials. For the induction step, assume the statement holds for queries. Consider the reply to the ( + 1)-th query: S +1 and Ŝ +1 are monomials; Z +1 and T +1 are sums of polynomials and elements output by the adversary divided by s +1 . Using the induction hypothesis on the adversary's outputs, we deduce that the denominators divide +1 i=1 s i . Similarly, we can show that the numerators of each element output by the challenger can be written as a sum of divisors of

x k+1 0 x k+1 1 k i=1 s i .
The "ideal" model and the generic group model differ if and only if two elements are distinct as rational fractions but identical as (handle of a) group element. That is, if we evaluate two different rational fractions at scalar values x 0 , x 1 , s 1 , . . . , s k and obtain the same result.

Any such equality of rational fractions generated during the game can be rewritten as a polynomial equation of degree 3k + k + 2 (3k + 2 upper-bounding the degree of the numerator and k that of the denominator). Because the values x 0 , x 1 , s 1 , . . . , s k are uniformly random (and hidden from the adversary), the Schwartz-Zippel lemma [START_REF] Jacob | Fast probabilistic algorithms for verification of polynomial identities[END_REF] yields that the probability of this equality holding is at most 4k+2 p-1 . If the adversary computes at most q group operations, then there are at most q + 3 + 3k group elements, where 3 comes from the generator and the verification key, and 3k corresponds to the answers to the signing queries (note that Ŝ and S correspond to the same monomial). There are therefore 1 2 (q + 3k + 3)(q + 3k + 2) pairs of rational fractions. Using the union bound, we conclude that the adversary can distinguish the two models with probability at most 4k+2 2(p-1) (q + 3k + 3)(q + 3k + 2) < 2k+1 2 λ (q + 3k + 3) 2 , since p -1 > 2 λ , which is the bound claimed by the theorem. Generalization of our scheme. We conclude by mentioning that our scheme easily generalizes to ElGamal encryptions of vectors of group elements without increasing the size of signatures: for an encryption key (P 1 , . . . , P n ) and a signing key (x 0 , . . . , x n ), a ciphertext consisting of C 0 = rG and C i = M i + rP i for 1 ≤ i ≤ n, a signature on randomizable ciphertexts is defined as:

Z := 1 s G + n i=0 x i C i S := sG Ŝ := s Ĝ T := 1 s x 0 G + n i=1
x i P i (4.68)

Chapter 5

Transferable E-cash: A Cleaner Model and the First Practical Instantiation

This is a joint-work with Georg Fuchsbauer and Chen Qian.

Overview. In this chapter we first revisit the model for transferable e-cash, proposing simpler yet stronger security definitions and then give the first concrete instantiation of the primitive, basing it on bilinear groups, and analyze its concrete efficiency.

Security Models

Algorithms and protocols

An e-cash scheme is set up by running ParamGen and the bank generating its key pair via BKeyGen.

The bank maintains a list of users UL and a list of deposited coins DCL. Users run the protocol Register with the bank to obtain their secret key, while their public keys are added to UL. With her secret key a user can run Withdraw with the bank to obtain coins, which she can transfer to others via the protocol Spend. Spend is also used when a user deposits a coin at the bank. After receiving a coin, the bank runs CheckDS on the coin and the previously deposited coins in DCL, which determines whether to accept the coin. If so, it is added to DCL; if not (in case of double-spending), CheckDS returns the public key of the accused user and a proof Π, which can be verified using VfyGuilt.

ParamGen(1 λ ), on input the security parameter λ in unary, outputs public parameters par, which are an implicit input to all of the following algorithms and interactive protocols.

BKeyGen (par) is executed by the bank B and outputs its public key pk B and its secret key sk B = (sk W , sk D , sk CK ), where sk W is used to issue coins in Withdraw and to register users in Register; sk D is used as the secret key of the receiver when coins are deposited via Spend; and sk CK is used for CheckDS.

Register B(sk W ), U(pk B ) is a protocol between the bank and a user. The user obtains a secret key sk and the bank gets pk, which it adds to UL. In case of error, they both obtain ⊥.

Oracles

We now define oracles used in the security definitions, which differ depending on whether the adversary impersonates a corrupt bank or users. If during the oracle execution an algorithm fails (i.e., it outputs ⊥) then the oracle also stops. Otherwise the call to the oracle is considered successful; a successful deposit oracle call must also not detect any double-spending.

Registration and corruption of users. The adversary can instruct the creation of honest users and either play the role of the bank during registration, or passively observe registration. It can moreover "spy" on users, meaning it can learn the user's secret key. This will strengthen yet simplify our anonymity games compared to [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF], where once the adversary had learned the secret key of a user (by "corrupting" her), the user could not be a challenge user in the anonymity games anymore (selfless anonymity, while we achieve full anonymity).

BRegist() plays the bank side of Register and interacts with A. If successful, it adds (pk, ⊥, uds = 0) to UL (where uds is the number of double-spends).

URegist() plays the user side of the Register protocol when the bank is controlled by the adversary.

Upon successful execution, it adds (pk, sk, 0) to UL.

Regist() plays both parties in the Register protocol and adds (pk, sk, 0) to UL.

Spy(i), for i ≤ |UL|, returns user i's secret key sk i .

Withdrawal oracles. The adversary can either withdraw a coin from the bank, play the role of the bank, or passively observe a withdrawal. Spd(j) spends the coin from the j-th entry (owner j , c j , cds j , origin j ) in CL to A, who could be impersonating a user, or the bank during a deposit. The oracle plays user U in the Spend protocol with secret key sk owner j . It increments the coin spend counter cds j by 1. If afterwards cds j > 1, then the owner's double-spending counter uds owner j is incremented by 1.

S&R(j, i) spends the j-th coin in CL to user i. It runs (ok, c) ← Spend U(c j , sk owner j , pk B ), U (sk i , pk B ) and adds (owner = i, c, cds = 0, pointer = j) to CL. It increments the coin spend counter cds j by 1. If afterwards cds j > 1, then uds owner j is incremented by 1.

BDepo() lets A deposit a coin. It runs U in Spend using the bank's secret key sk D with the adversary playing U. If successful, it runs CheckDS on the received coin and updates DCL accordingly; else it outputs a pair (pk, Π). (Note that no oracle "UDepo" is required, since Spd lets the adversarial bank have an honest user deposit a coin.)

Economic properties

We distinguish two types of security properties of transferable e-cash schemes. Besides anonymity notions, economic properties ensure that neither the bank nor users will incur an economic loss when participating in the system.

Soundness. If an honest user accepted a coin during a withdrawal or a transfer, then she is guaranteed that the coin will be accepted by others, either honest customers when transferring, or the bank when depositing. The game is formalized in Fig. 5.1 where i 2 plays the role of the receiver of a spending or the bank. For convenience, we define probabilistic polynomial-time (PPT) adversaries A to be stateful in all our security games.

Definition 5.1 (Soundness).

A transferable e-cash system is sound if for any PPT A, we have

Adv sound A (λ) := Pr[Expt sound A (λ) = 1] is negligible in λ.

Unforgeability

This notion can be seen as a merge of unforgeability and user identification from [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] (which were not consistent as we will explain in Sect. 5.2). The notion protects the bank, ensuring that no (coalition of) users can spend more coins than the number of coins they withdrew. It also guarantees that whenever a coin is deposited and refused by CheckDS, it also returns the identity of a registered user, who is accused of double-spending. (Exculpability, below, ensures that no innocent user will be accused.) The game is formalized in Fig. 5.2 and lets the adversary impersonate all users.

Definition 5.2 (Unforgeability). A transferable e-cash system is unforgeable if

Adv unforg A (λ) := Pr[Expt unforg A (λ) = 1] is negligible in λ for any PPT A.
Exculpability. This notion, a.k.a. non-frameability, ensures that the bank, even when colluding with malicious users, cannot wrongly accuse an honest user of double-spending. Specifically, it guarantees that an adversarial bank cannot produce a double-spending proof Π * that verifies for the public key of an honest user i * that has never double-spent. The game is formalized as in Fig. 5.3.

(Exculpability). A transferable e-cash system is exculpable if Adv

excul A (λ) := Pr[Expt excul A (λ) = 1] is negligible in λ for any PPT A.

Anonymity properties

We will not follow previous anonymity notions [BCF + 11, BCFK15], but introduce new ones which precisely distinguish between the adversary's capabilities, in particular, whether it is able to detect double-spending. When the adversary impersonates the bank, we consider two cases: user anonymity and coin anonymity (and explain why this distinction is necessary).

As transferred coins necessarily grow in size [START_REF] Chaum | Transferred cash grows in size[END_REF], we can only guarantee indistinguishability of compatible coins. We therefore define comp(c 1 , c 2 ) = 1 iff size (c 1 ) = size (c 2 ), where the size(c) = 1 after c was withdrawn and it increases by 1 after each transfer.

Coin anonymity. This notion is closest to (and implies) the anonymity notion of classical e-cash: an adversary, who also impersonates the bank, issues two coins to the challenger and when she later receives them (via a deposit in classical e-cash), she should not be able to associate them to their issuances. In transferable e-cash, we allow the adversary to determine two series of honest users via which the coins are respectively transfered before being given back to the adversary.

The experiment is specified on the left of Fig. 5.4: users i (0) 0 and i (1) 0 withdraw a coin from the adversarial bank, user i (0) 0 passes it to i (0) 1 , who passes it to i (0) 2 , etc., In the end, the last users of the two chains spend the coins to the adversary, but the order in which this happens depends on a random bit b, which the adversary must decide.

User anonymity. Coin anonymity required that users who transfer the coin are honest. If one of the users through which the coin passes colluded with the bank, there would be a trivial attack: after receiving the two challenge coins, the bank simulates the deposit of one of them and the deposit of the coin intercepted by the colluding user. If a double-spending is detected, it knows that the received coin corresponds to the sequence of users which the colluder was part of.

← ParamGen(1 λ ) pk B ← A(par) i (0) 0 ← A URegist,Spy ; run UWith(i (0) 0 ) with A i (1) 0 ← A URegist,Spy ; run UWith(i (1) 0 ) with A (i (0) 1 , . . . , i (0) k0 ), (i (1) 1 , . . . , i (1) k1 ) ← A URegist,Spy If k 0 = k 1 then abort For j = 1, . . . , k 0 : Run S&R 2j -1, i (0) j Run S&R 2j, i (1) j Run Spd(2k 0 + 1 + b) with A Run Spd(2k 0 + 2 -b) with A b * ← A Return b * Expt u-an A,b (λ): par ← ParamGen(1 λ ) pk B ← A (par) (i (0) 0 , i (1) 0 ) ← A URegist,Spy Run Rcv(i b ) with A (i (0) 1 , . . . , i (0) k0 ), (i (1)
1 , . . . , i

(1) Since double-spending detection is an essential feature of e-cash, attacks of this kind are impossible to prevent. However, we still want to guarantee that, while the bank can trace coins, the involved users remain anonymous. We formalize this in the game on the right of Fig. 5.4, where, in contrast to coin anonymity, there is only one coin and the adversary must distinguish the sequence of users through which the coin passes before returning to her. In contrast to coin anonymity, we now allow the coin to already have some "history", rather than being freshly withdrawn.

k1 ) ← A URegist,Spy If k 0 = k 1 then abort For j = 1, . . . , k 0 : Run S&R j, i (b) j Run Spd(k 0 + 1) with A b * ← A Return b *
Coin transparency. This notion is in some sense the strongest anonymity notion and it implies that a user that transfers a coin cannot recognize it if at some point she receives it again. Note that this notion (as well as coin anonymity) is not even achieved by physical cash, as banknotes can be marked by users (or the bank). As the bank can necessarily trace coins (for double-spending detection), it is assumed to be honest for this notion. Actually, only the detection key sk CK must remain hidden from the adversary, while sk W and sk D can be given.

The game formalizing this notion, specified in Fig. 5.5, is analogous to coin anonymity, except that the challenge coins are not freshly withdrawn; instead, the adversary spends two coins of its choice to users of its choice, both are passed through a sequence of users of the adversary's choice and one of them is returned to the adversary.

There is another trivial attack that we need to exclude: the adversary could deposit the coin that is returned to him and one, say the first, of the coins he initially transfered to an honest user. Now if the deposit does not succeed because of double-spending, the adversary knows that it was the first coin that was returned to him. Again, this attack is unavoidable due to the necessity of double-spending detection. It is a design choice that lies outside of our model to implement sufficient deterrence from double-spending, so it would exceed the utility of breaking anonymity. This is the reason why the game aborts if the adversary deposits twice a coin from the set of "challenge coins" (consisting of the two coins the adversary transfers and the one it receives). The variable ctr counts how many times a coin from this set was deposited. Note also that because A has sk W , and can therefore create unregistered users, we do not consider UL in this game. Definition 5.4 (Anonymity). For x ∈ {c-an, u-an, c-tr} a transferable e-cash scheme satisfies x 0 ← CheckDS(sk CK , ∅, CL, c 0 ) If x 0 = ⊥ then ctr ← ctr + 1 //c 0 had been deposited DCL ← CheckDS(sk CK , ∅, ∅, c 0 ) //add c 0 to list of challenge coins i (1) ← A URegist,BDepo,Spy Run Rcv(i (1) ) with A; let c 1 be the received coin stored in CL [2] x

x if Adv x A (λ) := Pr[Expt x A,1 (λ) = 1] -Pr[Expt x A,0 (λ) = 1]
1 ← CheckDS(sk CK , ∅, CL, c 1 ) If x 1 = ⊥ then ctr ← ctr + 1 //c 1 had been deposited If comp(c 0 , c 1 ) = 1 then abort x 2 ← CheckDS(sk CK , ∅, DCL , c 1 ) //add c 1 to list of challenge coins If x 2 = ⊥ then DCL ← x 2 // (c 1 could be a double-spending of c 0 ) (i (0) 1 , . . . , i (0) k0 ), (i (1) 1 , . . . , i (1) k1 ) ← A URegist,BDepo ,Spy If k 0 = k 1 then abort If (k b = 0) then run S&R b + 1, i (b) 1 // spend coin c b to user i (b) 1 . . .

Comparison with previous work

Model comparison

In order to justify our new model, we start with discussing a security vulnerability of the previous model [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF].

Issues with economical notions. As already pointed out in Sect. 5.1, the correctness properties were missing in previous models.

No soundness guarantees.

In none of the previous models was there a security notion that guaranteed that an honest customer could successfully transfer a coin to another honest user or the bank, even if the coin was obtained regularly.

Fuzzy definition of "unsuccessful deposit". Previous models defined a protocol called "Deposit", which we separated it into an interactive (Spend) and a static part (CheckDS). In their definition of unforgeability, the authors [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] use the concept of "successful deposit", which was not clearly defined, as an "unsuccessful deposit" could mean one of the following:

• The bank detects a double-spending and provides a proof accusing the cheater (who could be different from the depositer).

• The customer did not follow the protocol (e.g., by sending a malformed coin), in which case we cannot expect a proof of guilt from the bank.

• The customer followed the protocol but using a coin that was double-spent (either earlier or during deposit); however, the bank does not obtain a valid proof of guilt and outputs ⊥.

After a careful reading of the definitions in [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] we concluded that the authors do not distinguish the second and the third case. This is a serious issue, since the second case cannot be avoided, while the third case should be avoided so the bank does not lose money without being able to accuse the cheater. This is now guaranteed by our unforgeability notion in Def. 5.2.

An error in a proof in BCFK15

The authors of [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] claim that their scheme satisfies the notion StR-fa defined in [BCF + 11] (after having discovered an error in the StR-fa proof of the scheme of that paper). To achieve this anonymity property (the hardest property to achieve, as they notice), they use malleable signatures, a primitive with very strong security guarantees. The ensure that whenever the adversary, after obtaining simulated signatures, outputs a valid message/signature pair (m, σ), it must have derived the pair from received signatures. Formally, there exists an extractor that can extract a transformation from σ that links m to the messages for which the adversary queried signatures. However, in the definition of StR-fa [BCF + 11] the adversary receives sk W (as in our c-tr notion), which in their instantiation [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF] contains the signing key for the malleable signature scheme. Using this, the adversary can thus easily compute a fresh signature from which no extractor can recover a transformation explaining the signed message.

For this reason we claim that our scheme is the first to satisfy the "spirit" of the StR-fa notion. We believe that the error in the proof was a consequence of the complexity of StR-fa and that our notion c-tr is simpler and more intuitive.

Instantiation Overview

The bank creates money and the validates new users in the system. Digital signatures can be used for these two functions: the bank signs the key of a new user, who can then prove that he is registered; and during a coin issuing, the bank signs a message M sn that is associated to the initial serial-number (SN) component sn 0 of a coin, which makes coins unforgeable.

After a coin has been transferred k times, its core consists of an SN list sn 0 , sn 1 , . . . , sn k , together with a list of tags tag 1 , . . . , tag k (for a freshly withdrawn coin, we have k = 0). When a user spends such a coin, the receiver generates a fresh SN component sn k+1 , from which the spender must generate a tag tag k+1 that is also associated with her public key and the last serial number sn k (which she generated when she received the coin.)

These tags allow the bank to identify the fraudster in case of double-spending, while they preserve the anonymity of honest users. A coin moreover contains the users' public key w.r.t. which the tags were created, as well as certificates on them issued by the bank. To provide anonymity, all these components are not given in the clear, but as a zero-knowledge proof of knowledge. That is, a coin is a proof of knowledge of its serial number, its tags, the user public keys and their certificates and ensures that all of them are consistent.

As we use a commit-and-prove proof system, all these values are included in the coin as commitments. Recall that a coin also includes a signature by the bank on (a message related to) the initial SN component. In order to achieve anonymity towards the bank (coin anonymity), the bank must sign this message blindly, which is achieved by using the SigCm functionality: the user sends a commitment to the serial number, and the bank computes a committed signature on the committed value.

Finally, the bank needs to be able to detect whether a double-spending occurred and identify the user that committed it. One way would be to give the serial numbers and the tags (which protect the anonymity of honest users) in the clear. This would yield a scheme that satisfies coin anonymity and user anonymity (note that in these two notions the bank is corrupted). However, coin transparency, the most intricate anonymity notion, would not be achieved, since the owner of a coin could easily recognize it when she receives it again by looking at its serial number.

It is coin transparency that requires to hide the serial numbers (and the associated tags), and moreover to use a randomizable proof system, since the appearance of a coin needs to completely change after every transfer. To hide the serial numbers and the tags from users, but still provide access to them by the bank, we add encryptions of them to the coin. However, these must smoothly interoperate with the randomization of the coin, which is why we require rerandomizable encryption that can be tied into the machinery of updating of the proofs, which is necessary every time the ciphertexts and the commitments contained in a coin are refreshed.

Technical description

Primitives used.

The basis of our scheme is a randomizable extractable NIZK commit-and-prove scheme

Auxiliary functions.

In order to simplify the description of our scheme, we will first define several auxiliary functions. To randomize a given tuple of commitments and ciphertext, and proofs for them (and adapting the proofs to the randomizations), we use an algorithm Rand, which internally runs C.RdCm, E.ReRand, C.AdptPrf and E.AdptPrf with the same randomness.

Assuming the equations for T.SVfy(•, •, •) = 1, T.SVfy init (•, •, •) = 1 and T.TVfy(•, •, •, •, •) = 1, as well as E.Verify(pk, •, •, c) = 1 are all in the set E of equations supported by the proof system, we define the following: C.Prv sn,init proves that a committed initial serial number sn has been honestly generated w.r.t. a committed key pk T and a committed message M (given the used randomness ρ pk , ρ sn and ρ M ), while C.Verify sn,init verifies such proofs. C.Prv sn and C.Verify sn do the same for non-initial serial numbers (for which there are no messages, but which require a proof of well-formedness instead).

C.Prv

U : -n $ ← -N ; ρ sn , ρ cert , ρ pk , ρ sn-pf , ν sn $ ← -R -(sn , sn-pf ) ← T.SGen(par T , sk tag , n ) -c cert ← C.Cm(ck, cert , ρ cert ) -c pk ← C.Cm(ck, pk , ρ pk ) -c sn ← C.Cm(ck, sn , ρ sn ) -c sn-pf ← C.Cm(ck, sn-pf , ρ sn-pf ) -c sn ← E.Enc(ek, sn , ν sn ) -π cert ← C.Prv(ck, S.Verify(vk B , •, •) = 1, (pk tag , ρ pk ), (cert , ρ cert )) -π sn ← C.Prv sn (ck, pk T , sn , sn-pf , ρ pk , ρ sn , ρ sn-pf ) -π sn ← C.E.Prv enc (ck, ek, sn , ρ sn , ν sn , c sn )
-Send (sn , ρ sn ) to U U : -Parse c as c 0 , (c j = (c j pk , c j cert , π j cert , c j sn , π j sn , c j tag , π An incrimination proof in our e-cash scheme is simply an incrimination proof of the tag scheme T. Thus, if the reduction correctly guesses the user u that will be wrongfully incriminated by A (which it can with probability 1/u), then we can construct an adversary against exculpability of T. The term m-ind comes from the fact that we first need to switch C to hiding mode, so we can simulate π sn and π tag for the target user, since the oracles O 1 and O 2 in the game for tag exculpability (see Fig. 2.3) do not return sn-pf and t-pf . Theorem 5.8. Let A be an adversary that wins the coin anonymity game (c-an) with advantage and let k be an upper-bound on the number of users transferring the challenge coins. Then there exist adversaries against mode-indistinguishability of C and tag-anonymity of T with advantages m-ind and t-an , resp., such that ≤ 2 m-ind + (k + 1) t-an . Theorem 5.9. Let A be an adversary that wins the user anonymity game (u-an) with advantage and let k be a bound on the number of users transferring the challenge coin. Then there exist adversaries against mode-indistinguishability of C and tag-anonymity of T with advantages m-ind and t-an , resp., such that ≤ 2 m-ind + (k + 1) t-an .

In the proof of both theorems, we first define a hybrid game in which the commitment key is switched to hiding mode (hence the loss m-ind , which occurs twice for b = 0 and b = 1). All commitments are then perfectly hiding and the only information available to the adversary are the serial numbers and tags. (They are encrypted in the coin, but the adversary, impersonating the bank, can decrypt them.)

We then argue that, by tag anonymity of T, the adversary cannot link a user to a pair (sn, tag), even when it knows the users' secret keys. We define a sequence of k + 1 hybrid games (as k transfers involve k + 1 users); going through the user vector output by the adversary, we can switch, one-by-one all users from the first two the second vector. Each switching can be detected by the adversary with probability at most t-an . Note the additional factor 2 for t-an in game c-an, which is due to the fact that there are two coins in witch we switch users, whereas there is only one in game u-an. Theorem 5.10. Let A be an adversary that wins the coin-transparency game (c-tr) with advantage , let be the size of the challenge coins, and k be an upper-bound on the number of users transferring the challenge coins. Then there exist adversaries against mode-indistinguishability of C, tag-anonymity of T, IACR-security of E and RCCA-security of E with advantages m-ind , t-an , iacr and rcca , resp., such that ≤ 2 m-ind + (k + 1) t-an + 2 iacr + rcca .

The crucial difference to the previous anonymity theorems is that the bank is honest (which makes this strong notion possible). We therefore must rely on the security of the encryptions, for which the reduction thus does not know the decryption key. At the same time, the reduction must be able to detect double-spendings, when the adversary deposits coins. Since we use RCCA encryption, the reduction can do so by using its own decryption oracle.

Recall that the RCCA-secure scheme E is only used to encrypt the initial part of the serial number; using a less efficient scheme does thus not have a big impact on the efficiency of our scheme.

From all other ciphertexts contained in a coin (which are under scheme E) we only require IACR security, which standard ElGamal encryption satisfies under DDH. Thus, we instantiate E with ElGamal vector encryption. (Note that our instantiation of E is also built on top of ElGamal). We prove the following in the appendix. Theorem 5.14. Assuming SXDH, our randomizable encryption scheme in Appendix A.2 is RCCAsecure and the one in Appendix A.2 is IACR-secure. Double-spending tags. We will use a scheme that builds on the one given in [START_REF] Baldimtsi | Anonymous transferable E-cash[END_REF]. We have optimized the size of the tags and made explicit all the functionalities not given in the previous version. We defer this to Appendix A.2.

Efficiency analysis

For a group G ∈ {G, Ĝ, Z p }, let |G| denote the size of one element of G. Let c btsrap denote the coin output by U at the end of the Withdraw protocol (which corresponds to c init plus secret values, like n, ρ sn , etc., to be used when transferring the coin), and let c std one (non-initial) component of the coin. We conclude by summarizing the characteristics of our scheme in the following table and refer to Appendix A. 3

π i ∧ π i σ ∧ π i
sn Let E sig and E com,1 be the following events: B 1 breaks the unforgeability of the signature scheme S; and B 3 breaks the soundness of the commitment scheme C.

Property A.2. E counterfeit ⊆ E sig ∪ E com,1 .
Suppose that we are in the case E counterfeit \ E sig . Because the coin has been accepted during Spend in a BDepo oracle call, the proofs output in B 3 are correct. Let sn 1 , ν 1 , M 1 , pk 1 T , σ 1 , . . . , sn |S| , ν |S| , M |S| , pk |S| T , σ |S| be the extraction of the commitments given by B 3 to the challenger of the soundness game. Then if there exists i such that S.Verify vk, M i , σ i = 1, the soundness game is won by B 3 .

Suppose that

|S| i=1

S.Verify vk, M i , σ i = 1. Since we are not in E sig , all the M i 's correspond to one coin that has been withdrawn. But only q W messages M correspond to these coins. Thus, First we consider the following part of Expt c-an A,0,ZK (λ)) with more details:

|{M i } |S| i=1 | ≤ q W . If
i 0 ← A URegist,Spy
Run UWith ZK (i 0 ) with A i 1 ← A URegist,Spy Run UWith ZK (i 1 ) with A

We would like to swap the serial numbers of i 0 and i 1 by using tag-anonymity. The issue here is that in the first call to UWith ZK , we do not know yet i 1 (because it is chosen in a second round). Fortunately, at this step we only sent A data that is unrelated to this serial number, because we are using ZCm. Thus, at the end of this part, we can compute the ciphertexts of both initial coins.

We can decompose this part of the game as: We can do the sn-computations and the encryptions at the end of this part (because they are not related to data sent to A). We can therefore replace the previous instructions by the following algorithm DoubleUWith: pk , c

DoubleUWith A : i 0 ← A URegist,Spy
(1) cert , π

(1) cert , c

(1) sn , π

(1)

sn , c

(1)

M , c

(1) σ , π

(1) σ , c(1) sn , π(1) sn ),

--→ ρ (1) ), n (1) , sn (1) , ρ

(1)

sn + ( --→ ρ (1) ) sn , ρ

(1)

pk + (

--→ ρ (1) ) pk CL[1] ← (i 0 , c (0)
1 , 0, A) CL [2] ← (i 1 , c

(1) 1 , 0, A) Return (i 0 , i 1 )

To express these swaps of instruction, we define the following game.

Experiment Expt c-an

A,0,ZKV2 (λ): Gr ← BGGen(1 λ ) par T ← T.Setup(Gr) par S ← S.Setup(Gr) par S ← S .Setup(Gr) (ck, td) ← C.SmSetup(Gr) par ← (1 λ , par S , par S , par T , ck) pk B ← A(par) (i 0 , i 1 ) ← DoubleUWith A Now, by remarking that two randomized commitments of the same type in the hiding-mode will have the (exact) same distribution, we can deduce that Expt c-an A,0,ZKV2,k (λ) is perfectly indistinguishable from Expt c-an A,1,ZK (λ). From a similar reasoning to previous ones we get that Expt c-an A,1,ZK (λ) is m-ind statistically close to Expt c-an A,1 (λ). Finally, we deduce that Expt c-an A,1 (λ) is 2( ZK + (k + 1) t-an )-statistically-close to Expt c-an A,0 (λ). Note that t-an is the advantage against tag-anonymity of an adversary that is making just one call to O 1 and one to O 2 .

A.2 Instantiation of the new blocks Instantiation and proofs of the double spending tag scheme

We will reuse the scheme introduced in [BCFK15].

T.Setup (Gr):

• Parse Gr as (p, G, Ĝ, G T , e, g 1 , ĝ)

• g 2 , h 1 , h 2 $ ← -G • Return (g 1 = g, g 2 , h 1 , h 2 )
We define M = {(g m 1 , ĝm ) ∈ G × Ĝ} m∈Zp T.KeyGen (par T ):

• sk $ ← -Z p

• Return sk T := sk, pk T := ĝsk • LHSPS.SignDerive vk, ( -→ σ , {w i , -→ σ (i) } i=1 ) :

1. For all i ∈ {1, . . . , }, parse σ (i) as (z i , r i ).

2. Output the signature σ = ( i=1 z w i i , i=1 r w i i ).

• LHSPS.Verify(vk LHSPS , σ):

1. Parse the signature as σ = (z, r) and the message -→ M = (M 1 , . . . , M n ). Theorem A.19 ([LPJY13, Theorem 1]). The above construction of a one-time linearly homomorphic structure-preserving signature scheme is unforgeable if the SXDH assumption holds in the underlying group.

The above scheme was proven to be unforgeable under the DP assumption, which is implied by the SXDH assumption. As in the remaining part of the construction of RCCA requires SXDH to hold, we state this theorem with SXDH assumption.

Replayable-CCA encryption scheme.

An RCCA encryption scheme E consists of six PPT algorithms E = (KeyGen, Enc, ReRand, Dec, Verify, AdptPrf). It should verify the following specifications:

• E.KeyGen (Gr): a randomized algorithm which takes as input the group description and outputs an encryption public key pk and a corresponding decryption key dk.

• E.Enc (pk, m, ν): a randomized encryption algorithm which takes as input a public encryption key pk, a plaintext (from a plaintext space), some randomness and outputs a ciphertext.

• E.ReRand (pk, c, ν): a randomized algorithm which takes as input a public key, a ciphertext and some randomness,. and outputs another ciphertext.

• E.Dec (dk, c): a deterministic decryption algorithm which takes a decryption key and a ciphertext, and outputs either a plaintext or an error indicator ⊥.

• E.Verify (pk, m, ρ, c): a deterministic algorithm which takes as input a public key, a message, some randomness, and a ciphertext and outputs a bit.

• E.AdptPrf (ck, pk, c M , c, (π, c ν ) , ν ) a randomized algorithm which takes as input a commitment key, an encryption public key, a commitment, an equality proof (i.e a Groth-Sahai proof and a commitment), a ciphertext, a proof, some randomness, and outputs an equality proof.

We give the following explicit construction of the RCCA scheme supporting encryption of vectors of group elements.

E.KeyGen (Gr):

1. Parse Gr as (G, Ĝ, G T , e).

Choose two random group elements f, g

$ ← -G 2 .
1. Parse c as σ = ({c i } n i=1 , π b , π θ , π-→ v , π F GH , π-→ w ). 2. Verify that π b , π θ , π-→ v , π F GH , π-→ w are all correct.

3. Verify the following pairing equations:

c 0 = g ν c 1 = f ν c i+1 = h ν • m i .
where i ∈ {1, . . . , n}.

E.AdptPrf (ck, pk, c M , c, (π, c ν ) , ν ):

1. We just update the Groth-Sahai proof the new randomness ν by multiplying c ν = c ν • ĝν .

2. As the equality proofs consists of the following pairing equations:

c 0 = g ν c 1 = f ν c i+1 = h ν • m i .
where of Theorem 5.14. The completeness and the correctness of the above RCCA encryption scheme are straightforward to verify. We will focusing on the Replayable-CCA property. We proceed by the series of hybrid games Game 0 , . . . , Game 5 , we denote by Adv i the advantage of the adversary A to win the game Game i .

  e., a tuple that satisfies e(a, ŷ d) = e(kv, ĝ) ∧ e(b, ĝ) = e(f, d) ∧ e(v, ĝ) = e(g, ŵ).

CHAPTER

:

  Let (ck, xk) ← C.ExSetup and (sk, vk) ← S.KeyGen, and let M ∈ M; if ρ, ρ $ ← -R, then the following three are distributed equivalently: C.Cm ck, S.Sign(sk, M ), ρ , C.Prv ck, E S.Verify(vk,•,•) , (M, ρ), (Σ, ρ ) and SigCm ck, sk, C.Cm(ck, M, ρ) and SmSigCm xk, vk, C.Cm(ck, M, ρ), S.Sign(sk, M ) .

Figure 2 . 2 :

 22 Figure 2.2: Security games for rerandomizable encryption schemes

Figure 2 . 3 :

 23 Figure 2.3: Game for tag anonymity (with oracles also used in exculpability) for double-spending tag schemes

  hold, we set d τ,i := ∞ and define d τ := min{d τ.1 , d τ.2 , d τ.T }. (By non-triviality, we have d τ < ∞.) Theorem 3.5 (DLog implies Uber in the AGM). Let G be of type τ ∈ {1, 2, 3} and (

  thus upper-bounded by the probability that its maximal coefficient Q max 1 ( -→ y ) ≡ p 0 when evaluated at the random point -→ y . By the Schwartz-Zippel lemma, the probability that Q 1 (Z) ≡ 0 is thus upper-bounded by d p-1 . The degree d of Q 1 (and thus of Q max 1 ) is upper-bounded by the total degrees of P 1 , which is max{d R , d-→ R , d-→ S } = d 2.1 in Def. 3.4. B alg thus aborts in line (*) with probability at most

Figure 3 . 2 :

 32 Figure 3.2: Algebraic game for the flexible Uber assumption

3 . 3 :

 33 Figure 3.3: Algebraic game for the Uber assumption relative to bilinear group G and adversary A alg , parametrized by (vectors of) rational fractions -→ R , -→ S , -→ F , R , S and F

Figure 3 . 4 :

 34 Figure 3.4: Algebraic game for the flexible-targets Uber assumption

T ) Definition 3 .

 3 13 (Degree of non-triviality for Gegenuber assumption).Let (Q 1 , Q 2 , Q T , R * , S * , F * ) be a non-trivial tuple of polynomials in Z p [X 1 , . . . , X m ]. For i ∈ {1, 2, T } define d i := max{deg P } P ∈Q i . We define the type-τ degree d τ of (Q 1 , Q 2 , Q T ,R * , S * , F * ) as follows: • If (τ.1) holds, let d τ.1 := max{1, deg R * } • max{d 1 , d 2 } in case τ ∈ {1, 2} and d τ.1 := max{1, deg R * } • d 1 in case τ = 3. • If (τ.2) holds, let d τ.2 := max{1, deg S * } • max{d 1 , d 2 } in case τ = 1 and d τ.2 := max{1, deg S * } • d 2 in case τ ∈ {2, 3}.

Figure 4 . 1 :

 41 Figure 4.1: Games for ciphertext-indistinguishability and class-hiding

Figure 4 . 3 :

 43 Figure 4.3: Our instantiation SRC of SoRC

Figure 4

 4 Figure 4.4: Games for decisional Diffie-Hellman and class-hiding instantiated with SRC from Fig. 4.3

1 ,

 1 X1 ) e(G, Ŝ * ) = e(S * , Ĝ) (4.22) e(T * , Ŝ * ) = e(G, X0 )e(P (k+1) , X1 ) (4.23)

BWith()

  plays the bank side of the Withdraw protocol. Coins withdrawn by A (and thus unknown to the experiment) are not added to the coin list CL. UWith(i) plays user i in Withdraw when the bank is controlled by the adversary. Upon obtaining a coin c, it adds (owner = i, c, cds = 0, origin = A) to CL. With(i) simulates a Withdraw protocol execution playing both B and user i. It adds (owner = i, c, cds = 0, origin = B) to CL. Spend and deposit oracles. Rcv(i) makes user i receive a coin from A. The oracle plays the role of U with user i's secret key in the Spend protocol. It adds a new entry (owner = i, c, cds = 0, origin = A) to CL.

CHAPTER 5 .Figure 5 . 1 :

 551 Figure 5.1: Game for soundness (protecting users from financial loss)

Figure 5 . 2 :Figure 5 . 3 :

 5253 Figure 5.2: Game for unforgeability (protecting the bank from financial loss)Expt excul A (λ): par ← ParamGen(1 λ ); pk B ← A (par) (i * , Π * ) ← A URegist,Spy,UWith,Rcv,Spd,S&R,UDepo (par) Return 1 if all of the following hold:-VfyGuilt(pk i * , Π * ) = 1 -There was no call Spy(i * ) uds i * = 0 Return 0 Figure 5.3: Game for exculpability (protecting honest users from accusation)

CHAPTER 5 .

 5 TRANSFERABLE E-CASH: A CLEANER MODEL AND THE FIRST PRACTICAL INSTANTIATION Expt c-an A,b (λ): par

Figure 5 . 4 :

 54 Figure 5.4: Games for coin and user anonymity (protecting users from a malicious bank)

Figure 5 . 5 :

 55 Figure 5.5: Game for coin transparency (protecting users from malicious users)

C

  = C.Setup, C.Cm, C.RdCm, C.ExSetup, C.Extr, C.Prv, C.Verify, C.AdptPrf , to which we add compatible schemes: an M-structure-preserving signature scheme S = (S.Setup, S.KeyGen, S.Sign, S.Verify), admitting an M-commuting signature add-on SigCm, as well as an M -structure-preserving signature scheme S ; furthermore a double-spending tag scheme T = T.Setup, T.KeyGen, T.SGen, T.SGen init , T.SVfy, T.SVfy init , T.TGen, T.TVfy, T.Detect, T.VfyGuilt , as well as two randomizable encryption schemes E = (E.KeyGen, E.Enc, E.ReRand, E.Dec, E.Verify, E.AdptPrf), and E . (We require E to satisfy RCCA security, whereas E need only be IACR-secure).

  init pk i T , sn i , M i = 1, then B 3 won the soundness game.Assume |S| i=1 T.SVfy init pk i T , sn i , M i = 1. Since T is bootable, we have|{sn i } |S| i=1 | ≤ |{M i } |S| i=1 |, from which we deduce |{sn i } |S| i=1 | ≤ q W <|DCL| (the last inequality comes from we suppose we are in E counterfeit ). Note that by construction of DCL, all the initial serial numbers of his elements are differents. Let call this set I.By |I| = |DCL|, we deduce |I| > |{sn i } |S| i=1 |. By construction |I| = |{E .Dec(dk init , ci sn )} |S| i=1 |, then |{E .Dec(dk init , ci sn )} |S| i=1 | > |{sn i } |S| i=1 |. Let i 0 be such that E .Dec(dk init , ci 0 sn ) ∈ |{sn i } |S| i=1 |.It means that by correctness of E E .Enc pk, sn i 0 , ν i 0 = ci 0 sn , and thus (still because of the correctness of E ) E .Verify pk, sn i 0 , ν i 0 , ci 0 sn = 1.We deduce that |S| i=1 E .Verify pk, sn i , ν i , ci sn = 1, and consequently B 3 won the soundness game. We thus have E counterfeit \ E sig ⊆ E com,1 . Now we build the following algorithm to break unforgeability of S : Adversary B A,S .Sign * (sk ,•) 2 par S , vk : Initialize UL as an empty list Extract Gr from par S (ck, xk) ← C.ExSetup (Gr) par S ← S.Setup (Gr)( -→ i (0) , -→ i (1) ) ← A URegist,Spy Let k := | -→ i (0) |; if k = | -→ i (1)|, abort the entire procedure Then repeat the following step for j = 1, . . . , k:Run S&R ZK (2j -1, ( -→ i (0) ) j ); Run S&R ZK (2j, ( -→ i (1) ) j ) Run Spd ZK (2k + 1 + b) with A Run Spd ZK (2k + 2 -b) with A b * ← A Return b *Because, we are in the hiding mode the following property follows directly of the perfect zero-knowledge in hiding mode: Property A.7. | Pr(Expt c-an A,0,hiding (λ)) -Pr(Expt c-an A,0,ZK (λ))| = 0.

  sn ) ← T.SGen init (sk i 0 , n (0) ) c cert ← C.SmPrv(td, S .Verify(vk , •, •) = 1, ρ sn ← C.SmPrv sn,init (td, ρ A Compute C.Verify(ck, S.Verify(vk, •, •) = 1, c σ , π σ ) If it fails, output ⊥ else continue; ν sn ← C.SmPrv enc (td, ek, ρ ρ (0) ) pk CL ← [(i 0 , c (0) 1 , 0, A)] i 1 ← A URegist,Spy n (1) $← -N ; ρ , and compute:

  cert ← C.SmPrv(td, S .Verify(vk ,•, •) = 1, ρ sn ← C.SmPrv sn,init (td, ρ σ ) from A If C.Verify(ck, S.Verify(vk, •, •) = 1, c (0) M , c (0) σ , π σ ) fails, then output ⊥ else continue i 1 ← A URegist,Spyρ cert ← C.SmPrv(td, S .Verify(vk , •, •) = 1, ρ sn ← C.SmPrv sn,init (td, ρ

  A If C.Verify(ck, S.Verify(vk, •, •) = 1, c (1) M , c

  σ ) fails, then output ⊥n (0) , n (1) $ ← -N ; (sn (0) , M (0) sn ) ← T.SGen init (sk i 0 , n (0) ) (sn (1) , M (1) sn ) ← T.SGen init (sk i 1 , n (1) )A.1. SECURITY PROOFS FOR THE TRANSFERABLE E-CASH SCHEME 107 ν sn ← E.Enc(ek, sn (0) , ν sn ← E.Enc(ek, sn (1) , ν sn ← C.SmPrv enc (td, ek, ρ sn ← C.SmPrv enc (td, ek, ρ

  ) ← A URegist,Spy Let k := | -→ i (0) |; if k = | -→ i (1)|, abort the entire procedure Then repeat the following step for j = 1, . . . , k:Run S&R ZK (2j -1, ( -→ i (0) ) j , ); Run S&R ZK (2j, ( -→ i (1) ) j ) Run Spd ZK (2k + 1 + b) with A Run Spd ZK (2k + 2 -b) with A b * ← A Return b *And because this swap is transparent for the adversary, it implies the following game swap:Property A.8. | Pr(Expt c-an A,0,ZK (λ)) -Pr(Expt c-an A,0,ZKV2 (λ))| = 0.Now we have to swap the serial numbers. To do that we define two new procedures:DoubleUWith A rev : i 0 ← A URegist,Spy

  sn ← C.ZCm(ck, ρ (0) sn ); c (0) pk ← C.ZCm(ck, ρ (0) pk ) c (0)M ← C.ZCm(ck, ρ (0) M ) π (0) cert ← C.SmPrv(td, S .Verify(vk , •, •) = 1, ρ (0) pk , ρ (0) cert ) par ← (1 λ , par S , par S , par T , ck) pk B ← A(par) (i 0 , i 1 ) ← DoubleUWith A rev ( -→ i (0) , -→ i (1) ) ← A URegist,Spy Let k := | -→ i (0) |; if k = | -→ i (1)|, abort the entire procedure Consider i 0 as ( -→ i (0) ) 0 , and i 1 as ( ) ) j ].sk Then repeat the following step for j = 1, . . . , k :Run S&R ZK,inv (2j -1, ( -→ i (0) ) j , UL[( -→ i (1) ) j-1 ].sk, UL[( -→ i (1) ) j ].sk); Run S&R ZK,inv (2j, ( -→ i (1) ) j , UL[( -→ i (0) ) j-1 ].sk, UL[( -→ i (0) ) j ].sk) Run Spd ZK,inv (2k + 1 + b) with A Run Spd ZK,inv (2k + 2 -b) with A b * ← A Return b *Analogously to two previous properties we deduce: Property A.11. | Pr(Expt c-an A,0,ZKV2,k-1 (λ)) -Pr(Expt c-an A,0,ZKV2,k (λ))| ≤ 2 t-an .

2 .

 2 Return 1 iff (M 1 , . . . , M n ) = (1 G , . . . , 1 G ) and the following equation is verified. e(z, ĝz ) • e(r, ĝr ) = n i=1 e(M i , ĝi ).

  and deg(F 1 + F 2 ) ≤ max{deg F 1 , deg F 2 }.

	Schwartz-Zippel lemma. We will use the following version of the Schwartz-Zippel lemma
	[DL77]:
	Lemma 2.1. Let P ∈ Z p [X 1 , . . . , X m ] be a non-zero polynomial of total degree d. Let r 1 , . . . , r m
	be selected at random independently and uniformly from Z * p . Then
	Pr P (r 1 , . . . , r m ) ≡ p 0 ≤	d p -1	.
	We state the following technical lemma, which we will use in our reductions.

Lemma 2.2. Let P be a non-zero multivariate polynomial in Z p [X 1 , . . . , X m ] of total degree d. Define

  R gen is generic and if for every algebraic algorithm A alg , algorithm B alg defined as B alg := R

	A alg gen satisfies

  .1: Algebraic game for the Uber assumption relative to bilinear group G and adversary A alg , parametrized by (vectors of) or polynomials

	-→ R ,	-→ S ,	-→ F , R , S and F
	We have argued above that if the tuple (

  , S , F ) being nontrivial, which correspond to conditions (2.1), (2.2) and (2.T) in Def. 3.3. Each condition enables a different type of reduction, of which B alg runs the one that minimizes d 2 from Def. 3.4.

	We start with Case (2.1), that is, R is linearly independent from	-→ R and	-→ S .

Adversary B alg (g 2 , Z 1 , . . . , Z q ): On input a problem instance of game q-dlog G 2 with

Z i = [z i ] 2 ,

B alg simulates über G for A alg . It defines g 1 ← ψ(g 2 ) and g T ← e(g 1 , g 2 ). Then, it picks random values -→ y $

  the zero polynomial then B alg aborts. ( * ) Else, it factors Q 1 to obtain its roots z 1 , . . . (of which there are at most max{deg R , d-→ R , d-→ S }; we analyse the degree of Q 1 below). If for one of them we have g z i 2 = Z, then B alg returns z i .We analyze B alg 's success probability. First note that B alg perfectly simulates game über G , as the values x i are uniformly distributed in Z p and alg does not abort in ( * ) and A alg wins game über G

	-→ U,	-→ V and	-→ W are correctly computed. Moreover,
	if B

  .4. THE RUBER ASSUMPTION FOR FLEXIBLE TARGETS 37 If (τ, i) does not hold, set d τ,i := ∞. Define d τ := min{d τ.1 , d τ.2 , d τ.T }. (DLog implies Uber for rational fractions in the AGM). Let G be a bilinear group of type τ ∈ {1, 2, 3} and let (

	Theorem 3.9

  Figure 3.7: Game for 2-one-more discrete logarithm 2-omdl G i relative to bilinear group G i , i ∈ {1, 2} and adversary A algProof. Let R alg be an algebraic reduction s.t. for every algorithm A alg that (t, )-breaks 2-omdl G i ,

07

Return log g Z 08 Return ⊥

  Now suppose LCM(P 1 , . . . , P n )( -→ x ) ≡ p 0. Since LCM(P 1 , . . . , P n ) divides n i=1 P i , we have n i=1 P i ( -→ x ) ≡ p 0. Because Z p is an integer domain, this implies that P i ( -→ x ) ≡ p 0 for some i.

and only if LCM(P 1 , . . . , P n )( -→ x ) ≡ p 0.

Proof. Let i be such that P i ( -→ x ) ≡ p 0. Since P i divides LCM(P 1 , . . . , P n ), we have LCM(P 1 , . . . , P n )( -→ x ) ≡ p 0.

  and only if a least common denominator of all these polynomials vanishes at -→ x , i.e. D( -→ x ) ≡ p 0 (by Lemma 3.19), and B alg only proceeds if the latter is not the case. In this case alg does not stop in line ( * * ) either and A alg is successful then

	A alg 's inputs,	-→ U,	-→ V and	-→ W are correctly computed.
	If B

  1 in Def. 3.13. B alg thus aborts in line (*) with probability at most

	d 2,1 p-1 . Cases (2.2) (where we have S * / ∈ FrSp(Q 2 )) and (2.T ) are treated analogously. Theorem 3.14
	for Type-2 groups now follows because
	Adv

  .50) CHAPTER 4. SIGNATURES ON RANDOMIZABLE CIPHERTEXTS Considering the linear coefficient in x 0 , and recalling that φ s,i 0 = 0 by (4.43), we deduce ∀ i > i 0 : γ

		(k+1) z,i	= ζ t,i = 0 .	(4.51)
	Applying this to equation (4.50) yields x 2 0 γ	(k+1) t,i

  Ŝj and Z * = ζG + Z j + ζ s,j S j + ζ t,j T j . By (4.44), (4.38), (4.39) and (4.35) we have Ŝ * = φ s,i 0 Ŝi 0 Moreover, by (4.47), (4.36), (4.33), (4.51) and (4.58) we have Z * = ζ z,i 0 Z i 0 + ζ t,i 0 T i 0 . We can now rewrite (4.24) as:

	4.3. SECURITY OF OUR SCHEME			65
	Recall that Ŝ * = φ Ĝ + φ 0 X0 + φ 1 X1 +	k	φ s,j k	ζ z,j
		j=1	j=1
				.59)

  ParamGen(1 λ ); ((sk W , sk D , sk CK ), pk B ) ← BKeyGen(par) DCL ← ∅ // lists the challenge coins ctr ← 0 // counts how often a challenge coin was deposited i (0) ← A URegist,BDepo ,Spy (par, pk B , sk W , sk D ) // BDepo uses CheckDS •, •, •, •, DCL (see below) instead of CheckDS Run Rcv(i (0) ) with A; let c 0 be the received coin stored in CL[1]

	5.2. COMPARISON WITH PREVIOUS WORK	73
	Expt c-tr A,b (λ):
	par ←

is negligible in λ for any PPT adversary A.

  sn,init (ck, pk T , sn, M, ρ pk , ρ sn , ρ M ):-πsn ← C.E .Prv enc (ck, ek init , sn, ρ sn , ν sn , csn ) ρ pk , ρ cert , ρ sn , ρ M , ρ σ , ν sn , ρ π,sn Rand (c pk , c cert , π cert , c sn , π sn , c M , c σ , π σ , csn , πsn ), (ρ pk , ρ cert , ρ sn , ρ M , ρ σ , ν sn , ρ π,sn )-Output c 0 , n, sn, ρ sn + ρ sn , ρ pk + ρ pk Spend U(c, sk U = (cert, pk T , sk T ), pk B = (ek init , ek, vk, vk )), U (sk U = (cert , pk tag , sk tag ), pk B ) :

	$ ← -R	//since πsn contains a commitment,
		we also sample randomness for it
	-c 0 ←

  -(tag, t-pf ) ← T.TGen(par T , sk T , n, sn )c tag ← C.Cm(ck, tag, ρ tag ) -ctag ← E.Enc(ek, tag, ν tag ) π tag ← C.Prv tag (ck, pk T , sn, sn , tag, t-pf , ρ pk , ρ sn , ρ sn , ρ tag , ρ t-pf ) -πtag ← C.E.Prv enc (ck, ek, tag, ρ tag , ν tag , ctag ) -Send c = c 0 , (c j ) i j=1 , c tag , π tag , ctag , πtag to U ; output ok U :-If any of the following fail then abort and output ⊥:-VER init (ek init , c 0 )-VER body (ek, vk, vk , c j-1 , c j ), for j = 1, . . . , i -C.Verify tag (ck, c i pk , c i sn , c sn , c tag , π tag ) -C.E.Verify enc (ck, ek, c tag , ctag , πtag ) Rand ((c j ) i j=0 , c pk , c cert , π cert , c sn , π sn , c tag , π tag , c sn , π sn , c tag , π tag ), Let A be an adversary that wins the game exculpability with advantage and makes u calls to the oracle URegist. Then there exist adversaries against mode-indistinguishability of C and tag-exculpability of T with advantages m-ind and t-exc , resp., such that ≤ u • t-exc + m-ind .

	-pick uniformly at random	-→ ρ
	-c rand ← -→ ρ

j tag , cj sn , cj tag , πj sn , πj tag )) i j=1 n, sn, ρ sn , ρ pk ρ tag , ν tag , ρ t-pf $ ← -R -Output c rand , n , sn , ρ sn + ( -→ ρ ) sn , ρ pk + ( -→ ρ ) pk

CheckDS sk CK = (dk init , dk), DCL, UL, c : Theorem 5.7.

  for the details of our analysis. After k transfers the size of a coin is|c btsrap | + k|c std |. W ≥ |DCL|, then abort Let D := ∅ For c ∈ Coins D :Parse c as c 0 , (c j ) i j=1 , n, sn, ρ sn , ρ pk Add c 0 to S

	If q Parse S as c i pk T , c i cert , π i cert , c i sn , π i sn , c i M , c i σ , π i σ , ci sn , πi sn 1≤i≤|S|
	Parse πi sn as c i , π i
	Send	|S| i=1	E .Verify ek init , X i 1 , X i 2 , ci sn ∧ S.Verify vk, X i 3 , X i 4 = 1∧
	T.SVfy init X i 5 , X i 1 , X i 3	,
	c 1 sn , c 1 , c 1 M , c 1 σ , c 1 pk T , . . . , c	|S| sn , c |S| , c |S| M , c |S| σ , c |S| pk T ,
						|Π guilt |	2|G|
			|pk B |	15|G| + 8| Ĝ|	|c btstrap | 6|Z p | + 147|G| + 125| Ĝ|
			|sk U | |Z p | + 2|G| + 2| Ĝ|	|c std |	54|G| + 50| Ĝ|
			|pk U |		| Ĝ|	|( -→ sn,	-→ tag)|	(4t + 2)|G|

|sk B | 9|Z p | + 2|G| + 2| Ĝ| |S| i=1

  i ∈ {1, . . . , n}.

	Public Key	(10 + n)G + 4	Ĝ
	Decryption Key	nZ p
	Ciphertext	(6n + 19)G + (16 + 4n)	Ĝ
	Verification equations	2 Linear + n quadratic
	size of the equality proof	(2 + 2n)G + (2 + 4n)	Ĝ

We did not consider the bound from [Boy08, Theorem 1], as it is an incorrect copy of the one in[START_REF] Boneh | Hierarchical identity based encryption with constant size ciphertext[END_REF].

Considering an equation of rational fractions over this quotient can also be seen as simply setting x0 = x1 = 0. Everything we infer about the coefficients from these modified equations is also valid for the original equation, since these must hold for all values (x0, x1, s1, . . . , s k ) and so in particular for (0, 0, s1, . . . , s k ).Yet another interpretation when equating coefficients in equations modulo (x0, x1) is that one equates coefficients only of monomials that do not contain x0 or x1.

We use the oracle only at these step, for the other serial number and tag generations, we use the secret keys (which we have generated) like in the Expt c-an A,0,ZKV2 .

Acknowledgments

Correctness and security definitions

Correctness of SoRC requires that the encryption scheme and the signature scheme are correct. Note that together with signature-adaptation (Def. 4.5 below), this implies that adapted signatures verify as well. We also require that the encryption scheme satisfies the standard security notion. Class-hiding is a property of equivalence-class signatures that states that given a representative of an equivalence class, then a random member of that class is indistinguishable from a random element of the whole space. We give a stronger definition, which we call fully class-hiding (analogously to full anonymity). Whereas in the original notion [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF]Def. 18], the representative is uniformly picked by the experiment, in our notion it is chosen by the adversary.

Definition 4.4. Let game CL-HID be as defined in Fig. 4.1. A SoRC scheme is fully class-hiding if for all p.p.t. adversary A, the following function is negligible in λ:

Pr CL-HID A SRC (λ, 1) = 1 -Pr CL-HID A SRC (λ, 0) = 1 .

Signature-adaptation requires that signatures that have been adapted to a randomization of the signed ciphertext are distributed like fresh signatures on the randomized ciphertext. A strengthening is the following variant, which also holds for maliciously generated verification keys [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF]Def. 20].

Definition 4.5. A SoRC scheme is signature-adaptable (under malicious keys) if for all p ∈ PP, all (vk, ek, c, sig) ∈ VK p × EK p × C p × S p that satisfy Verify(vk, ek, c, sig) = 1 and all r ∈ R p , the output of Adapt(sig, r) is uniformly distributed over the set sig ∈ S p Verify vk, ek, Rndmz(ek, c, r), sig = 1 . Note that if Sign outputs a uniform element in the set of valid signatures (which is the case in the ECS scheme from [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF] and our scheme) then Def. 4.5 implies that for all honestly generated (sk, vk) and all ek, c and r the outputs of the following two procedures are distributed equivalently:

INSTANTIATION

Adapt Sign(sk, ek, c), r and Sign sk, ek, Rndmz(ek, c, r ) . (4.7)

Together, full class-hiding and signature-adaptability under malicious keys imply that for an adversary that creates a signature verification key as well as a ciphertext and a signature on it, a randomization of this ciphertext together with an adapted signature looks like a random ciphertext with a fresh signature on it. (In contrast, for equivalence-class signatures, this was only true if the signed message was not chosen by the adversary [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF].)

Unforgeability. Finally, we present our strengthened notion of unforgeability, which is defined w.r.t. keys and equivalence classes. That is, after the adversary queries a signature for (ek, c), all tuples (ek, c ) with c ∈ [c] ek (that is, c encrypts the same message as c under ek) are added to a set Q of signed objects. The adversary's goal is to produce a signature on a pair (ek * , c * ) that is not contained in Q. (In the original definition [START_REF] Blazy | Signatures on randomizable ciphertexts[END_REF], Q would contain the equivalence classes of c under all encryption keys, i.e., all encryptions of the plaintext of c under all keys.) Definition 4.6. Let EUF be the game defined in Fig. 4

.2. A SoRC scheme is unforgeable is for all p.p.t. adversary A the following function is negligible in λ:

Pr EUF A SRC (λ) = 1 .

Instantiation

Our instantiation of SoRC is given in Fig. 4.3. Its signatures sign ElGamal ciphertexts (C 0 , C 1 ), and the signature elements (Z, S, Ŝ) constitute a structure-preserving signature on (C 0 , C 1 ) similar to the optimal scheme from [START_REF] Abe | Optimal structure-preserving signatures in asymmetric bilinear groups[END_REF]. (And removing G from the definition of Z would yield the equivalence-class scheme from [START_REF] Fuchsbauer | Structure-preserving signatures on equivalence classes and constant-size anonymous credentials[END_REF]: note that, without G, multiplying Z by r yields a signature on the message r • (C 0 , C 1 ).) The new element T in our scheme allows for adaptation of signatures to randomizations of the signed ciphertext. Randomization implicitly defines the following equivalence classes: for P ∈ EK p and (C 0 , C 1 ), (C 0 , C 1 ) ∈ C p :

(C 0 , C 1 ) ∈ (C 0 , C 1 ) P ⇐⇒ ∃ r ∈ Z p : (C 0 , C 1 ) = (C 0 + rG, C 1 + rP ) .

Security of our scheme

Correctness of our scheme follows by inspection. Moreover, ElGamal encryption [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] satisfies IND-CPA if the decisional Diffie-Hellman (DDH) assumption holds for BGGen.

Property 4.7. If DDH holds for BGGen then the scheme in Fig. 4.3 is fully class-hiding (Def. 4.4).

CHAPTER 5. TRANSFERABLE E-CASH: A CLEANER MODEL AND THE FIRST PRACTICAL INSTANTIATION

Withdraw B(sk W ), U(sk U , pk B ) is run between the bank and a user, who outputs a coin c (or ⊥), while the bank outputs ok (in which case it debits the user's account) or ⊥.

Spend U(c, sk, pk B ), U (sk , pk B ) is run between two users and lets U spend a coin c to U (who could be the bank). U outputs a coin c (or ⊥), while U outputs ok (or ⊥).

CheckDS (sk CK , UL, DCL, c), run by the bank, takes as input its checking key, the lists of registered users UL and of deposited coins DCL and a coin c. It outputs an updated list DCL (when the coin is accepted) or a user public key pk U and an incrimination proof Π.

VfyGuilt (pk U , Π) can be executed by anyone. It takes a user public key and an incrimination proof and returns 1 (acceptance of Π) or 0 (rejection).

Note that we define a transferable e-cash scheme as stateless: there is no common state information shared between the algorithms. This means that a coin withdrawn will be the same, whether it was the first or the n-th coin the bank issues to a specific user. Moreover, when a user U receives a coin from a user U, then the transferred coin will only depend on the original coin (not on other coins received by U or coins transferred by U). Thus, the bank and the users need not store anything about past transactions for transfer; the coin itself must be sufficient.

In particular, the bank can separate withdrawing from depositing, in that CheckDS, used during deposit, need not be aware of the withdrawn coins.

Correctness properties

These properties were not stated in previous models. We believe they are important, as they preclude schemes that satisfy security notions by not doing anything.

Let par be an output of ParamGen(1 λ ) and (sk B = (sk W , sk D , sk CK ), pk B ) be output by BKeyGen(par) and let sk and sk be two user outputs of Register. Then the following holds (while correctness of CheckDS and VfyGuilt is implied by the security definitions below):

• none of the outputs is ⊥;

• any execution of Register B(sk W ), U(pk B ) yields output pk for B and sk for U;

• any execution of Withdraw B(sk W ), U(sk, pk B ) yields ok for B and c for U;

• in an execution of Spend U(c, sk, pk B ), U (sk , pk B ) , no party outputs ⊥;

• and sk D works as a user secret key sk .

Security definitions

Global variables

In our security games, we store all information about users and their keys in the user list UL. Its entries are of the form (pk i , sk i , uds i ), where uds i indicates how many times user U i has double-spent.

In the coin list CL, we keep information about the coins created in the system. For each withdrawn or spent coin c, we store a tuple (owner, c, cds, origin), where owner stores the index i of the user who withdrew or received the coin (we do not store coins withdrawn or received by the adversary). We also include cds, which counts how often this specific instance of the coin has been spent. In origin we write "B" if the coin was issued by the honest bank and "A" if it originates from the adversary; if the coin was originally spent by the challenger itself, we store a pointer indicating which original coin this transferred coin corresponds to. Finally, we maintain a list of deposited coins DCL.

C.E.Verify enc (ck, ek, c M , cM , πeq = (π eq , c ν )):

Components of the coin.

There are two types of components, the initial components C init , and the standard components C std . The first is of the form

consisting of commitments (the c-values) to the withdrawer's key pk, her certificate cert, the initial serial number sn and the related message M , the bank's signature σ on M , and an encryption csn of sn. It also contains proofs π cert and π sn of validity of cert and sn and a proof πsn that c sn and csn contain the same value. We use to pad so that both types of component have the same format.

Validity of an initial component is verified w.r.t. an encryption key (that can be for either E or E ) and two signature verification keys for S and S :

VER init ek, vk, vk , coin init : Return 1 iff the following hold: // coin init as in (5.1) -C.Verify(ck, S.Verify(vk,

sn Standard components of a coin are of the form

and instead of M and the bank's signature they contain a commitment c tag and an encryption ctag of the tag produced by the spender (and a proof π tag of validity and πtag proving that the values in c tag and ctag are equal). A coin is verified by checking the validity and consistency of each two consecutive components. If the first is an initial component then the values c i-1 tag , π i-1 tag , ci-1 tag and πi-1 tag are ; if it is a standard component then c M , c i-1 σ and π i-1 σ are .

sn , ci-1 tag , πi-1 tag , coin std : // coin std as in (5.2) Return 1 iff the following hold: Using the above, we now give the formal definition of our transferable e-cash scheme. (Recall that par is an implicit input to all algorithms.)

ParamGen(1 λ ):

• Gr ← BGGen(1 λ )

• par S ← S.Setup(Gr)

• par S ← S .Setup(Gr) CHAPTER 5. TRANSFERABLE E-CASH: A CLEANER MODEL AND THE FIRST PRACTICAL INSTANTIATION

• par T ← T.Setup(Gr)

• ck ← C.Setup(Gr)

• Return par = (1 λ , Gr, par S , par S , par T , ck)

BKeyGen():

• Parse par as (1 λ , Gr, par S , par S , par T , ck)

• (sk, vk) ← S.KeyGen(par S )

• (sk , vk ) ← S .KeyGen(par S )

• (ek init , dk init ) ← E .KeyGen(Gr)

• (ek, dk) ← E.KeyGen(Gr)

• (sk T , pk T ) ← T.KeyGen(par T )

• cert ← S .Sign(sk , pk T ) • Else let j be minimal so that ( -→ sn

VfyGuilt(pk T , Π): Return T.VfyGuilt(pk T , Π)

Correctness and security analysis

Theorem 5.5. Our transferable e-cash scheme satisfies all correctness properties and is perfectly sound.

The first four correctness properties follow in a straightforward way from the correctness properties of S, S and C, and verifiability of T. The fifth property follows from the fact that sk D has the form of a customer secret key.

Because a user verifies the validity of all components of a coin before accepting it, perfect soundness of our scheme is a direct consequence of the correctness properties of S, S and C, and in particular perfect soundness of C, as well as verifiability of T.

The detailed proofs of the following theorems can be found in Appendix A.1. We omit the proofs for u-an and c-tr as they are analogous to the one for c-an. Theorem 5.6. Let N be the nonce space and S be the space of signatures of scheme S. Let A be an adversary that wins the unforgeability game with advantage and makes at most d calls to BDepo. Suppose that C is perfectly sound and (M ∪ S)-extractable. Then there exist adversaries against the unforgeability of the signature schemes S and S with advantages sig and sig , resp., such that

Assume that during the adversary's deposits the bank never picks the same final nonce twice. (The probability that there is a collision is at most d 2 /|N |.) In this case, there are two ways for the adversary to win:

(1) CheckDS outputs ⊥, or an invalid proof, or an unregistered user: Suppose that, during a BDepo call for a coin c, CheckDS does not return a coin list. Recall that, by assumption, the final part (chosen by the bank at deposit) of the serial number of c is fresh. Since CheckDS runs T.Detect, by soundness of C and two-extractability of T, this will output a pair (pk, Π), such that VfyGuilt(pk, Π) = 1. Since a coin contains a commitment to a certificate for the used tag key (and proofs of validity), we can, again by soundness of C, extract an S -signature on pk. Now if pk is not in UL, then it was never signed by the bank, and A has thus broken unforgeability of S .

(2) q W < |DCL|: If the adversary creates a valid coin that has not been withdrawn, then by soundness of C, we can extract a signature by the bank on a new initial serial number and therefore break unforgeability of S. PRACTICAL INSTANTIATION As for c-an and u-an, the reduction first makes all commitments perfectly hiding and proofs perfectly simulatable (which loses m-ind twice). Since all ciphertexts in the challenge coin given to the adversary are randomized, the reduction can replace all of them, except the initial one, by IACR-security of E. (Note that in the game these ciphertexts never need to be decrypted.) The factor 2 is due to the fact that there are at most encryptions of SN/tag pairs. Finally, replacing the initial ciphertext (the one that enables detection of double-spending) can be done by a reduction to RCCA-security of E : the oracle Depo can be simulated by using the reduction's own oracles Dec and GDec oracles (depending on whether Depo is called before or after the reduction receives the challenge ciphertext) in the RCCA-security game. Note that, when during a simulation of CheckDS, oracle GDec outputs replay, the reduction knows that a challenge coin was deposited, and thus increases ctr.

Instantiation of the building blocks and efficiency

The instantiations we use are all proven secure in the standard model under non-interactive hardness assumptions.

Commitments and proofs.

The commit-and-prove system C will be instantiated with Groth-Sahai proofs [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], of which we use the instantiation based on SXDH.

Theorem 5.11 ([GS08]). The Groth-Sahai scheme with values

extractable, mode-indistinguishable assuming SXDH, and perfectly hiding in the hiding mode.

We note that moreover, all our proofs can be made zero-knowledge [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], because all pairingproduct equations we use are homogeneous (i.e., the right-hand term is the neutral element). We have (efficient) extractability, as we only need to efficiently extract group elements from commitments (and not scalars) in our reductions. (Note that for information-theoretic arguments concerning soundness, Extr can also be inefficient.) Signature schemes. For efficiency and type-compatibility reasons, we use two different signature schemes. The first one needs to support the functionality SigCm, which implies a specific format of messages. The second scheme is less restrictive, which simplifies the description of our scheme and makes its instantiation more efficient. While all our other components rely on standard assumptions, the following scheme is secure under a non-interactive q-type assumption defined in [AFG + 10].

Theorem 5.12. The signature scheme from [AFG + 10] with message space M := {(g m , ĝm ) | m ∈ Z p } is (strongly) unforgeable assuming q-ADHSDH and AWFCDH (defined in Section 2.3), and it supports the SigCm functionality [START_REF] Fuchsbauer | Commuting signatures and verifiable encryption[END_REF].

Theorem 5.13. The signature scheme described in [AGHO11, Section 5] is structure-preserving with message space M := G 2 and (strongly) unforgeable assuming SXDH.

Randomizable encryption schemes.

To instantiate the RCCA-secure scheme E we follow the approach from [START_REF] Libert | Structure-preserving chosen-ciphertext security with shorter verifiable ciphertexts[END_REF]. Their construction is only for one group element, but by adapting the scheme, it can support encryption of a vector in G n for arbitrary n.

In our e-cash scheme, we need to encrypt a vector in G 2 , and since it is not clear whether more recent efficient schemes like [START_REF] Faonio | Structure-preserving and re-randomizable RCCA-secure public key encryption and its applications[END_REF] can be adapted to this, we give an explicit construction, which we detail in Appendix A.2.

INSTANTIATION OF THE BUILDING BLOCKS AND EFFICIENCY

Appendix A A.1 Security proofs for the transferable e-cash scheme

Remark that some of our theorems in the appendix are more general than the ones in the body of the thesis, as they work for a scheme with only computational soundness of C (whereas in the body we assume perfect soundness).

Unforgeability

Theorem A.1. Suppose that there exists an adversary A against unforgeability with advantage unforg and using at most d calls to oracle BDepo. Suppose that M and the signature space of S are included in V . Then we can build a polynomial-time adversary B 1 against the unforgeability of the signature scheme S with advantage sig , an adversary B 2 against the unforgeability of S with advantage sig , and B 3 and B 4 against the soundness of the commitment scheme C with advantage h,1 and h,2 . Then

Sketch of proof Note that the adversary has two possibilities to break the game: either it creates counterfeit (i.e., q W < |CL|), or it wins by making a deposit fail (because CheckDS does not output neither a list nor a valid pair with a registered user key). In our proof we will prove separately the security of these two aspects. First we will prove in property A.2, that creating counterfeit is harder than breaking the unforgeability of S, or proving a false statement in C. In a second step, in property A.3, we prove that if fresh nonces are picked every time during the deposits, then it is harder to make Deposit fail than breaking the unforgeability of S', or proving a false statement in C.

We first recall the security games involved. The unforgeability against the e-cash system:

If in a BDepo call, CheckDS does not return a coin list Return 1 if any of the following hold:

-CheckDS did not output a pair (pk, Π) -VfyGuilt(pk, Π) = 0 pk ∈ UL Let q W be the number of calls to BWith If q W < |DCL| then return 1 Return 0 and the unforgeability game against a signature scheme:

Finally, the soundness of the commitment scheme:

Let E unforg be the event that A wins the game. Then it means that, at some point after a call to BDepo, CheckDS did not output a list or q W < |DCL|. We partition E unforg as follows:

• E Decrypt-fails : In CheckDS, a decryption fails or does not output any serial number and tag, when it is supposed to;

• E same : In CheckDS, we do not find any j such that -→ sn j = -→ sn j ;

• E DDS-fails : In CheckDS, T.Detect does not output any (pk T , Π G );

• E incorrect : CheckDS outputs (pk i * , Π G ) such that VfyGuilt (pk i * , Π G ) = 0;

• E not-register : pk i * ∈ UL;

We can first build the adversary B 1 against the unforgeability of S, this adversary will bet on E counterfeit : q W < |DCL| (id est A creates valid money). It means that A has forged a commited signature for a fresh serial number and thus forged a signature for a fresh serial number or a false ZK-proof for the equation S.Verify (And in this second case B 3 will break soundness). One may notice that to simulate SigCm, B 1 needs xk and SmSigCm.

Adversary B

A,S.Sign * (sk,•) 1

In each call of BWith, add the coin received to the list Coins W In each call of BDepo, add the coin received to the list Coins D BWith * is similar to BWith, except instead of using SigCm we use SigCm * :

Then return (M, σ) Else abort

We let identify the part of the secret key that is ignored in the entire game (because the bank never spent a coin). By correctness of the committed signature of S, the simulation will be perfect.

And by M ∪ S-extractability of C, we can deduce that B 1 is efficient. We now construct a first adversary B 3 against soundness:

In each call of BDepo, add the whole coin received in the list Coins D Let q W be the number of successful calls to BWith (sk, vk) ← S.KeyGen (Gr) par T ← T.Setup (Gr) par ← 1 λ , Gr, par S , par S , par T , ck (ek init , dk init ) ← E .KeyGen (Gr) (ek, dk) ← E.KeyGen (Gr) (sk tag , pk T ) ← T.KeyGen (Gr) sk D ← ( , pk T , sk tag ) pk B ← ek init , ek, vk, vk Execute A BRegist,BWith,BDepo (par, pk B ) Every time we would use the algorithm S .Sign in an oracle call, we use the oracle S .Sign * sk , • , and we add the input to UL Let (pk, Π) be the output of the last call to BDepo If a such pair is never returned by BDepo, then abort Let c 1 be the last coin sent by the user Parse c 1 as c 0 , c j i j=1 , n, sn, ρ sn , ρ pk Let j be minimal such that ( -→ sn) j-1 = ( -→ sn ) j-1 (using the same notation as in CheckDS)

We let identify the part of the secret key that could be ignored in the protocols (as the certificate cert of a receiver is never used). Let E sig be the event that B 2 breaks the unforgeability of S .

We construct a second adversary against soundness of C:

Let (pk, Π) be the output of the last call to BDepo If a such pair is never returned by BDepo, then abort Let c be the last coin sent by the user and i be its size Parse c as c 0 , c k i k=1 , n, sn, ρ sn , ρ pk Let j be minimal such that ( -→ sn) (j-1) = ( -→ sn ) (j-1) (with the same notation as in CheckDS)

Parse c (j-1) as c Let c be the coin that collides with c and i be its size Parse c as c 0 , c k i k=1

, n , sn , ρ sn , ρ pk Parse c (j-1) as c

cert , π , π

Parse π j sn as c j νsn , π j sn,eq Parse π j tag as c j νtag , π j tag,eq

νsn , c

sn,eq ∧ π

sn,eq ∧ π j sn,eq ∧ π j sn,eq ∧ π (j-1) sn,valid ∧ π j sn,valid ∧ π j sn,valid ∧ π j tag,eq ∧ π j tag,eq ∧ π j tag,valid ∧ π j tag,valid

Let E com,2 and E same-nonce be the events that B 4 breaks the soundness of C, and a same nonce is picked by the bank during two different calls to BDepo respectively.

A.1. SECURITY PROOFS FOR THE TRANSFERABLE E-CASH SCHEME 101 Suppose that we are in E unforg \ (E com,2 ∪ E counterfeit ∪ E same ). Because the coin has been accepted, the proofs are correct (as they are verified in the Spend protocol, during a call to BDepo). We are thus in a case where the extracted commitment will verify the equations. Let sn 0 , . . . , sn i , tag 1 , . . . , tag i , pk (j-1) tag , cert (j-1) , pk j tag , pk j tag , sn (j-1) , ν (j-1) sn , sn (j-1) , ν (j-1) sn , sn j , ν j sn , sn j , ν j sn , sn-pf (j-1) , sn-pf j , sn-pf j , tag j , ν j tag , tag j , ν j tag , t-pf j , t-pf j be the extraction of the commitments given by B 4 to the challenger of the soundness game. Because we are not in E com,2 , B 4 loses the game: for all k ∈ {1, . . . , i}:

and for all k ∈ {1, . . . , i}: E.Verify ek, tag k , ν k sn , ck tag = 1. Then by the correctness of E and E , we deduce that E Decrypt-fails will not happen. Because we are in E unforg \ E counterfeit , it means that during the execution of CheckDS, it has been detected that the first serial number of c was the same of another coin (here c ). Note that the last sn of a deposited coin is generated (with the key sk T ) and encrypted by the bank itself. Then because we are not in E same , CheckDS will find a j, such that -→ sn j = -→ sn j . By construction E.Dec dk, cj sn = E.Dec dk, c j sn , which by correctness of E (and because we are not in E com, 2 ) means sn (j-1) = sn (j-1) . Since: 1 = T.SVfy pk j T , sn j , sn-pf j = T.SVfy pk j T , sn j , sn-pf j = T.TVfy pk (j-1) T , sn (j-1) , sn j , tag j , t-pf j = T.TVfy pk (j-1) T , sn (j-1) , sn j , tag j , t-pf j = T.SVfy all pk (j-1) T , sn (j-1) , sn-pf (j-1) , and, because T is SN-identifiable, we can deduce that pk j tag = pk j tag . Moreover, since T is two-extractable, we deduce that if pk j tag ∈ UL, E DDSfails , E incorrect and E not-register will not happen.

We proved that E unforg \ E counterfeit ∪ E same ∪ E com, 2 =⇒ pk j tag ∈ UL. By noting that if pk j tag ∈ UL, and if E com, 2 ∪ E same ∪ E counterfeit does not happen, B 2 will win the unforgeability game against S . We finally deduce:

Now we suppose to be in E same , then by correctness of E, we deduce that the serial numbers were also identical before their encryption. Then by sn-injectivity, it means that the nonces picked during the deposits were the same, and we are therefore in E same-nonce . Thus E same ⊆ E same-nonce . From this inequality we deduce

By measuring the probability, we can finally conclude:

APPENDIX A.

Experiment Expt tag-exculpability B (λ): The game is perfectly simulated from A's point of view, except when it calls Spy(u * ), or makes that user double-spend, or if it detects that we are in hiding-mode (which happens with probability at most m-ind ). Let E ex and E tag be the events that A wins and that B 1 wins respectively. Suppose that we are in E ex . That means A forges a proof against one of the user registered (and does not spy on her). The probability that this user is u * is at least 1 u . And in this case, the following holds:

• A did not spy on u * or make her double-spend (in both cases we would not be in E ex ).

• VfyGuilt (pk T , Π * ) = 1, (because we are in E ex ) we thus have T.VfyGuilt(sk T , Π * ) = 1.

A.1. SECURITY PROOFS FOR THE TRANSFERABLE E-CASH SCHEME 103

We thus deduce that Pr (E ex ) ≤ u Pr (E tag ) .

Coin anonymity (full proof)

Theorem A.5. Let A be an adversary that wins the coin anonymity game (c-an) with advantage and let k be an upper-bound on the number of users transferring the challenge coins. Then there exist adversaries against mode-indistinguishability of C and tag-anonymity of T with advantages m-ind and t-an , resp., such that ≤ 2 m-ind + (k + 1) t-an .

Sketch of proof.

In the proof, we first define a hybrid game in which the commitment key is switched to hiding mode (hence the loss m-ind , which occurs twice for b = 0 and b = 1). All commitments are then perfectly hiding and the only information available to the adversary are the serial numbers and tags. (They are encrypted in the coin, but the adversary, impersonating the bank, can decrypt them.)

We then argue that, by tag anonymity of T, the adversary cannot link a user to a pair (sn, tag), even when it knows the users' secret keys. We define a sequence of k + 1 hybrid games (as k transfers involve k + 1 users); going through the user vector output by the adversary, we can switch, one-by-one all users from the first two the second vector. Each switching can be detected by the adversary with probability at most 2 t-an . There is a technical difficulty to manage the first swap: We still don't know the second tag secret key to withdraw the first coin. Fortunately in the hiding mode, we don't send any ciphertext to the bank, but only commitments and zero-knowledge proof.

Full proof. We recall Expt c-an

A,0 :

|, abort the entire procedure Then repeat the following step for j = 1, . . . , k:

In the game Expt c-an A,0,hiding , we will change the commitment key. If the adversary will detect it, it will break the mode-indistinguishability of C, then the distribution of the experiment will not change except with probability m-ind (property A.6).

Experiment Expt c-an

A,0,hiding (λ):

|, abort the entire procedure Then repeat the following step for j = 1, . . . , k:

We never use td in Expt c-an A,0,hiding (λ). Therefore, if we use a challenge (Gr, ck), in a Expt c-an A,0 (λ) game. If ck has been generated by C.Setup, it will be exactly Expt c-an A,0,hiding (λ), if ck has been generated by C.SmSetup, the experiment will be exactly Expt c-an A,0,hiding . This experiment can therefore be seen as a mode-distinguisher.

We Experiment Expt c-an A,0,ZK (λ):

sn ← E.Enc(ek, sn (1) , ν

(1)

long enough to compute the following and output it:

pk , c

(1) cert , π

(1) cert , c

(1)

sn , π

(1)

sn , c

(1)

n (1) , sn (1) , ρ

(1)

sn ) π(1) sn ← C.SmPrv enc (td, ek, ρ

(1)

sn , c(0) sn ) Pick uniformly at random --→ ρ (0) , --→ ρ (1) long enough to compute:

sn , π

(1) sn , c

(1)

We define ∀l ∈ {0, . . . , k -1} a new game:

Experiment Expt c-an A,0,ZKV2,l (λ):

|, abort the entire procedure Consider i 0 as ( -→ i (0) ) 0 , and i 1 as (

Then repeat the following step for j = 1, . . . , l:

Run S&R ZK,inv (2j, (

l , sk

l , sk

(1) l+1 ) Then repeat the following step for j = l + 2, . . . , k:

We receive a challenge of the tag-anon game of T (and not the tag exculpability game, contrarily to the proof of theorem A.4): par T , and we use this parameter as the double spending tag primitive parameter instead of generate it ourself in the Expt c-an A,0,ZKV2 experiment. In DoubleUWith, we send to the tag-anon-challenger, the secret keys of i 0 and i 1 . And we use O 1 to generate the serial number of i 0 in DoubleUWith and O 2 (0) to generate the corresponding tag in the first S&R ZK 1 . If the challenger was in mode 0, it will not change the whole experiment. But if the challenger is in mode 1, it will replace i 0 by i 1 . Let call Expt c-an A,0,ZKV2,-1 the game corresponding to this swap. We have just proved that

With the same strategy we replace i 1 by i 0 , i.e show that:

The proof is completely analog for the following property which authorize us to swap multiple games.

And finally we have to define a last oracle to swap the last keys (and the corresponding game):

T.SGen init (par T , sk T , n):

T.SGen (par T , sk T , n):

T.Detect (sn, sn , tag, tag , L):

• Parse sn as (M, N )

• Parse sn as (M , N )

• Parse tag as (A, B)

• Parse tag as (A , B )

e (A , ĝ) = e (M , pk T )

• Return (pk, (A , M ))

T.VfyGuilt (pk, π):

• Parse π as (A, N );

A.2. INSTANTIATION OF THE NEW BLOCKS

113

• Return e (A, ĝ) = e (N, pk) ∧ A = 0 G 1 T.SVfy init (par T , pk T , sn, M sn ):

• Parse sn as (M, N )

• Parse M sn as (M 1 , M1 ), (M 2 , M2 )

• Return e (M, ĝ) e(g -1

T.SVfy (par T , pk T , sn, sn-pf ):

TVfy (par T , pk, sn, sn , tag, t-pf ):

• Parse sn as (M, N )

• Parse tag as (A, B)

• Parse sn as (M , N )

• Return

Proofs

Theorem A.12. This scheme is extractable, bootable, SN-verifiable, tag-verifiable and N injective.

These properties are all straightforward to show and we therefore omit the proof.

Property A.13. The scheme is SN-collision-resistant.

Let (pk, P ) and pk , P such that it exists sn such that:

T.SVfy (par T , pk, sn, P ) = T.SVfy par, pk , sn, P = 1.

We parse sn as (M, N ). We can deduce the followings equations:

e (M, ĝ) = e (g 1 , P ) = e g 1 , P

We deduce that P = P . Then we can deduce e (M, ĝ) e g -1 2 , P e g -1 2 , pk = 0 G T = e (M, ĝ) e g -1 2 , P e g -1 2 , pk =⇒ e g -1 2 , pk = e g -1 2 , pk Then we can finally deduce pk = pk . The reasoning is analogous for T.SVfy init .

To prove the two other results, we will use the following lemma.

Lemma A.14. If there exists an adversary A against T uple with advantage , then there exists an adversary B against DDH in G with advantage DDH such that 3K ≤ DDH , with K the number of oracles calls to O b .

We define the following oracles:

We notice that the adversary cannot distinguish O 0 and O 0.3 , O 0.3 and O 0.7 , O 0.7 and O 1 , with probability more than DDH , respectively, by viewing the triple

h n 2 as DDH triple. (We can compute the others elements by knowing the discrete logarithms of the elements which are not in the DDH-triple, and computing all the other oracle calls honestly). This proves the lemma. ((G, g 1 , q), ( Ĝ, ĝ, q), e): par T ← ((G, g 1 , q), ( Ĝ, ĝ, q), e) (sk 0 , sk 1 ) ← A (par

We can use the previous theorem to understand that the adversary could not distinguish Perfect-tag-anonymity from tag-anonymity (except with probability 3K DDH ) In the latter game, we could replace b by 1 -b without changing the distribution of the input adversary.

Theorem A.16. Let A be an adversary that wins the exculpability game with probability and K oracle call to O 1 , then there exist B 1 , B 2 adversary against DDH respectively in G with advantage DDH and in Ĝ with advantage ˆ DDH , such that:

Using the same argument as in the previous corollary, we deduce by incurring a loss of 3K DDH , we can consider that oracle calls do not yield any information to the adversary. Then after we receive a triple (ĝ 1 , ĝ2 , ĝ3 ) in Ĝ, we send ĝ1 as the public key. Then we receive (N, A) such that e (N, pk) = e (A, ĝ) with A = 0 G 1 . This means that A = N log g 1 (pk) and we can check if e (N, ĝ3 ) = e (A, ĝ2 ) to guess if it is a DDH triple or not.

Efficiency results

We summarize all the efficiency results as follows (where "m.s.w.u" means multiscalar with unkown):

of the message vector -→ m = (m 1 , . . . , m n ) ∈ G n . As in [START_REF] Libert | Structure-preserving chosen-ciphertext security with shorter verifiable ciphertexts[END_REF], we use the same one-time linearly homomorphic structure-preserving signature scheme [LPJY13] LHSPS = (KeyGen, Sign.Verify), for which let

the signing key of the LHSPS is composed of two linearly homomorphic signatures of -

. Using this signing key, anyone generate the signature σ-→ m of any message

The second part of the ciphertext is a zero-knowledge proof for the language

where

that log f (c 0 ) = log g (c 1 ), then the ciphertext is a valid ciphertext. Also note that signatures on -→ v with b = 1 will only be generated in the security proof.

To enable re-randomization, we generate a signature σ-→ w on the vector -→ w = (f b , g b , 1,

) and add a zero-knowledge proof of knowledge of the valid signature σ-→ w . It is easy to see that with σ-→ w , we can generate signatures for all re-randomization of the vector -→ v .

One-time linearly homomorphic structure-preserving signature

To construct the re-randomizable CCA encryption scheme, we need the one-time linearly homomorphic structure-preserving signature.

Definition A.17 ((One-time) linearly homomorphic structure-preserving signature [START_REF] Libert | Linearly homomorphic structure-preserving signatures and their applications[END_REF]). A one-time linearly homomorphic structure-preserving signature is tuple of 4 algorithms LHSPS = (Setup, Sign, SignDerive, Verify) with the following specifications:

We recall the following construction of the one-time linearly homomorphic structure-preserving signature scheme.

• LHSPS.Setup (Gr, n):

1. Parse Gr as (G, Ĝ, G T , e).

Chose ĝz , ĝr

$ ← -Ĝ. For i ∈ {1, . . . , n}, randomly chose χ i , γ i and compute ĝi = ĝχ i z ĝγ i r . 3. Output the verification key pk = (ĝ z , ĝr , {ĝ i } n ) ∈ Ĝn+2 and the signing key sk = ({χ i , γ i } n i=1 ).

• LHSPS.Sign vk, sk, -→ M :

1. Parse the verification key vk = (ĝ z , ĝr , {ĝ i } n ) ∈ Ĝn+2 , the signing key sk = ({χ i , γ i } n i=1 ) and the message

Choose random exponents {α

Define two vectors

then generate two LHSPS signatures σ-→ v 1 and σ-→ v 2 which will be used to proof that a vector is in the Span( -→ v 1 , -→ v 2 ). together with the signing key -→ tk.

6. Output the decryption key dk = α and the public key

Notice that the LHSPS signing key -→ tk will never be published by the key generation algorithm, it will only be used in the security proofs.

E.Enc (pk, m, ν):

6. Compute a Groth-Sahai proof π-→ v of the validity of the LHSPS signature σ-→ v .

7. To enable the re-randomization, compute

and Groth-Sahai proof π F GH of them.

Define the vector

Game 0 : We have Game 0 is identical to the original RCCA security game and thus by definition:

Game 1 : In this game, we will modify the challenge ciphertext provided to the adversary in the RCCA security game. The new challenge ciphertext is:

We only modify π -→ v and π -→ w . In stead of generating these two proofs using the signing key

Notice that this is the perfect sound setting of the Groth-Sahai proof system. ξ and ζ can be use to extract the witness. Since the only difference between Game 1 and Game 2 is the change of

, the indistinguishability can be proven using the SXDH assumption. Thus,

Game 3 : In this game, we modify the decryption oracle. We will add a manual verification of the underlying LHSPS for the decryption queries. To do this, since the Groth-Sahai proof is settled in the soundness mode ( -→ u 1 = -→ u ξ and -

). We can use the trapdoors ξ, ζ to extract the witness in the commitments of the Groth-Sahai proof. We extract -→ v and σ-→ v = (z, r) from the proof π-→ v . We use the signing key td of the linearly homomorphic structure-preserving signature σ † -→ v = (z † , r † ) to generate a signature σ † -→ v of the vector -→ v . The challenger will reject the decryption query if σ † -→ v = σ-→ v . We can see that, if an adversary can distinguish Game 3 from Game 2 then he can forge a valid signature of the underlying LHSPS. Since the unforgeability of the LHSPS is based on the SXDH problem, we have Adv 3 ≤ Adv 2 + Adv DP (1 λ ).

Game 4 : We will modify all the decryption oracles (both pre-challenge and post-challenge ones) to avoid the use of log g (h i ) = α i . After making these changes, we can modify the generation of

Pre-challenge decryption queries: We use the trapdoor of the Groth-Sahai proof to extract the witness of the proof, if we have b = 0 then we directly reject the proof.

Post-challenge decryption queries:

We also use the trapdoor of the Groth-Sahai proof to extract the witness of the proof, if b = 0 and the ciphertext is not rejected by the rule of Game 3 , the challenger outputs Replay. Additionally, both in pre-challenge and post-challenge decryption queries. Since we don't have α i anymore, we decrypt the ciphertext by computing

. We now analyse the change of the decryption oracles:

Pre-challenge: It is easy to see that in case of b = 0, the challenger only issued two LHSPS signatures of -→ v 1 and -→ v 2 . And the vector -→ v is clearly not in the span of Span( -

So the adversary is statistically impossible to forge a correct signature.

A.2. INSTANTIATION OF THE NEW BLOCKS 121

Post-challenge: Note that the Groth-Sahai proof is in the perfect soundness setting of the Groth-Sahai proof, thus the challenger C can use the trapdoor to extract all the witness used in the proof. We will now separate two case:

with a overwhelming probability, we will have -→ v ∈ Span( -→ v 1 ). Thus we have

thus we can answer

Replay to the adversary.

Game 5 : We modify the distribution of the challenge ciphertext. Instead of choosing them as an encryption of -→ M 0 or -→ M 1 . We Choose them all random elements. By the self-rerandomizability of the DDH assumption in G, the game 5 is indistinguishable from the game 4.

During the Game 5 , as the challenge ciphertext is only random group elements, the adversary cannot have more advantage than a random guess.

Instantiation of the encryption scheme E

Let Gr = (p, G, G). E.KeyGen():

• Return ((G dk 1 , G dk 2 ), (dk 1 , dk 2 ))

E.Enc((D 1 , D 2 ), (M 1 , M 2 ), ν):

E.ReRand((D 1 , D 2 ), (C 0 , C 1 , C 2 ), ν):

E.Dec((dk 1 , dk 2 ), (C 0 , C 1 , C 2 )):

E.AdptPrf(ck, ek, (com M 1 , com M 2 ), c, π = (π, com ν ), ν ):

• Analog to A.2

Property A.20. If there exists an adversary A that breaks the IACR property of the scheme with advantage IACR , then there exists an adversary B that breaks SXDH with advantage SXDH , with IACR ≤ 4 SXDH .

We define the following experiments: ABSTRACT Transferable e-cash is the most faithful digital analog of physical cash, as it allows users to transfer coins between them without interacting with the bank. Strong anonymity requirements and the need for mechanisms to trace illegal behavior (double-spending of coins) have made instantiating the concept notoriously hard. Baldimtsi et al. (PKC'15) have given a first instantiation, which however relied on a powerful cryptographic primitive that made the scheme non-practical. In this thesis we revisit the model for transferable e-cash, proposing simpler yet stronger security definitions and then give the first concrete instantiation of the primitive, basing it on bilinear groups, and analyze its concrete efficiency. Because to build our scheme, we are using non-standard assumption in a bilinear group context, we analyze the hardness of a broad class of assumptions in a relevant context: the algebraic group model.

A.3 Efficiency analysis of the transferable e-cash scheme

KEYWORDS

e-cash, strong anonymity, randomizable NIZK proofs, algebraic group model, uber assumption, signatures on equivalence classes, generic group model.