Paper 2023/1416
On Black-Box Knowledge-Sound Commit-And-Prove SNARKs
, University of TartuAbstract
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
-
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}
}
