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 $|\pi|=\mathsf{poly}(\lambda)(|x|+|w|)^\delta$ for some constant $\delta<1$, 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 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 $\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.

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 knowledgeNIZKSNARG
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2020/649}},
      url = {https://eprint.iacr.org/2020/649}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.