Project topics and materials
Get Complete Project Material File(s) Now! »
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 [Nec94] introduced the generic group model (GGM) [Sho97, Mau05], 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 [LRSW99, CL04]).
Following the approach first used in [ABM15], a more recent work by Fuchsbauer, Kiltz, and Loss [FKL18] introduces the algebraic group model, in which all algorithms are assumed to be algebraic [PV05]. 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 [FKL18, MBKM19, Lip19, GWC19]. It has also recently been used to analyze blind (Schnorr) signatures [FPS20], which are notoriously difficult to prove secure in the standard or random oracle model. Another recent work by Agrikola, Hofheinz and Kastner [AHK20] 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 [FKL18, Los19]. We also show that there exists a natural hierarchy among Uber assumptions 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 authenti-cation, 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. [Bra00, BL13]).
The zero-knowledge proofs for these schemes are either instantiated using Σ-protocols [CL03, CL04] (and are thus interactive or in the random oracle model) or in the standard model [BCKL08] using Groth-Sahai proofs [GS08]. 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 [HS14] extended this concept to structure-preserving signatures on equivalence classes (later improved in [FHS19]) for messages from G2, by adding a functionality called signature adaptation: given a signature on a message m ∈ G2 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 [FHS19]: 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 m0 := r • m for a random r and the signature adapted to m0 is indistinguishable from a random element m00 from G2 together with a fresh signature on m00.
Besides the first attribute-based anonymous credential scheme for which the complexity of showing is independent of the number of attributes [FHS19], 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 [FHS15, FHKS16], revocable anonymous credentials [DHS15], as well as efficient constructions [FGKO17, DS18] of both access-control encryption [DHO16] and dynamic group signatures [BSZ05].
The most efficient construction of ECS is the one from [FHS19], which was proven secure in the generic group model [Sho97]. 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. [AGHO11]. Moreover, there is strong evidence that structure-preserving signatures of this size cannot be proved secure by a reduction to non-interactive assumptions [AGO11], 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 [FG18] and in the common-reference string model [KSD19] (with signatures 6 times longer than [FHS19]).
Signatures with flexible public key [BHKS18] and mercurials signatures [CL19] are extensions of ECS that allow signatures to be adapted not only to multiples of the signed message, but also to multiples of the verification key. This has been used to build delegatable anonymous credentials [BCC+09] in [CL19]. Delegatable credentials allow for hierarchical structures, in which users can delegate obtained credentials to users at lower levels.
Shortcomings of ECS. While schemes based on ECS offer (near-)optimal efficiency, a drawback is their weak form of anonymity. Consider a user who asks for a signature on m = (m0G, m1G) (where G is the generator of the group (G, +)). If the user later sees a randomization (M00, M10) of this message, she can easily identify it as hers by checking whether m1M00 = m0M10. The notion of anonymity (which is called class-hiding in ECS) that can be achieved for these equivalence classes is thus akin to what has been called selfless anonymity [CG05] in the context of group signatures: in contrast to full anonymity [BMW03], signatures are only anonymous to those that do not know the secret values used to construct them (the signing key for group signatures; the values m0 and m1 in our example above).
This weakness can have concrete repercussions on the anonymity guarantees provided by schemes built from ECS, for example delegatable credentials. In previous instantiations [BCC+09, Fuc11] of the latter, the showing of a credential is anonymous to anyone, in particular to a user that has delegated said credential to the one showing it. However, in the construction from the ECS variant mercurial signatures [CL19], if Alice delegates a credential to Bob, she can identify Bob whenever he uses the credential to authenticate, which represents a serious infringement to Bob’s privacy. In fact, anonymity towards the authority issuing (or delegating) credentials has been considered a fundamental property of anonymous credential schemes.
In [CL19], when Alice delegates a credential to Bob, she uses her secret key (x0, x1 ) ∈ (Z|∗G|)2 to sign Bob’s pseudonym under her own pseudonym (P0, P1) = (rx0G, rx1G) for a random r, which becomes part of Bobs credential. When Bob shows it, he randomizes Alice’s pseudonym to (P00, P10) := (r0P0, r0P1) for a random r0, which Alice can recognize by checking whether x1P00 = x0P10.
Signatures on randomizable ciphertexts. To overcome this weakness in anonymity in ECS, we use a different type of equivalence class. Consider an ElGamal [ElG85] encryption (C0, C1) = (rG, M + rP ) of a message M under an encryption key P . Such ciphertexts can be randomized by anyone, that is, without knowing the underlying message, a fresh encryption of the same message can be computed by choosing r0 and setting (C00, C10) := (C0 +r0G, C1 + r0P ) = ((r +r0)G, M +(r+r0)P ). All possible encryptions of a message form an equivalence class, which, in contrast to multiples of pairs of group elements, satisfy a “full” anonymity notion: after randomization, the resulting ciphertext looks random even to the one that created the original ciphertext (see Proposition 4.7).
If such equivalence classes yield better anonymity guarantees, the question is whether we can have adaptable signatures on them, that is, signatures on ciphertexts that can be adapted to randomizations of the signed ciphertext. It turns out that this concept exists and even predates that of ECS and is called signatures on randomizable ciphertexts (SoRC) [BFPV11]. Since their introduction, SoRC have been extensively used in e-voting [CCFG16, CFL19, CGG19, HPP20] and other primitives, such as blind signatures and extensions thereof [BFPV13]. Blazy et al. [BFPV11] prove their instantiation of SoRC unforgeable under standard assumptions in bilinear groups. Its biggest drawback is that it only allows for efficiently signing messages that consist of a few bits.
Transferable e-cash
E-cash. Starting with Chaum’s seminal work [Cha83], since the 1980s cryptographers have sought to devise an electronic analogue to physical cash, which guarantees secure and private payments [Cha83, CFN90, Bra94, CHL05, CLM07, BCKL09]. Cryptographic e-cash defines three types of participants: a bank, users and merchants. Users withdraw electronic coins from the bank and 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 [Cha83], 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 [CFN90] 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, c0 with the same serial number but with different double-spending tags t, t0 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 [CHL05] 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 [vSN92] 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 [vAE90, OO90, FY93] 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 of transfers [CG08], or schemes using involved techniques, such as [BCFK15], that make them far from being implementable on constrained mobile devices.
Anonymity. The first transferable e-cash schemes by Okamoto and Ohta [OO90, OO92] satisfy various properties such as divisibility and transferability but only provide very weak levels of anonymity. While withdrawals and spendings cannot be linked, it can be easily decided whether two payments were made by the same user, a notion later termed weak anonymity (WA). Chaum and Pedersen [CP93] extended a scheme by van Antwerpen [vAE90] by adding transferability of coins. Their scheme satisfies strong anonymity (SA), which, in addition to unlinkability of withdrawals and payments, guarantees that no one can tell whether two payments were made by the same user. However, a user in their scheme can recognise coins he observed in previous transactions. Strong anonymity is also satisfied by later schemes proposed in [Bla08, CGT08].
Chaum and Pedersen [CP93] also showed that transferred coins must necessarily grow in size and that an adversary with unbounded resources can always recognise a coin he owned when seeing it spent later. A formal treatment of anonymity notions for transferable e-cash was undertaken by Canard and Gouget [CG08], who introduce two strengthenings of weak and strong anonymity. Full anonymity (FA) requires that no adversary, even when colluding with the bank, can link a coin he previously observed to a coin he receives via a transfer or a spending (“observe-then-receive anonymity”). Perfect anonymity (PA) states that an adversary colluding with the bank cannot link a coin previously owned to a coin he receives. Note that these notions are not satisfied by decentralised cryptocurrencies like Bitcoin, where a coin can be traced throughout transfers.
This led to the following hierarchy of anonymity notions: WA ⇐ SA ⇐ FA ⇐ PA. While it was known [CP93] that perfect anonymity cannot hold against unbounded adversaries, Canard and Gouget [CG08] showed that it cannot be achieved against bounded adversaries either. This led them to introduce two orthogonal relaxations of perfect anonymity, both incomparable to FA. PA1 (a.k.a. spend-then-observe): no adversary, controlling the bank, can link a previously owned coin to a coin he passively observes being transferred between two honest users; and PA2 (a.k.a. spend-then-receive): when the bank is honest then no adversary can link a coin previously owned to a coin he receives. (If the adversary colludes with the bank, this notion is not achievable, as it contradicts detection of double-spendings.) The authors then construct a transferable e-cash scheme that satisfies all achievable anonymity properties, but which is completely impractical as it relies on meta-proofs and thus Cook–Levin reductions.
Implementable schemes. The first practical scheme that satisfies (conditional versions of) FA, PA1 and PA2 was given by Fuchsbauer, Pointcheval and Vergnaud [FPV09] and was based on the efficient non-interactive zero-knowledge proofs due to Groth and Sahai [GS08] for which they introduced a compatible certification mechanism. The scheme has however two severe shortcomings: the users have to store the data of all transactions they were involved in, so they can prove innocence in case of fraud; and more seriously, when a double-spending is detected, all users up to the double- spender are revealed. Anonymity of a user therefore only holds as long as every other user in the system behaves honestly.
Based on the primitive of commuting signatures by Fuchsbauer [Fuc11], Blazy, Canard, Fuchs-bauer, Gouget, Sibert and Traoré [BCF+ 11] proposed a scheme that overcomes the above drawbacks by assuming the existence of a trusted entity called the judge. This authority must be invoked every time a double-spending is detected, as it holds a key that can lift the anonymity of users. It can however also use it to trace all coins and users in the system at any time, which conflicts with one of the main goals of e-cash: that users remain anonymous as long as they do not double-spend.
The first transferable e-cash scheme that satisfies all anonymity properties suggested in the literature (FA, PA1, PA2) was given last year by Baldimtsi, Chase, Fuchsbauer and Kohlweiss [BCFK15]. It does not assume any trusted parties nor does it rely on Cook–Levin reductions or heuristics like the random-oracle model [BR93] 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 [CG08], 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 [BFKW09] and commuting signatures [Fuc11], Chase et al. [CKLM14] proposed malleable signatures, where anyone can transform a signature on a message m into a signature on m0, as long as T (m) = m0 for some allowed transformation T . They show that malleable signatures yield delegatable credentials, and the transferable e-cash scheme in [BCFK15] 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. [ZLG12] proposed a transferable variant of conditional e-cash [SCS07], 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 [Sar13] constructed a protocol, which was later shown to be neither anonymous nor to prevent double-spending by Barguil and Barreto [BB15]. Tiwari and Gupta [TG14] 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 [TH16] 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 [BCFK15]. 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.
Instead, we give a direct instantiation based on Groth-Sahai proofs [GS08], which are ran-domizable, structure-preserving signatures [AFG+10], which are compatible with GS proofs, and rerandomizable encryption satisfying RCCA-security [CKN03] (a the corresponding variant of CCA security). While we use signature schemes from the literature [AGHO11, Fuc11], we construct a new RCCA-secure encryption scheme based on [LPQ17] that is tailored to our scheme. Finally, we reuse the (efficient) tags introduced in [BCFK15] 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 [BCFK15]: 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 [Boy08] 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 gz , is also given gz2 , . . . , gzq and must compute . We prove that if the maximum total degree of the challenge polynomials in (→− →− →−)
z 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 (→− →− →−)) is infeasible to compute. We prove this by generalizing a technique R,S,T first used by Fuchsbauer et al. [FKL18] to prove soundness of Groth’s SNARK [Gro16] under the q-DLog assumption in the AGM.
Table of contents :
1 Introduction
1.1 Context
1.2 State of the art
1.3 Our results
2 Preliminaries
2.1 Notations
2.2 Security Model
2.3 Computational assumptions
2.4 Primitives used
2.5 Proof of Lemma 2.9
3 Classification of computational assumptions in the algebraic group model
3.1 The Uber-Assumption Family
3.2 The Flexible Uber Assumption
3.3 The Ruber Assumption
3.4 The Ruber Assumption for Flexible Targets
3.5 Uber Assumptions with Decisional Oracles
3.6 The Flexible Gegenuber Assumption
3.7 Separation of (q + 1)-DL from q-DL
3.8 Separation of 2-One-More DL from q-DL
3.9 Running Time of the Generic Reduction of Theorem 3.5
3.10 Proof of Theorem 3.9
3.11 Proof of Theorem 3.14
4 Signatures on randomizable ciphertexts
4.1 Definitions
4.2 Instantiation
4.3 Security of our scheme
5 Transferable E-cash: A Cleaner Model and the First Practical Instantiation
5.1 Security Models
5.2 Comparison with previous work
5.3 Instantiation
5.4 Instantiation of the building blocks and efficiency
Bibliography
A
A.1 Security proofs for the transferable e-cash scheme
A.2 Instantiation of the new blocks
A.3 Efficiency analysis of the transferable e-cash scheme
