Cryptology ePrint Archive: Report 2012/548

Efficient Modular NIZK Arguments from Shift and Product

Prastudy Fauzi and Helger Lipmaa and Bingsheng Zhang

Abstract: We propose a non-interactive product argument, that is more efficient than the one by Groth and Lipmaa, and a novel shift argument. We then use them to design several novel non-interactive zero-knowledge (NIZK) arguments. We obtain the first range proof with constant communication and subquadratic prover's computation. We construct NIZK arguments for $\mathbf{NP}$-complete languages, {\textsc{Set-Partition}}, {\textsc{Subset-Sum}} and {\textsc{Decision-Knapsack}}, with constant communication, subquadratic prover's computation and linear verifier's computation.

Category / Keywords: FFT, multi-exponentiation, non-interactive zero knowledge, product argument, range argument, shift argument

Date: received 19 Sep 2012, last revised 9 Sep 2013

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

Note: Full version corresponding to a CANS 2013 paper

Version: 20130909:211622 (All versions of this report)

Short URL: ia.cr/2012/548

Discussion forum: Show discussion | Start new discussion