Minimum resource zero knowledge proofs

Abstract

Several resources relating to zero-knowledge protocols are considered. They are the number of envelopes used in the protocol, the number of oblivious transfer protocols executed during the protocol, and the total amount of communication required by the protocol. It is shown that after a preprocessing stage consisting of O(k) executions of oblivious transfer, any polynomial number of NP-theorems of any polysize can be proved noninteractively and in zero knowledge, on the basis of the existence of any one-way function, so that the probability of accepting a false theorem is less than 1/2/sup k/.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>