SCS Undergraduate Thesis Topics
|Jeremiah Blocki||Manuel Blum||Direct Zero-Knowledge Proofs|
A Zero-Knowledge Proof is an interactive protocol which allows one party (the prover) to prove a statement (S) to another party (the verifier) without revealing anything beyond the truth of S. If S is true then the prover should always be able to convince the verifier that the statement is true without revealing anything else. If S is false then the verifier should be able to catch the prover cheating with high probability. For example, Oded Goldreich found a protocol which allowed the prover to convince a verifier that a graph G is k-colorable without revealing anything else. Consequently, all languages in NP are known to have Zero-Knowledge Proofs because they can be reduced to Graph Coloring. However, there are no known direct Zero-Knowledge Proofs for many NP-Complete languages. I present direct Zero-Knowledge Proof protocols for Subset Sum, Clique, SAT and Integer Programming.