Paper 2023/1416 Original: eprint.iacr.org/2023/1416 ↗
On Black-Box Knowledge-Sound Commit-And-Prove SNARKs
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2023-09-20: last updated
- 2023-09-20: published
- Short URL
- https://ia.cr/2023/1416
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}