NIZK from SNARGs

• Published in: Journal of cryptology 2023-04, Vol.36 (2), Article 14
• Main Authors: Kitagawa, Fuyuki, Matsuda, Takahiro, Yamakawa, Takashi
• Format: Article
• Language: English
• Subjects: Coding and Information Theory; Combinatorics; Communications Engineering; Computational Mathematics and Numerical Analysis; Computer Science; Conversion; Knowledge; Languages; Networks; Probability Theory and Stochastic Processes; Research Article
• ISSN: 0933-2790; 1432-1378
• DOI: 10.1007/s00145-023-09449-3

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 | π | = poly ( λ ) ( | x | + | w | ) δ for some constant δ < 1 , where | x | is the statement length, | w | is the witness length, and λ is the security parameter. Especially, we do not require the efficiency of the verification to be sublinear in | x | or | w |. As a corollary, we give a generic conversion from a SNARK to a zero-knowledge SNARG assuming the existence of one-way functions where SNARK is a SNARG with knowledge-extractability. For this conversion, we require the SNARK to be fully succinct, i.e., the proof size is poly ( λ ) ( | 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.