Paper 2024/816
Zero-knowledge IOPs Approaching Witness Length
Abstract
Interactive Oracle Proofs (IOPs) allow a probabilistic verifier interacting with a prover to verify the validity of an NP statement while reading only few bits from the prover messages. IOPs generalize standard Probabilistically-Checkable Proofs (PCPs) to the interactive setting, and in the few years since their introduction have already exhibited major improvements in main parameters of interest (such as the proof length and prover and verifier running times), which in turn led to significant improvements in constructions of succinct arguments. Zero-Knowledge (ZK) IOPs additionally guarantee that the view of any query-bounded (possibly malicious) verifier can be efficiently simulated. ZK-IOPs are the main building block of succinct ZK arguments which use the underlying cryptographic object (e.g., a collision-resistant hash function) as a black box.
In this work, we construct the first ZK-IOPs approaching the witness length for a natural NP problem. More specifically, we design constant-query and constant-round IOPs for 3SAT in which the total communication is
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in CRYPTO 2024
- Keywords
- Interactive Oracle ProofsZero-KnowledgeTensor CodesZero-Knowledge CodesSumcheck
- Contact author(s)
-
noga @ cs haifa ac il
mor weiss @ biu ac il - History
- 2024-05-27: approved
- 2024-05-26: received
- See all versions
- Short URL
- https://ia.cr/2024/816
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/816, author = {Noga Ron-Zewi and Mor Weiss}, title = {Zero-knowledge {IOPs} Approaching Witness Length}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/816}, year = {2024}, url = {https://eprint.iacr.org/2024/816} }