PERFECT ZERO-KNOWLEDGE ARGUMENTS FOR NP USING ANY ONE-WAY PERMUTATION

''Perfect zero-knowledge arguments'' is a cryptographic primitive whic h allows one polynomial-time player to convince another polynomial-tim e player of the validity of an NP statement, without revealing any add itional information (in the information-theoretic sense). Here the sec urity achieved is on-line: in order to cheat and validate a false theo rem, the prover must break a cryptographic assumption on-line during t he conversation, while the verifier cannot find (ever) any information unconditionally. Despite their practical and theoretical importance, it was only known how to implement zero-knowledge arguments based on s pecific algebraic assumptions. In this paper we show a general constru ction which can be based on any one-way permutation. The result is obt ained by a construction of an information-theoretic secure bit-commitm ent protocol. The protocol is efficient (both parties are polynomial t ime) and can be based on any one-way permutation.