## 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 ]