Paper 2023/1416

On Black-Box Knowledge-Sound Commit-And-Prove SNARKs

Helger Lipmaa, University of Tartu
Abstract

Gentry and Wichs proved that adaptively sound SNARGs for hard languages need non-falsifiable assumptions. Lipmaa and Pavlyk claimed Gentry-Wichs is tight by constructing a non-adaptively sound zk-SNARG FANA for NP from falsifiable assumptions. We show that FANA is flawed. We define and construct a fully algebraic $F$-position-binding vector commitment scheme VCF. We construct a concretely efficient commit-and-prove zk-SNARK Punic, a version of FANA with an additional VCF commitment to the witness. Punic satisfies semi-adaptive black-box $G$-knowledge-soundness, a new natural knowledge-soundness notion for commit-and-prove SNARKs. We use a new proof technique to achieve global consistency using a functional somewhere-extractable commitment scheme to extract vector commitment's local proofs.

Note: Full version of the Asiacrypt 2023 paper.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Keywords
Commit-and-provefalsifiable assumptionsGentry-Wichsnon-adaptive soundnessQA-NIZKvector commitmentzk-SNARK
Contact author(s)
helger lipmaa @ gmail com
History
2023-09-24: approved
2023-09-20: received
See all versions
Short URL
https://ia.cr/2023/1416
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1416,
      author = {Helger Lipmaa},
      title = {On Black-Box Knowledge-Sound Commit-And-Prove {SNARKs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1416},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1416}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.