Proof — Goldreich–Micali–Wigderson zero-knowledge proof
Statement
Every language in NP has a zero-knowledge proof system, assuming one-way functions exist. A zero-knowledge proof convinces a verifier that a statement is true without revealing any information beyond that fact. The proof transforms any NP-proof into an interactive zero-knowledge protocol using commitment schemes.
Formula
∀L ∈ NP: L has ZK proof
Equation
NP ⊆ ZK (assuming OWF)
Proof sketch
Goldreich, Micali, and Wigderson showed how to compile any NP witness into a zero-knowledge interactive proof. The prover commits to the witness using a bit-commitment scheme (from one-way functions), then reveals information in a way that is simulatable by the verifier alone. The protocol for Graph Isomorphism and the reduction from SAT (via NP-completeness) establish the result for all of NP.
Source
Goldreich, Micali, Wigderson, Proofs that yield nothing but their validity, FOCS 1986; JACM 1991.
Domains
mathematics, computer-science, cryptography
People
Related
- Theorem: Goldreich–Micali–Wigderson zero-knowledge proof
- Proof: Goldreich–Micali–Wigderson zero-knowledge proof