Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols/Decision knapsack, FFT, non-interactive zero knowledge, product argument, range argument, set partition, shift argument, subset sum

Date: received 19 Sep 2012, last revised 2 Jul 2013

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20130702:141755 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]