Paper 2012/548

Efficient Modular NIZK Arguments from Shift and Product

Prastudy Fauzi and Helger Lipmaa and Bingsheng Zhang

Abstract

Very few general techniques are known for constructing succinct and computationally efficient NIZK arguments for non-trivial languages. Groth proposed product and permutation arguments, and then used them in a modular way to construct a succinct Circuit-SAT argument. Lipmaa improved the complexity of Groth's basic arguments, while Chaabouni, Lipmaa, and Zhang (FC 2012) used them to construct the first constant-length NIZK range argument. Since Groth's and Lipmaa's basic arguments have quadratic prover's computation, so do all the resulting modular arguments. We continue the study of modular NIZK arguments, by proposing a significantly more efficient version of the product argument and a novel shift argument. Based on these two arguments, we significantly speed up the range argument from FC 2012, obtaining the first range proof with constant length and subquadratic (in the logarithm of the range length) prover's computation. We also propose efficient arguments for three $\mathbf{NP}$-complete languages, set partition, subset sum and decision knapsack, with constant communication, $n^{1 + o (1)}$ prover's computation and linear verifier's computation.

Note: Last version has improved readability, comparison with some recent work, and includes one more concrete direct argument for an NP-complete language