Succinct non-interactive zero-knowledge proofs with preprocessing for LOGSNP

Yael Tauman Kalai, Ran Razt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

Let Λ : {0, 1}n × {0, 1}m → {0, 1} be a Boolean formula of size d, or more generally, an arithmetic circuit of degree d, known to both Alice and Bob, and let y ∈ {0, 1}m be an input known only to Alice. Assume that Alice and Bob interacted in the past in a preamble phase (that is, applied a preamble protocol that depends only on the parameters, and not on Λ, y). We show that Alice can (non-interactively) commit to y, by a message of size poly(m, log d), and later on prove to Bob any N statements of the form Λ(x1, y) = Z1,..., Λ(xN, y) = zN by a (computationally sound) non-interactive zero-knowledge proof of size poly (d, log N). (Note the logarithmic dependence on N). We give many applications and motivations for this result. In particular, assuming that Alice and Bob applied in the past the (poly-logarithmic size) preamble protocol: 1. Given a CNF formula Ψ(w 1,..., wm) of size N, Alice can prove the satisfiability of Ψ by a (computationally sound) non-interactive zero-knowledge proof of size poly(m). That is, the size of the proof depends only on the size of the witness and not on the size of the formula. 2. Given a language L in the class LOGSNP and an input x ∈ {0, 1}n, Alice can prove the membership x ∈ L by a (computationally sound) non-interactive zero-knowledge proof of size polylogn. 3. Alice can commit to a Boolean formula y of size m, by a message of size poly(m), and later on prove to Bob any N statements of the form y{x1) = z1,...,y(xN) = zN by a (computationally sound) non-interactive zero-knowledge proof of size poly(m, log m). Our cryptographic assumptions include the existence of a poly-logarithmic Symmetric-Private-Information-Retrieval (SPIR) scheme, as defined in [4], and the existence of commitment schemes, secure against circuits of size exponential in the security parameter.

Original languageEnglish (US)
Title of host publication47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pages355-366
Number of pages12
DOIs
StatePublished - Dec 1 2006
Externally publishedYes
Event47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, United States
Duration: Oct 21 2006Oct 24 2006

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
CountryUnited States
CityBerkeley, CA
Period10/21/0610/24/06

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Succinct non-interactive zero-knowledge proofs with preprocessing for LOGSNP'. Together they form a unique fingerprint.

  • Cite this

    Kalai, Y. T., & Razt, R. (2006). Succinct non-interactive zero-knowledge proofs with preprocessing for LOGSNP. In 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 (pp. 355-366). [4031371] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2006.74