We construct a (computationally sound) non-interactive zero-knowledge proof, where the size of the proof is polynomial in the size of the *witness* (which may be much smaller than the instance). Our proof requires an interactive preprocessing phase, that does not depend on the instance (other than being poly-logarithmic in the instance size). For example, we show:
(1) Given a CNF formula Psi(w_1,...,w_n) of size N >> n, Alice can prove the satisfiability of Psi by a (computationally sound)
non-interactive zero-knowledge proof of size poly(n).
(2) Given a language L in the class LOGSNP (such as LOG-CLIQUE) and an input x in {0,1}^N, Alice can prove the membership x \in L by a
(computationally sound) non-interactive zero-knowledge proof of size polylog(N).
(3) Alice can commit to a Boolean formula F of size n, by a message of size poly(n), and later on prove to Bob any N statements of the
form F(x_1)=z_1,...,F(x_N)=z_N by a (computationally sound) non-interactive zero-knowledge proof of size poly(n,log N).
Our cryptographic assumptions include the existence of a poly-logarithmic Symmetric-Private-Information-Retrieval (SPIR)
scheme, and the existence of commitment schemes that are secure against circuits of size exponential in the security parameter.
This is joint work with Ran Raz.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.