Recent efficient constructions of zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs), require a setup phase in which a common-reference string (CRS) with a certain structure is generated. This CRS is sometimes referred to as the public parameters of the system, and is used for constructing and verifying proofs. A drawback of these constructions is that whomever runs the setup phase subsequently possesses trapdoor information enabling them to produce fraudulent pseudoproofs.
Rafaël del Pino, Vadim Lyubashevsky, Gregory Neven, Gregor Seiler
We propose a lattice-based electronic voting scheme, EVOLVE (Electronic Voting from Lattices with Verification), which is conjectured to resist attacks by quantum computers. Our protocol involves a number of voting authorities so that vote privacy is maintained as long as at least one of the authorities is honest, while the integrity of the result is guaranteed even when all authorities collude. Furthermore, the result of the vote can be independently computed by any observer. At the core of the protocol is the utilization of a homomorphic commitment scheme with strategically orchestrated zero-knowledge proofs: voters use approximate but efficient "Fiat-Shamir with Aborts" proofs to show the validity of their vote, while the authorities use amortized exact proofs to show that the commitments are well-formed. We also present a novel efficient zero-knowledge proof that one of two lattice-based statements is true (so-called OR proof) and a new mechanism to control the size of the randomness when applying the homomorphism to commitments. We give concrete parameter choices to securely instantiate and evaluate the efficiency of our scheme. Our prototype implementation shows that the voters require $8$ milliseconds to submit a vote of size about $20$KB to each authority and it takes each authority $0.15$ seconds per voter to create a proof that his vote was valid. The size of the vote share that each authority produces is approximately $15$KB per voter, which we believe is well within the practical bounds for a large-scale election.
For a linear function f, a vector \(\mathbf{x}\) with small coefficients, and a vector \(y=f(\mathbf{x})\), we would like to be able to give a zero-knowledge proof for the knowledge of an \(\mathbf{x}'\) with small coefficients that satisfies \(f(\mathbf{x}')=y\). This is a common scenario in lattice-based cryptography, and there is currently no satisfactory solution for this problem. All known protocols are built via the repetition of a basic protocol that only has constant (1/2 or 2/3) soundness error. This implies that the communication complexity of the final protocol will be at least a factor of k larger than that of the basic one, where k is the security parameter.
Foteini Baldimtsi, Jan Camenisch, Maria Dubovitskaya, Anna Lysyanskaya · 7 authors
Membership revocation is essential for cryptographic applications, from traditional PKIs to group signatures and anonymous credentials. Of the various solutions for the revocation problem that have been explored, dynamic accumulators are one of the most promising. We propose Braavos, a new, RSA-based, dynamic accumulator. It has optimal communication complexity and, when combined with efficient zero-knowledge proofs, provides an ideal solution for anonymous revocation. For the construction of Braavos we use a modular approach: we show how to build an accumulator with better functionality and security from accumulators with fewer features and weaker security guarantees. We then describe an anonymous revocation component (ARC) that can be instantiated using any dynamic accumulator. ARC can be added to any anonymous system, such as anonymous credentials or group signatures, in order to equip it with a revocation functionality. Finally, we implement ARC with Braavos and plug it into Idemix, the leading implementation of anonymous credentials. This work resolves, for the first time, the problem of practical revocation for anonymous credential systems.
We present a zero-knowledge argument for NP with low communication complexity, low concrete cost for both the prover and the verifier, and no trusted setup, based on standard cryptographic assumptions. Communication is proportional to d log G (for d the depth and G the width of the verifying circuit) plus the square root of the witness size. When applied to batched or data-parallel statements, the prover's runtime is linear and the verifier's is sub-linear in the verifying circuit size, both with good constants. In addition, witness-related communication can be reduced, at the cost of increased verifier runtime, by leveraging a new commitment scheme for multilinear polynomials, which may be of independent interest. These properties represent a new point in the tradeoffs among setup, complexity assumptions, proof size, and computational cost. We apply the Fiat-Shamir heuristic to this argument to produce a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) in the random oracle model, based on the discrete log assumption, which we call Hyrax. We implement Hyrax and evaluate it against five state-of-the-art baseline systems. Our evaluation shows that, even for modest problem sizes, Hyrax gives smaller proofs than all but the most computationally costly baseline, and that its prover and verifier are each faster than three of the five baselines.
The Fiat-Shamir construction (Crypto 1986) is an efficient transformation in the random oracle model for creating non-interactive proof systems and signatures from sigma-protocols. In classical cryptography, Fiat-Shamir is a zero-knowledge proof of knowledge assuming that the underlying sigma-protocol has the zero-knowledge and special soundness properties. Unfortunately, Ambainis, Rosmanis, and Unruh (FOCS 2014) ruled out non-relativizing proofs under those conditions in the quantum setting.
Youngho Yoo, Reza Azarderakhsh, Amir Jalali, David Jao · 5 authors
We present the first general-purpose digital signature scheme \nbased on supersingular elliptic curve isogenies secure against quantum \nadversaries in the quantum random oracle model with small key sizes. \nThis scheme is an application of Unruh’s construction of non-interactive \nzero-knowledge proofs to an interactive zero-knowledge proof proposed \nby De Feo, Jao, and Plut. We implement our proposed scheme on an x86- \n64 PC platform as well as an ARM-powered device. We exploit the stateof-the-art \ntechniques to speed up the computations for general C and \nassembly. Finally, we provide timing results for real world applications.
We describe a new succinct zero-knowledge argument protocol with the following properties. The prover commits to a large data-set M, and can thereafter prove many statements of the form \(\exists w : \mathcal {R}_i(M,w)=1\), where \(\mathcal {R}_i\) is a public function. The protocol is succinct in the sense that the cost for the verifier (in computation & communication) does not depend on |M|, not even in any initialization phase In each proof, the computation/communication cost for both the prover and the verifier is proportional only to the running time of an oblivious RAM program implementing \(\mathcal {R}_i\) (in particular, this can be sublinear in |M|). The only costs that scale with |M| are the computational costs of the prover in a one-time initial commitment to M.
We present Strain, a new auction protocol running on top of blockchains and guaranteeing bid confidentiality against fully-malicious parties. As our goal is efficiency and low blockchain latency, we abstain from using traditional, highly interactive MPC primitives such as secret shares. We focus on a slightly weaker adversary model than MPC which allows Strain to achieve constant latency in both the number of parties and the bid length. The main idea behind Strain is a new maliciously-secure two-party comparison mechanism executed between any pair of bids in parallel. Using zero-knowledge proofs, Strain broadcasts the outcome of comparisons on the blockchain in a way that all parties can verify each outcome. Strain’s latency is not only asymptotically optimal, but also efficient in practice, requiring a total of just 4 blocks of the underlying blockchain. Strain provides typical auction security requirements such as non-retractable bids against fully-malicious adversaries.
Advanced cryptographic protocols such as anonymous credentials, voting schemes, and e-cash are typically constructed by suitably combining signature, commitment, and encryption schemes with zero-knowledge proofs. Indeed, a large body of protocols have been constructed in that manner from Camenisch-Lysyanskaya signatures and generalized Schnorr proofs. In this paper, we build a similar framework for lattice-based schemes by presenting a signature and commitment scheme that are compatible with Lyubashevsky’s Fiat-Shamir proofs with abort, currently the most efficient zero-knowledge proofs for lattices. The latter proofs provide a weaker, relaxed form of soundness, i.e., the witnesses that the knowledge extractor can obtain are guaranteed to lie only in a domain that is larger than the one from which the inputs of honest provers need to come. To cope with this soundness problem, we define corresponding notions of relaxed signature and commitment schemes. We demonstrate the flexibility and efficiency of our new primitives by constructing a new lattice-based anonymous attribute token scheme and providing concrete parameters to securely instantiate this scheme.
Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra · 6 authors
We propose Bulletproofs, a new non-interactive zero-knowledge proof protocol with very short proofs and without a trusted setup; the proof size is only logarithmic in the witness size. Bulletproofs are especially well suited for efficient range proofs on committed values: they enable proving that a committed value is in a range using only 2 log_2(n)+9 group and field elements, where n is the bit length of the range. Proof generation and verification times are linear in n. Bulletproofs greatly improve on the linear (in n) sized range proofs in existing proposals for confidential transactions in Bitcoin and other cryptocurrencies. Moreover, Bulletproofs supports aggregation of range proofs, so that a party can prove that m commitments lie in a given range by providing only an additive O(log(m)) group elements over the length of a single proof. To aggregate proofs from multiple parties, we enable the parties to generate a single proof without revealing their inputs to each other via a simple multi-party computation (MPC) protocol for constructing Bulletproofs. This MPC protocol uses either a constant number of rounds and linear communication, or a logarithmic number of rounds and logarithmic communication. We show that verification time, while asymptotically linear, is very efficient in practice. The marginal cost of batch verifying 32 aggregated range proofs is less than the cost of verifying 32 ECDSA signatures. Bulletproofs build on the techniques of Bootle et al. (EUROCRYPT 2016). Beyond range proofs, Bulletproofs provide short zero-knowledge proofs for general arithmetic circuits while only relying on the discrete logarithm assumption and without requiring a trusted setup. We discuss many applications that would benefit from Bulletproofs, primarily in the area of cryptocurrencies. The efficiency of Bulletproofs is particularly well suited for the distributed and trustless nature of blockchains. The full version of this article is available on ePrint.
We propose a framework for constructing efficient designated-verifier non-interactive zero-knowledge proofs (\(\mathsf {DVNIZK}\)) for a wide class of algebraic languages over abelian groups, under standard assumptions. The proofs obtained via our framework are proofs of knowledge, enjoy statistical, and unbounded soundness (the soundness holds even when the prover receives arbitrary feedbacks on previous proofs). Previously, no efficient \(\mathsf {DVNIZK}\) system satisfying any of those three properties was known. Our framework allows proving arbitrary relations between cryptographic primitives such as Pedersen commitments, ElGamal encryptions, or Paillier encryptions, in an efficient way. For the latter, we further exhibit the first non-interactive zero-knowledge proof system in the standard model that is more efficient than proofs obtained via the Fiat-Shamir transform, with still-meaningful security guarantees and under standard assumptions. Our framework has numerous applications, in particular for the design of efficient privacy-preserving non-interactive authentication.