Project funded by WWTF, the Vienna Science and Technology Fund

Duration: 2020-01-01 – 2029-12-31

Funding: € 1,599,280

Current Members

• DI Dr Georg Fuchsbauer (PI), Associate Professor, TU Wien
• DI Fabian Regen (pre-doc)
• DI Marek Sefranek (pre-doc)

Alumni

• Dr Hamza Abusalah (post-doc)
• DI Mathias Wolf (pre-doc)

Project Description

We are observing a trend towards decentralization to avoid single points of failure and trust in a single actor. Its epitome is the blockchain, a publicly verifiable distributed ledger, introduced by Bitcoin, whose applications are now spreading far beyond currencies. Blockchains enabled smart contracts, which promise community-based applications that forgo reliance on centralized, typically commercial, actors.

Central to all such systems is their transparency; anyone can view and check consistency of Bitcoin transactions. While public verifiability is a prerequisite for consensus, this openness conflicts with an increasing awareness of the importance of privacy (as e.g. manifested by the EU’s GDPR) in a world where more and more user data is amassed and leaked in frequent security breaches. At the same time, the civic freedom of making payments anonymously is disappearing together with cash, forcing citizens to submit to surveillance by payment providers and secret services.

While cryptocurrencies may seem like an alternative, they often offer only very little privacy: transactions can be traced, systems lack rigorous guarantees, make strong assumptions or they are not practically efficient. Traceability of coins moreover violates fungibility, a fundamental principle of currency that demands that all coins be equal.

The overarching ambition of the COnFIDE project is to reconcile public verifiability with privacy in distributed ledgers.

The most promising approach to privacy are zero-knowledge proofs, as used for example by the cryptocurrency Zcash. Their shortcomings are a potential reliance on trusted parameters, security analyses relying on ad-hoc hardness assumptions or models making strong idealizations. We see reducing the trust assumptions that are necessary to achieve privacy as the main challenge for distributed ledgers.

Other issues with blockchains today concern their efficiency. Proof of work is still for consensus, leading to Bitcoin’s colossal electricity consumption. Alternatives either still rely on physical resources or are incompatible with privacy guarantees, and few systems are both sustainable and privacy-protecting. Another shortcoming is scalability; while Visa’s payment system handles 2000 transactions per second, Bitcoin handles 7. Moreover, all transactions remain in the blockchain forever, now over 600 GB for Bitcoin. While the current state of Bitcoin can be concisely represented by the set of unspent transactions (UTXOs), this is not possible in anonymous currencies, exacerbating bad scalability.

To overcome these issues, we are developing new cryptographic methods that reduce or eliminate the trust assumptions currently required for privacy. These we will underly distributed ledgers with stronger privacy guarantees based on weaker assumptions. For the embedding of cryptocurrencies into the legal framework, we moreover require the integration of means for prosecution of abuse, while at the same time preventing indiscriminate surveillance.

We will also work towards reconciling sustainability with privacy in distributed ledgers, improving the privacy guarantees of systems based on proof of space and proof of stake, the most ecologically friendly consensus mechanism. Towards ensuring scalability, we are developing blockchain protocols that allow discarding obsolete information, so they only store the current state; and other means of increasing throughput, all while protecting privacy. The results of COnFIDE will be essential to the viability of next-generation distributed systems and will ensure the safety of citizens and protection of the environment in a time of vast technological change.

Publications

• G. Fuchsbauer, A. Plouviez, Y. Seurin. Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model.   EUROCRYPT ‘20   [eprint]

  Blind signatures allow users to obtain a signature on a document without revealing it to the signer. They are at the heart of “traditional” e-cash and have plenty of privacy-enhancing applications in distributed ledgers. Schnorr signatures will be the new standard improving on (EC)DSA and are supported e.g. by Bitcoin. We revisit a protocol for blind issuing of Schnorr signatures, strengthen it and give formal security guarantees. This will enable privacy-preserving blockchain applications that rest on solid foundations.

• B. Bauer, G. Fuchsbauer, J. Loss. A Classification of Computational Assumptions in the Algebraic Group Model.   CRYPTO ‘20   [eprint]

  Two years earlier, we proposed an abstract model for analyzing cryptographic schemes, now a standard tool for proving the security of zero-knowledge proof systems. (The Algebraic Group Model and Its Applications, with Eike Kiltz and Julian Loss, CRYPTO ‘18 [eprint]). In this work, we classify in this model types of hardness assumptions, which are the foundation of cryptographic schemes that are corroborated by security proofs.

• B. Bauer, G. Fuchsbauer. Efficient Signatures on Randomizable Ciphertexts.   SCN ‘20   [eprint]

  We propose the currently most efficient realization of a signatures on randomizable ciphertexts, a cryptographic concept introduced by the PI that underlies schemes for anonymous authentication.

