**
Perfect Zero-Knowledge Arguments for NP Can Be Based on General
Complexity Assumptions.
**

*
Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung.
*

**
Abstract:
**
``Zero-knowledge arguments'' is a fundamental 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. Despite their practical and theoretical importance, it was
only known how to implement zero-knowledge arguments based on specific
algebraic assumptions; basing them on a general complexity assumption
was open since their introduction in 1986. In this paper, we finally
show a general construction, which can be based on * any* one-way
permutation.
We stress that our scheme is * efficient*: both players can execute
only polynomial-time programs during the protocol. Moreover, the
security achieved by arguments 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
can not find (ever!) any information unconditionally (in the
information theoretic sense).

**comment:**
Preliminary version appeared in Proceedings of advances in cryptology
(CRYPTO-92) Springer-Verlag Lecture Notes in Computer Science.
Final version Appeared in J. of Cryptology, 1998.

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |