Efficient Batch Verification in Statistical Zero-Knowledge
Learn about the concept of doubly efficient batch verification in statistical zero-knowledge protocols, including motivating examples, zero-knowledge proofs, SZK, possible solutions, and batch proofs. Explore the latest advances in cryptographic protocols for verifying large sets of data efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Doubly-Efficient Batch Verification in Statistical Zero-Knowledge Or Keret Technion Ron D. Rothblum Technion Prashant N. Vasudevan NUS 1
A Motivating Example A prover holding a long list of RSA public-keys wants to convince a verifier that the public-keys are well formed ?1, ,?? ?1 ?1 ?1,?1, ,??,?? 2
Zero-Knowledge Proofs [GMR82] A zero-knowledge proof is an interactive protocol between a prover and a verifier Completeness: Statement is correct verifier accepts w.h.p. Soundness: Statement is incorrect verifier rejects w.h.p. when interacting with prover Zero-Knowledge: For every PPT verifier there exists a PPT simulator with an output distribution from real interactions of the honest prover with the verifier any indistinguishable 3
SZK (Statistical Zero-Knowledge) The class of all promise problems that have statistically sound and statistically zero-knowledge proofs A central class capturing many problems in cryptography Has a rich structure that was extensively studied, e.g., [Vad99] NO = \??? YES = ?:? = ??,?,? PRIMES 4
Possible Solutions [GMR98] Non-interactive statistical zero-knowledge proof (NISZK) for verifying that a number is a valid RSA public-key ? = ?? $ $ ? 0,1? ? ? 5
Possible Solutions ZK and soundness are statistical Poly-time prover strategy given the prime factors ?1, ,?? $ 0,1?? ? ?1, ,?? 6
Possible Solutions Existing efficient zero-knowledge proofs, e.g., [Kil92] Computational soundness or computational zero-knowledge 7
ZK Batch Proofs [KRR+20, KRV21,MNRV24] NISZK proof for verifying ? instances with communication poly(?,log?) for all of NISZK ?1, ,?? $ 0,1? ? ? Exponential-time prover 8
Doubly-Efficient Batch Proofs [RRR16, RRR18, RR20] Doubly-efficient interactive proof for verifying ? instances with communication poly(?,log?) for all of UP Not ZK Hopefully, [RRRRRRRR26] will achieve ?(1) communication complexity NO = \??? ?1, ,?? YES = ?:? = ??,?,? PRIMES 9
Our Result A new protocol [RR20] [MNRV24] Batching for UP NISZK Doubly-efficient SZK Batching for UP Doubly-efficient Not ZK Batching for NISZK SZK Not doubly-efficient 10
Our Result Main Theorem: Every problem UP NISZK has a public-coin SZK protocol for verifying ? instances ?1, ,??, each of length ?, with the following parameters: Communication complexity: poly(?,log?) Number of rounds: polylog(?,?) Verifier runtime: ? ? poly(?) The honest prover, given also the ? unique witnesses, runs in time poly(?,?) 11
Our Result Unconditional result Information-theoretic security guarantees Applications include prime products, quadratic residuosity and variants thereof 12
Upsides of Information-Theoretic Security Paranoia Less assumptions (==less paranoia) Potential for better efficiency Furthers our understanding of (NI)SZK 13
Our Starting Point - The [RR20] UP Batch Proof ?1, ,?? ?1, ,?? {??} 14
From Public Coin to ZK ?1, ,?? ?1, ,?? 15
From Public Coin to ZK ?1, ,?? ?1, ,?? 16
Preserving the Communication Complexity The communication complexity of the commitments We reduce the [MNRV24] proof to efficient (instance- dependent) commitments The communication complexity of the ZKP Using the [IKOS07] MPC-in-the-head paradigm 17
Questions? 18
