The Taub Faculty of Computer Science Events and Talks

A statistical zero-knowledge proof for a problem Pi enables a computationally unbounded prover to convince a polynomial-time verifier that x belongs to Pi without revealing any additional information about x to the verifier, in a strong information-theoretic sense. Suppose, however, that the prover wishes to convince the verifier that k separate inputs x_1,...,x_k all belong to Pi (without revealing anything else). A naive way of doing so is to simply run the SZK protocol separately for each input. In this thesis we ask whether it is possible to do so with significantly shorter communication, and show that this is indeed the case for a large subclass of problems in SZK.