Paper 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.