• D. Catalano, G. Fuchsbauer, A. Soleimanian. Double-Authentication-Preventing Signatures in the Standard Model.   SCN ‘20   [eprint]

  Double-authentication-preventing signatures were designed to deter issuance of rogue certificates (which certification authorities have been ordered to do by intelligence agencies, resulting in the latter being able to read all encrypted traffic). This type of signatures has also been used to prevent forgery in distributed ledgers. We propose a realization featuring a combination of properties hitherto not achieved.

• B. Bauer, G. Fuchsbauer, C. Qian. Transferable E-cash: A Cleaner Model and the First Practical Instantiation.   PKC ‘21   [eprint]

  We give the first practical realization of fully anonymous transferable e-cash. In such a system, like for “fiat” currencies, electronic coins are issued by a central bank. Whereas in “classical” e-cash, an e-cash obtained must be immediately deposited at the bank, transferable e-cash allows further payments – as with physical cash.

• B. Bauer, G. Fuchsbauer, A. Plouviez. The One-More Discrete Logarithm Assumption in the Generic Group Model.   ASIACRYPT ‘21   [eprint]

  The one-more discrete logarithm assumption (OMDL) underlies the security analysis of many practically relevant advanced signature schemes, used e.g. in Bitcoin. After showing that a purported proof in the literature is flawed, we give the first formal analysis of OMDL (as well as the related computational Diffie-Hellman problem), showing it is hard in the generic group model. This shows that there are no “group-independent” attacks possible against OMDL.

• H. Abusalah, G. Fuchsbauer, P. Gaži, K. Klein.  SNACKs: Leveraging Proofs of Sequential Work for Blockchain Light Clients.   ASIACRYPT ‘22   [eprint]

  We present a new method for constructing light clients by using proofs of sequential work. As blockchain data is constantly growing, users are not storing the full history but rely on the mediation of full nodes when interacting with the blockchain. Light clients allow them to do so without having to trust the full node.

• G. Fuchsbauer, M. Orrù.  Non-interactive Mimblewimble Transactions, Revisited.  ASIACRYPT ‘22   [eprint]

  Mimblewimble is a payment protocol that, besides offering privacy by design, improves on scalability: while in blockchains every transaction must be stored forever, in Mimblewimble only the “unspent transaction outputs”, which represent the current state of the system, must be kept. We propose and rigorously analyze a variant that lets users transfer funds without interacting with the receiver (as is standard in other cryptocurrencies), building on our earlier work from EUROCRYPT'19 [eprint]. Our protocol is now implemented by Litecoin.

• M. Chase, G. Fuchsbauer, E. Ghosh, A. Plouviez.  Credential Transparency System.   SCN ‘22

  Digital credentials are a major component of today’s digital identity ecosystem. For usability, managing them is often outsourced to a service provider, such as for Single Sign-On (SSO) systems and identity hubs, which however requires immense trust in the provider. We introduce credential transparency systems, which add strong transparency guarantees to a credential management system while preserving privacy and usability features of the system.

• D. Catalano, G. Fuchsbauer, A. Soleimanian.  Double-Authentication-Preventing Signatures in the Standard Model.  J. Comput. Secur. 30(1), 2022   [eprint]

  (journal version of article above)

• H. Abusalah, V. Cini.  An Incremental PoSW for General Weight Distributions.  EUROCRYPT ‘23   [eprint]

  This work continues our research on light clients (ASIACRYPT 2022), which allow users that do not store the full blockchain to obtain information from full nodes without having to trust them. We construct incremental proofs of sequential work and use it for light mining, where a new miner can securely mine, i.e., extend an existing blockchain, without storing the entire blockchain.

• H. Abusalah. SNACKs for Proof-of-Space Blockchains.   FC ‘23   [eprint]

  We extend our light client constructions (ASIACRYPT 2022) to systems whose underlying consensus system is proof of space. Bitcoin uses proof of work, which causes colossal energy consumption; in proof-of-space-based blockchains, which we introduced at FC 2018 [eprint] (meanwhile deployed in the cryptocurrency Chia), the provers instead show that they allocate a certain amount of disk space to mining. In contrast to expending energy, idle disk space can be used at basically no cost.

• G. Fuchsbauer, M. Wolf.  Concurrently Secure Blind Schnorr Signatures.  EUROCRYPT ‘24   [eprint]

  Schnorr signatures are being standardized by NIST and are also supported by Bitcoin. Blind signatures allow a user to obtain a signature on a message that is hidden from the signer; when the resulting signature is a Schnorr signature, this allows blind issuing of Bitcoin transactions, leading to new privacy-preserving protocols. We propose a new blind-signing protocol for Schnorr signatures, prove it concurrently secure and implement and benchmark it for different choices of the underlying building blocks.

