1993 | OriginalPaper | Buchkapitel
Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions
Extended Abstract
verfasst von : Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung
Erschienen in: Advances in Cryptology — CRYPTO’ 92
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
“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).