An extractable one-way function (EOWF), introduced by Canetti and Dakdouk (ICALP 2008) and generalized by Bitansky et al. (SIAM Journal on Computing vol. 45), is an OWF that allows for efficient extraction of a preimage for the function. We study (generalized) EOWFs that have a public image verification algorithm. We call such OWFs verifiably-extractable and show that several previously known constructions satisfy this notion. We study how such OWFs relate to subversion zero-knowledge (Sub-ZK) NIZKs by using them to generically construct a Sub-ZK NIZK from a NIZK satisfying certain additional properties, and conversely show how to obtain them from any Sub-ZK NIZK. Prior to our work, the Sub-ZK property of NIZKs was achieved using concrete knowledge assumptions.

In this paper we show that a wide class of (computationally) special-sound proofs of knowledge which have unique response property and are standard-model zero-knowledge are simulation-extractable when made non-interactive by the Fiat–Shamir transform. We prove that two efficient updatable universal zkSNARKs — Plonk[27] and Sonic[40] — meet these requirements and conclude by showing their simulation-extractability. As a side result we also show that relying security on rewinding and Fiat–Shamir transform often comes at a great price of inefficient (yet still polynomial time) knowledge extraction and the security loss introduced by these techniques should always be taken into account.

In this notebook, we will simulate the evolution of a simplified blockchain system on which Zeth is deployed in order to better educate the choice of the various protocol parameters (number of input notes, number of output notes, depth of the Merkle tree etc). This notebook can be used for further experiments (using parameters which are not yet documented). This notebook is focused around some key questions regarding the blockchain state growth under different configurations. This is particularly important since the growth of the blockchain state is a key factor that impacts the number of nodes on the distributed system (it drives the HW requirements for existing nodes on the network as well as affects how easy it is for new nodes to join the network (i.e. sync a new node)). In other words, as the number of nodes on a blockchain "boils down to convenience", we are interested to see how convenient (easy/fast/cheap) it is to validate on a blockchain under various network assumptions. Studying the state growth provides valuable hints with that regard. Nevertheless, the reader is reminded that, by the very essence of modeling, we make several simplifying assumptions in the section below that will thus ignore various aspects of a "real-life" running system.

Privacy preserving protocols suffer from the need to pay transaction fees on blockchain systems. While such fees constitute a sound economic barrier to a wide class of Denial of Service attacks, they also represent impediments to the design of state transitions with anonymous initiators. In this paper, we navigate the design space for "Zeth cryptographic relays". These enable Zeth users to carry out Zeth payments anonymously by relying on an extra party - a relay - to settle and execute state transitions on the blockchain.

In this post, we look at the Zeth protocol and list a set of considerations for the design of Zeth Bearer Instruments.

In this blog post, I will go back to some of the early results that pioneered the notion of "zero-knowledge proof" as we know it today. To that end, I will provide an introduction to the notion of Interactive Proofs (IP) as well as intuition as to what makes interactive protocols so powerful. The goal is to identify the pillars that make interactive zero-knowledge proofs possible, and then study how one can "play with" and substitute these essential ingredients in order to obtain Non-Interactive Zero-Knowledge (NIZK). Such non-interactive protocols have gained tremendous traction over the past few years, and are now used in cloud-computing settings, as well as on blockchain systems to only name a few of their numerous applications. While the past decades have seen a surge of new constructions (all offering different trade-offs) I propose - through this article - to take a step back and look at what makes all these beautiful protocols work and so appealing.

In this paper, we present Zecale, a general purpose SNARK proof aggregator that uses recursive composition of SNARKs. We start by introducing the notion of recursive composition of SNARKs, before introducing Zecale as a privacy preserving scalability solution. Then, we list application types that can emerge and be built with Zecale. Finally, we argue that such scalability solutions for privacy preserving state transitions are paramount to emulate 'cash' on blockchain systems.

This document specifies the Zeth protocol with various security fixes and performance improvements from the initial design.

