Efficient non-interactive zero-knowledge Proofs

Abstract

Non-Interactive Zero-Knowledge (NIZK) proofs, are proofs that yield nothing beyond their validity. As opposed to the interactive variant, NIZK proofs consist of only one message and are more suited for high-latency scenarios and for building inherently non- interactive schemes, like signatures or encryption. With the advent of pairing-based cryptography many cryptosystems have been built using bilinear groups, that is, three abelian groups G1,G2,GT oforderqtogetherwithabilinear function e : G1 × G2 → GT . Statements related to pairing-based cryptographic schemes are naturally expressed as the satisfiability of equations over these groups and Zq. The Groth-Sahai proof system, introduced by Groth and Sahai at Eurocrypt 2008, provides NIZK proofs for the satisfiability of equations over bilinear groups and over the integers modulo a prime q. Although Groth-Sahai proofs are quite efficient, they easily get expensive unless the statement is very simple. Specifically, proving satisfiability of m equations in n variables requires sending as commitments to the solutions Θ(n) elements of a bilinear group, and a proof that they satisfy the equations, which we simply call the proof, requiring additional Θ(m) group elements. In this thesis we study how to construct aggregated proofs i.e. proofs of size independent of the number of equations for different types of equations and how to use them to build more efficient cryptographic schemes. We show that linear equations admit aggregated proofs of size Θ(1). We then study the case of quadratic integer equations, more concretely the equation b(b − 1) = 0 which is the most useful type of quadratic integer equation, and construct an aggregated proof of size Θ(1). We use these results to build more efficient threshold Groth-Sahai proofs and more efficient ring signatures. We also study a natural generalization of quadratic equations which we call set-membership proofs i.e. show that a variable belongs to some set. We first construct an aggregated proof of size Θ(t), where t is the set size, and of size Θ(logt) if the set is of the form [0,t − 1] ⊂ Zq. Then, we further improve the size of our set-membership proofs and construct aggregated proofs of size Θ(log t). We note that some cryptographic schemes can be naturally constructed as set-membership proofs, specifically we study the case of proofs of correctness of a shuffle and range proofs. Starting from set-membership proofs as a common building block, we build the shortest proofs for both proof systems.