• J. Alwen, G. Fuchsbauer, M. Mularczyk.  Updatable Public-Key Encryption, Revisited.  EUROCRYPT ‘24   [eprint]

  Forward security (FS) guarantees that even if the secret key is revealed at some point, messages that were encrypted before remain secure. FS is a central goal of secure group messaging protocols, as used by Signal and WhatsApp. Updatable public-key encryption (UPKE) is used to obtain FS efficiently. We argue that the established security model for UPKE is insufficient for the intended applications, propose a stronger model, and construct a scheme satisfying it, which requires less than 2% of the bandwidth of the hitherto most efficient scheme.

• B. Bauer, G. Fuchsbauer, F. Regen.  On Proving Equivalence Class Signatures Secure from Non-interactive Assumptions.  PKC ‘24   [eprint]

  Equivalence-class signatures (EQS) where introduced by the PI (J. Cryptology, 2019 [eprint]) as an alternative to proving knowledge of signatures for anonymous authentication, and they led to efficient anonymous credentials. The main open question was whether EQS could be constructed in the “standard model”, i.e., without making idealizing assumptions. We give a negative answer, showing that a security proof from a non-interactive hardness assumption is impossible.

• B. Bauer, G. Fuchsbauer, F. Regen.  On Security Proofs of Existing Equivalence Class Signature Schemes.  ASIACRYPT ‘24   [eprint]

  We show that the main (and most efficient) construction of equivalence class signatures (J. Cryptology, 2019) can be shown secure in the “algebraic group model”, a weaker idealization than the one used in the original proof. (Given the negative result from the aforementioned work, this is arguably ideal.) We also show that an EQS construction from ASIACRYPT ‘19 had a flawed security proof.

• M. Sefranek. How (Not) to Simulate PLONK.  SCN ‘24   [eprint]

  PLONK [eprint] is one of the central zk-SNARK systems, with constant-size (0.5 KB) proofs of and sublinear verification time. Although deployed in several applications, it was only argued informally that it achieves zero knowledge. We reported and fixed a vulnerability in its original specification, which led to an update of PLONK, which we formally prove statistically zero-knowledge.

• G. Cho, G. Fuchsbauer, A. O’Neill, M. Sefranek.  Schnorr Signatures are Tightly Secure in the ROM under a Non-interactive Assumption.  CRYPTO ‘25   [eprint]

  We show that the widely used Schnorr signature scheme meets the standard security notion in the random oracle model (ROM) under the circular discrete-logarithm (CDL) assumption, which we introduce and formally analyze. Our reduction is completely tight, justifying for the first time parameter regimes used in deployed versions, without making additional idealizing assumptions. We also show that Sparkle+ (CRYPTO ‘23 [eprint], a threshold signing scheme for Schnorr, is tightly secure under CDL.

Preprints

• L. Eagen, A. Gabizon, M. Sefranek, P. Towa, Z.J. Williamson.  Stackproofs: Private Proofs of Stack and Contract Execution Using Protogalaxy.  [eprint]

  We describe and analyze a simplified variant of the zk-SNARK construction used in the Aztec protocol, a private smart contract system. For this we define the notion of repeated computation with global state, which is related to incrementally verifiable computation.

• J. Alwen, G. Fuchsbauer, M. Mularczyk, D. Riepel.  Lattice-Based Updatable Public-Key Encryption for Group Messaging.  [eprint]

  We give an updatable public-key encryption scheme satisfying our model (EUROCRYPT ‘24 [eprint]) that guarantees security in group messaging applications. Our scheme is proved from lattice assumptions and conjectured to be post-quantum secure.

• Z. Avarikioti, G. Fuchsbauer, P. Keer, M. Maffei, F. Regen.  A Composable Game-Theoretic Framework for Blockchains.  [arXive]

  Blockchains rely on economic incentives, which can be analyzed using game theory. However, isolated analysis often fails to capture incentive dynamics when applications interact with other components. We propose a compositional game-theoretic framework and illustrate it in case studies on HTLCs, Layer-2 protocols, and MEV. We show how compositional analysis reveals subtle incentive vulnerabilities and supports modular security proofs.

• G. Fuchsbauer, P. Garimidi, G.V. Policharla, M. Resnick, E.N. Tas.  Non-Delegatable Commitments.  [eprint]

  Cryptographic commitments allow a party to “commit” to a value without revealing it, and later “open” it, without being able to modify if. When commitments serve as cryptographic attestations of work (e.g. relaying blocks or storing data), the fact that the generation of commitments can be outsourced undermines the intended economic properties of the protocol. We introduce non-delegatable commitments, where outsourcing the commitment process is disincentivized, because it leaks the user’s secret key.

• J. Katz, M. Sefranek.  Issuer Hiding for BBS-Based Anonymous Credentials.  [eprint]

  Anonymous credentials allow users to prove possession of certain attributes without leaking anything else. They have recently received interest from companies including Google, Apple, and Cloudflare, and are being actively evaluated both at the IETF and in the EU. Anonymous credentials based on BBS signatures are a leading candidate for standardization. We show how in BBS-based credentials the identity of the issuer can be hidden, beyond revealing that it is in some pre-determined set.