**NIZK from SNARG**

*Fuyuki Kitagawa and Takahiro Matsuda and Takashi Yamakawa*

**Abstract: **We give a construction of a non-interactive zero-knowledge (NIZK) argument for all NP languages based on a succinct non-interactive argument (SNARG) for all NP languages and a one-way function. The succinctness requirement for the SNARG is rather mild: We only require that the proof size be $|\pi|=\mathsf{poly}(\lambda)(|x|+|w|)^c$ for some constant $c<1/2$, where $|x|$ is the statement length, $|w|$ is the witness length, and $\lambda$ is the security parameter. Especially, we do not require anything about the efficiency of the verification.

Based on this result, we also give a generic conversion from a SNARG to a zero-knowledge SNARG assuming the existence of CPA secure public-key encryption. For this conversion, we require a SNARG to have efficient verification, i.e., the computational complexity of the verification algorithm is $\mathsf{poly}(\lambda)(|x|+|w|)^{o(1)}$. Before this work, such a conversion was only known if we additionally assume the existence of a NIZK.

Along the way of obtaining our result, we give a generic compiler to upgrade a NIZK for all NP languages with non-adaptive zero-knowledge to one with adaptive zero-knowledge. Though this can be shown by carefully combining known results, to the best of our knowledge, no explicit proof of this generic conversion has been presented.

**Category / Keywords: **foundations / zero knowledge, NIZK, SNARG

**Date: **received 29 May 2020

**Contact author: **takashi yamakawa ga at hco ntt co jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20200603:095149 (All versions of this report)

**Short URL: **ia.cr/2020/649

[ Cryptology ePrint archive ]