Cryptology ePrint Archive: Report 2014/396

Efficient Short Adaptive NIZK for NP

Helger Lipmaa

Abstract: In Eurocrypt 2013, Gennaro et al.~proposed an efficient \emph{non-adaptive} short QAP-based NIZK argument for $\textsc{Circuit-SAT}$, where non-adaptivity means that the CRS depends on the statement to be proven. While their argument can be made adaptive by using universal circuits, this increases the prover computation by a logarithmic multiplicative factor. By following the QAP-based approach, we propose an efficient product argument, and then use it together with a modified shift argument of Fauzi et al.~in the modular framework of Groth to design an \emph{adaptive} short NIZK argument for $\textsc{Subset-Sum}$ and several other NP-complete languages that has the same complexity parameters as the QAP-based non-adaptive argument, resulting in the first adaptive short NIZK arguments for NP where the prover computation is dominated by a linear number of cryptographic operations. We also construct the most efficient known range argument.

Category / Keywords: $\textsc{Circuit-SAT}$, CRS, interpolation, NIZK, numerical NP-complete languages, product argument, quadratic arithmetic program, range proof

Date: received 30 May 2014, last revised 28 Sep 2014

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

Note: Second eprint version (28.09.2014) is thoroughly updated, and includes several new results

Version: 20140928:092635 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]