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

TitlePerfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions
Publication TypeTechnical Report
Year of Publication1992
AuthorsNaor, M., Ostrovsky R., Venkatesan R., & Yung M.
Other Numbers787
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 [BCC, BC, CH]. 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 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).

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1992/tr-92-082.pdf
Bibliographic Notes

ICSI Technical Report TR-92-082

Abbreviated Authors

M. Naor, R. Ostrovsky, Ramarathnam Venkatesan and Moti Yung

ICSI Publication Type

Technical Report