The Taub Faculty of Computer Science Events and Talks

Abstract: Zero-knowledge proofs enable a prover to convince a verifier of the truth of a statement without revealing anything else. Non-interactive zero-knowledge proof are zero-knowledge proofs where the prover constructs the proof without interaction with the verifier.

In a probabilistically checkable proofs the verifier only needs to read a small number of bits to be convinced that the statement to be proven is true with high probability. PCPs have been used to reduce the communication complexity of interactive zero-knowledge proofs by letting the verifier check a small number of bits of a prover's committed PCP. In this talk we show that efficient PCPs can also be used to reduce the communication complexity in non-interactive zero-knowledge proofs even though in this setting the verifier does not interact with the prover.

Our non-interactive zero-knowledge proofs are constructed in the so-called hidden random bit model where the prover has a set of random bits and reveals some of them to the verifier. We will show that using Naccache-Stern encryption we can instantiate the hidden random bit model with only a logarithmic overhead. Combining with the PCP technique this yields non-interactive zero-knowledge proofs that have quasi-linear communication complexity.