International Association
for Cryptologic Research

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.