Rafail Ostrovsky - Publications

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