Cryptology ePrint Archive: Report 2014/396

Almost Optimal Short Adaptive Non-Interactive Zero Knowledge

Helger Lipmaa

Abstract: Several recent short NIZK arguments are constructed in a modular way from a small number of basic arguments like the product argument or the shift argument. The main technical novelty of the current work is a significantly more efficient version of the product argument. Based on this, we propose an adaptive NIZK range argument with almost optimal complexity: constant communication (in group elements), constant verifier's computational complexity (in cryptographic operations), and $\Theta (n \log n)$ [resp., $\Theta (n)$] prover's computational complexity (in non-cryptographic [resp., cryptographic] operations). The latter can be compared to $n \log^{\omega (1)} n$ in the most efficient \emph{published} short adaptive non-interactive range argument, or $\Theta (n \log^2 n)$ [resp., $\Theta (n \log n)$] that is achievable when following QAP-based framework from Eurocrypt 2013. Here, $n$ is the logarithm of the range length. The new product argument can be used to construct efficient adaptive NIZK arguments for many other languages, including several that are $\mathsf{NP}$-complete like $\textsc{SubsetSum}$. Importantly, for all such languages, new adaptive arguments achieve better prover's computation than the QAP-based framework.

Category / Keywords: cryptographic protocols / CRS, NIZK, range proof, interpolation, product argument, quadratic arithmetic program

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

Contact author: helger lipmaa at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140530:123718 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]