NIZK from SNARG

Fuyuki Kitagawa; Takahiro Matsuda; Takashi Yamakawa

Paper 2020/649

NIZK from SNARG

Fuyuki Kitagawa, 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 for some constant , where is the statement length, is the witness length, and 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 SNARK to a zero-knowledge SNARG assuming the existence of one-way functions where SNARK is a SNARG with the knowledge-extractability. For this conversion, we require the SNARK to be fully succinct, i.e., the proof size is . 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.

Note: (Mar. 2 2022) Improved the main result in regard to the required succinctness parameter for SNARGs. Fixed problems in the side result about zero-knowledge SNARGs. (See Appendix A.)

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in TCC 2020
Keywords: zero knowledge NIZK SNARG
Contact author(s): takashi yamakawa ga @ hco ntt co jp
History: 2022-03-02: last of 2 revisions; 2020-06-03: received; See all versions
Short URL: https://ia.cr/2020/649
License: CC BY

BibTeX

@misc{cryptoeprint:2020/649,
      author = {Fuyuki Kitagawa and Takahiro Matsuda and Takashi Yamakawa},
      title = {{NIZK} from {SNARG}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/649},
      year = {2020},
      url = {https://eprint.iacr.org/2020/649}
}