Perfect Zero-Knowledge Arguments for NP Using any One-Way Permutation.

Moni Naor     Rafail Ostrovsky      Ramarathnam Venkatesan      Moti Yung


``Perfect zero-knowledge arguments'' is a cryptographic primitive which allows one polynomial-time player to convince another polynomial-time player of the validity of an NP statement, without revealing any additional information (in the information-theoretic sense). Here the security achieved is on-line: in order to cheat and validate a false theorem, the prover must break a cryptographic assumption on-line during the conversation, while the verifier cannot find (ever) any information unconditionally. In this paper we show a construction which can be based on any one-way permutation.

The result is obtained by a construction of an information-theoretic secure bit-commitment protocol based on one-way permutations. The computational load on the two parties, the sender and receiver, is low: evaluating the one-way permutation once and around n inner products. The protocol is perfectly hiding for the sender (i.e. even an all powerful receiver gets no information about the bit committed) and computationally binding to the receiver (a polynomial-time bounded sender cannot open the bit in two different ways). Most of the paper is devoted to the description of the bit-commitment scheme and its correctness and security proof.

Paper: Postscript, gzipped Postscript, PDF.

Back to: On-Line PublicationsRecent Papers

Back Home