1992 | OriginalPaper | Chapter
A One-Round, Two-Prover, Zero-Knowledge Protocol for NP
Authors : Dror Lapidot, Adi Shamir
Published in: Advances in Cryptology — CRYPTO ’91
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The model of zero knowledge multi prover interactive proofs was introduced by Ben-Or, Goldwasser, Kilian and Wigderson. A major open problem associated with these protocols is whether they can be executed in parallel. A positive answer was claimed by Fortnow, Rompel and Sipser, but its proof was later shown to be flawed by Fortnow who demonstrated that the probability of cheating in n independent parallel rounds can be exponentially higher than the probability of cheating in n independent sequential rounds. In this paper we use refined combinatorial arguments to settle this problem by proving that the probability of cheating in a parallelized BGKW protocol is at most 1/2n/9, and thus every problem in NP has a one-round two prover protocol which is perfectly zero knowledge under no cryptographic assumptions.