Pairing-based Succinct Non-interactive Zero-Knowledge Arguments

Jens Groth gave the third talk on Wednesday with this descriptive title. After motivating the construction with the correctness requirement for encrypted votes in an election, the speaker explained the basic properties of zero-knowledge arguments followed by the essential facts about his construction. It allows to prove satisfiability for any circuit consisting of NAND gates, which is NP-complete. The argument is publicly verifiable and sublinear in the number of gates, but it requires a quadratic non-uniform CRS. The presented table about related results suggests that there is a trade-off between the size of the argument and the size of the CRS. In terms of assumptions, the argument is based on the non-standard knowledge of exponent assumption and pairings but not the random oracle model. Finally, it achieves perfect completeness, computational soundness against an adaptive adversary, and perfect zero-knowledge.

A key component of the construction is an extended Pedersen commitment, where there is one commitment for a vector of values. Together with a second commitment of the same form for a related generator, one can create a so-called knowledge commitment that can be verified with a pairing. The knowledge of exponent assumption implies the knowledge of the committed values if the verification is successful.

There are three sub-arguments used as building blocks: a restriction argument, a product argument, and a permutation argument. The restriction argument shows that the values of a given subset in the commitment are zero, the product argument shows that the committed values are the component-wise product of the values of two other commitments, and the permutation argument shows that the values of one commitment are a permutation of the values of another.

The zero-knowledge argument now works as follows: The prover commits with three knowledge commitments to the two inputs and the outputs of all NAND gates. The restriction argument is used to show that the redundant positions in the commitments are set to zero, and the product argument is used that the square of all values equals the value, which implies that all values are 0 or 1, i.e., bits. For a NAND gates, the product of the input values equals one minus the output value. Therefore, the product argument can be used together with the homomorphic property of the commitment scheme to show that all gates are computed correctly. Finally, the permutation argument is used to show that the value on the wires are consistent.