Publication Details
Title: Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions
Author: M. Naor and R. Ostrovsky
Group: ICSI Technical Reports
Date: December 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-082.pdf
Overview:
"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).
Bibliographic Information:
ICSI Technical Report TR-92-082
Bibliographic Reference:
M. Naor and R. Ostrovsky. Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions. ICSI Technical Report TR-92-082, December 1992
Author: M. Naor and R. Ostrovsky
Group: ICSI Technical Reports
Date: December 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-082.pdf
Overview:
"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).
Bibliographic Information:
ICSI Technical Report TR-92-082
Bibliographic Reference:
M. Naor and R. Ostrovsky. Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions. ICSI Technical Report TR-92-082, December 1992