In this note, we remark that the aggregation property of the BLS signature scheme yields an efficient Content Extraction Signature (CES). This construction can be used to build digital credentials that support selective disclosure in various settings. Interestingly, this construction is efficient and well suited to build credential issuance schemes with various applications in the client-server or in the distributed ledger models. Finally, we sketch a protocol that combines the CES with the use of a NIZK which allows to prove predicate satisfaction on claims extracted from a credential, while keeping the data secret.

While NIZK arguments in the CRS model are widely studied, the question of what happens when the CRS was subverted has received little attention. In ASIACRYPT 2016, Bellare, Fuchsbauer, and Scafuro showed the first negative and positive results in the case of NIZK, proving also that it is impossible to achieve subversion soundness and (even non-subversion) zero-knowledge at the same time. On the positive side, they constructed an involved sound and subversion-zero-knowledge (Sub-ZK) non-succinct NIZK argument for NP. We consider the practically very relevant case of zk-SNARKs. We make Groth's zk-SNARK for Circuit-SAT from EUROCRYPT 2016 computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes. We only require the CRS trapdoor to be extractable and the CRS to be publicly verifiable. To achieve the latter, we add some new elements to the CRS and construct an efficient CRS verification algorithm. We also provide a definitional framework for knowledge-sound and Sub-ZK SNARKs.

Recently, Bellare et al. defined subversion-resistance (security in the case the CRS creator may be malicious) for NIZK. In particular, a Sub-ZK NIZK is zero-knowledge, even in the case of subverted CRS. We study Sub-ZK QA-NIZKs, where the CRS can depend on the language parameter. First, we observe that subversion zero-knowledge (Sub-ZK) in the CRS model corresponds to no-auxiliary-string non-black-box NIZK in the Bare Public Key model, and hence, the use of non-black-box techniques is needed to obtain Sub-ZK. Second, we give a precise definition of Sub-ZK QA-NIZKs that are (knowledge-)sound if the language parameter but not the CRS is subverted and zero-knowledge even if both are subverted. Third, we prove that the most efficient known QA-NIZK for linear subspaces by Kiltz and Wee is Sub-ZK under a new knowledge assumption that by itself is secure in (a weaker version of) the algebraic group model. Depending on the parameter setting, it is (knowledge-)sound under different non-falsifiable assumptions, some of which do not belong to the family of knowledge assumptions.

Pointcheval-Sanders (PS) signatures are well-studied in the literature and have found use within e.g. threshold credential schemes and redactable anonymous credential schemes. The present work leverages a mapping between PS signatures and a related class of polynomial-based signatures to construct multiple new signature/credential schemes. Specifically, new protocols for multi-message signatures, sequential aggregate signatures, signatures for message commitments, redactable signatures, and unlinkable redactable signatures are presented. A redactable anonymous credential scheme is also constructed. All original protocols employ constant-sized secret keys rather than linear-sized (in the number of messages/attributes). Security properties of the new protocols are analysed and a general discussion of security properties for both PS signatures and the new schemes is provided.

Variant secret sharing schemes deriving from Shamir's threshold secret sharing protocol are presented. Results include multi-secret sharing protocols using shares with O(1) elements, independent of the number of secrets. The new schemes achieve a weaker notion of security (they're secure rather than strongly secure) but maintain a property called K-privacy (inspired by k-anonymity). K-privacy ensures that all secrets remain private with respect to a subset of the secret space, though the particular subset providing privacy may vary among adversaries that acquire distinct sub-threshold sets of shares. Depending on the number of secrets and the protocol details, secure K-private multi-secret sharing schemes may be ''almost'' strongly secure or may remain merely secure and K-private - a difference captured by the notion of K-security. Novel applications of the multi-secret sharing schemes are presented, realising a primitive called a switched threshold signature. Switched threshold signatures have the quirky property that aggregating a threshold number of signatures of one type (e.g. Pointcheval-Sanders signatures) ''switches'' the signatures into a master signature of a different type. Collectively these results may permit efficiencies within, e.g., threshold credential issuance protocols.

