We provide a zero-knowledge argument for arithmetic circuit satisfiability with a communication complexity that grows logarithmically in the size of the circuit. The round complexity is also logarithmic and for an arithmetic circuit with fan-in 2 gates the computation of the prover and verifier is linear in the size of the circuit. The soundness of our argument relies solely on the well-established discrete logarithm assumption in prime order groups. At the heart of our new argument system is an efficient zero-knowledge argument of knowledge of openings of two Pedersen multicommitments satisfying an inner product relation, which is of independent interest. The inner product argument requires logarithmic communication, logarithmic interaction and linear computation for both the prover and the verifier. We also develop a scheme to commit to a polynomial and later reveal the evaluation at an arbitrary point, in a verifiable manner. This is used to build an optimized version of the constant round square root complexity argument of Groth (CRYPTO 2009), which reduces both communication and round complexity. Informally, a zero-knowledge argument involves two parties, the prover and the verifier, and allows the prover to prove to the verifier that a particular statement is true, without revealing anything else about the statement itself. Statements are of the form u ∈ L, where L is a language in NP. We call w a witness for a statement u if (u, w) ∈ R, where R is a polynomial time decidable binary relation associated with L. We require the zero-knowledge argument to be complete, sound and zero-knowledge. A prover with a witness w for u ∈ L can convince the verifier of this fact. Soundness: A prover cannot convince a verifier when u / ∈ L. Zero-knowledge: The interaction should not reveal anything to the verifier except that u ∈ L. In particular, it should not reveal the prover's witness w. Our goal is to build an efficient argument system for the satisfiability of an arithmetic circuit, i.e., a circuit that consists of addition and multiplication gates over a finite field Z p . Moreover we want to base the security of this argument solely on the discrete logarithm assumption: this will provide both strong security guarantees and good efficiency since there exists no known attacks better than generic ones for well-chosen elliptic curve subgroups. The most efficient zero-knowledge arguments solely based on the discrete logarithm assumption are Groth's protocol based on linear algebra [Gro09b] and its variant by Seo [Seo11]. Both of these protocols have a communication complexity that is proportional to the square root of the circuit size. This square root complexity has since then appeared as a (perhaps fundamental) barrier for discrete logarithm-based arguments for circuit satisfiability. We provide an honest verifier zero-knowledge argument for arithmetic circuit satisfiability based on the discrete logarithm assumption that only requires a logarithmic communication complexity. Our argument has perfect completeness and perfect special honest verifier zero-knowledge. Soundness is computational and based on the discrete logarithm assumption. We require a logarithmic number of moves, and both the prover and verifier have linear computational complexity. The argument is therefore efficient on all parameters with the biggest improvement being in the communication complexity. Improved Square Root Complexity Argument. We start from the circuit satisfiability argument of Groth [Gro09b], which requires 7 moves and has square root communication complexity in the total number of gates. In this argument the prover commits to all the wires using homomorphic multicommitments, verifies addition gates using the homomorphic properties, and uses a product argument to show that the multiplication gates are satisfied. We first improve Groth's argument into a 5 moves argument with square root communication complexity in the number of multiplication gates only. We
Bootle et al. REF construct arguments with logarithmic communication complexity and linear computation costs based on the discrete logarithm assumption.
Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting
IACR Cryptology ePrint Archive
IACR Cryptology ePrint Archive
Computer Science Mathematics