Welcome to IOU Digital Library

This research paper presents a low-communication two-prover perfect zero-knowledge proof system for the 3-SAT problem, a well-known NP-complete problem. In the proposed protocol, a verifier sends a single query to each prover, where the message length grows only logarithmically with the size of the formula, and each prover responds with a constant number of bits. The protocol guarantees that valid proofs are always accepted, while unsatisfiable instances are rejected with high probability. The work demonstrates how multi-prover interactive proof systems can achieve efficient zero-knowledge proofs for NP languages without relying on strong cryptographic assumptions, highlighting the advantages of multi-prover systems in complexity theory and cryptography.

no reviews

245: $a: Low Communication 2-Prover Zero-Knowledge Proofs for NP (Preliminary Version)
245: $b:
082: $a:
100: $a: Cynthia Dwork, Uri Feige, Joe Kilian, Moni Naor & Muli Safra
650: $a: Computer Science
250: $a:
440: $v:
250: $b: Springer Verlag
250: $c: 1998
020: $a:
300: $a: 13