Engineers of identity systems, both digital and non-digital, have assumptions and requirements that often lead to fundamentally different ideas about useful solutions. One’s preferred use cases establish mental models tailored to those uses, which in turn shape discussion and engineering of identity systems. The differences between these mental models consistently cause confusion and disagreement when advocates of different models collaborate, often without the parties realizing that others may be speaking from a distinctly different, yet valid, notion of identity. Considering different mental models allows for constructive dialogue and reconciliation of requirements, creating opportunities to address a wider set of use cases and to build systems with better overall applicability and quality. We present five distinct mental models observed in conversations among technologists and laypeople when discussing identity. We then discuss observed patterns of discussion and design that result from the intersection of some pairs of mental models. Finally, we close with guidance for incorporating all five mental models when evaluating or designing any real-world or digital-identity system. We propose that understanding and considering these different mental models will result in more fruitful collaboration and ultimately in better identity systems.

A shuffle argument is a cryptographic primitive for proving correct behaviour of mix-networks without leaking any private information. Several recent constructions of non-interactive shuffle arguments avoid the random oracle model but require the public key to be trusted. We augment the most efficient argument by Fauzi et al. [Asiacrypt 2017] with a distributed key generation protocol that assures soundness of the argument if at least one party in the protocol is honest and additionally provide a key verification algorithm which guarantees zero-knowledge even if all the parties are malicious. Furthermore, we simplify their construction and improve security by using weaker assumptions while retaining roughly the same level of efficiency. We also provide an implementation to the distributed key generation protocol and the shuffle argument.

zk-SNARKs are powerful cryptographic tools that provide new ways to achieve data privacy and verification. But what is a zk-SNARK? This primer introduces zk-SNARKs and explains why they’re so important in the blockchain context.

Zero-knowledge SNARKs (zk-SNARKs) have recently found various applications in verifiable computation and blockchain applications (Zerocash), but unfortunately they rely on a common reference string (CRS) that has to be generated by a trusted party. A standard suggestion, pursued by Ben Sasson et al. [IEEE S&P, 2015], is to generate CRS via a multi-party protocol. We enhance their CRS-generation protocol to achieve UC-security. This allows to safely compose the CRS-generation protocol with the zk-SNARK in a black-box manner with the insurance that the security of the zk-SNARK is not influenced. Differently from the previous work, the new CRS-generation protocol also avoids the random oracle model which is typically not required by zk-SNARKs themselves. As a case study, we apply the protocol to the state-of-the-art zk-SNARK by Groth [EUROCRYPT, 2016].

Transaction privacy is a hard problem on an account-based blockchain such as Ethereum. While Ben-Sasson et al. presented the Zerocash protocol [BCG+14] as a decentralized anonymous payment (DAP) scheme standing on top of Bitcoin, no study about the integration of such DAP on top of a ledger defined in the account model was provided. In this paper we aim to fill this gap and propose ZETH, an adaptation of Zerocash that can be deployed on top of Ethereum without making any change to the base layer. Our study shows that not only ZETH could be used to transfer Ether, the base currency of Ethereum, but it could also be used to transfer other types of smart contract-based digital assets. We propose an analysis of ZETH's privacy promises and argue that information leakages intrinsic to the use of this protocol are controlled and well-defined, which makes it a viable solution to support private transactions in the context of public and permissioned chains.

We define a new UC functionality (DL-extractable commitment scheme) that allows committer to open a commitment to a group element g^x; however, the simulator will be able to extract its discrete logarithm x. Such functionality is useful in situations where the secrecy of x is important since the knowledge of x enables to break privacy while the simulator needs to know x to be able to simulate the corrupted committer. Based on Fujisaki's UC-secure commitment scheme and the Damgard-Fujisaki integer commitment scheme, we propose an efficient commitment scheme that realizes the new functionality. As another novelty, we construct the new scheme in the weaker RPK (registered public key) model instead of the CRS model used by Fujisaki.