文章基本信息

标题：An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions
本地全文：下载
作者：Joe Kilian, Erez Petrank
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum, Feldman and Micali \cite{bfm}. Until recently there was a sizable polynomial gap between the most efficient noninteractive proofs for {\sf NP} based on general complexity assumptions \cite{fls} versus those based on specific algebraic assumptions \cite{Da}. Recently, this gap was reduced to a polylogarithmic factor \cite{Ki}; we further reduce the gap to a constant factor. Our proof system relies on the existence of one-way permutations (or trapdoor permutations for bounded provers). Our protocol is based on the random committed bit model introduced by Feige, Lapidot and Shamir. We show how to prove that an n-gate circuit is satisfiable, with error probability 1nO(1) , using only O(nlgn) random committed bits. For this error probability, this result matches to within a constant factor the number of committed bits required by the most efficient known {\em interactive} proof systems.
关键词：complexity, cryptography, non-interactive zero-knowledge, proof systems