Interactive Proofs (Berit)

Readings:

http://en.wikipedia.org/wiki/Zero-knowledge_proof

Sipser 10.4 Interactive proof systems pp. 387-399 skim the proof

Reading questions:

1. Why must Verifier be polynomial-time bounded while the Prover has no computational bound?

2. Why must the Verifier be able to make probabilistic moves?

3. What about interactive proofs allows us to verify languages that are not in NP?

4. Why are zero-knowledge proofs useful?

5. What is co-NP?

Lecture notes:

Zero-Knowledge Proof

-important in cryptography

-prove that statement is true without disclosing further information about the statement

example (stolen shamelessly from wikipedia):

Alice want to show Bob that she knows the secret passage between two tunnels in a cave without sharing the secret. Alice enters one of the tunnels when Bob is outside the cave so that Bob doesn’t know which tunnel she entered. Bob enters the cave and calls out which tunnel he wants Alice to come out of. If Alice knows the secret passage, it doesn’t matter which tunnel Bob calls out. If she doesn’t know the secret passage, she can only come out the right passage half of the time. If Alice and Bob do this many times, every time Alice is correct, the likelihood that Alice doesn’t know the secret passage becomes smaller and smaller, and Bob becomes convinced that Alice knows the secret passage without knowing anything about the secret passage.

Interactive Proof Systems

-NP is the set of languages whose members can be easily checked

e.g. ISO= pairs of isomorphic graphs- certificate is transformation from one graph to the other

-Prover and Verifier

-Prover is not trustworthy, has unbounded computing ability

-Verifier is probabilistic, polynomial time bounded

-for ISO, Prover provides certificate, Verifier checks

-what about complement to ISO, NONISO= pairs of graphs <G1, G2> that are NOT isomorphic? No known certificate, so NONISO is not definitively in NP.

ACTIVITY: How can the Prover convince the Verifier that a pair of graphs is in NONISO?

SOLUTION: Prover provides Verifier <G1, G2>. The verifier randomly selects G1 or G2 and sends an isomorphism H of the graph it selects. The Prover must identify which graph originated H. If G1 and G2 are not isomorphic, the Prover will always be able to do this. If they are, the Prover has no way to tell which graph H came from.

Quiz questions and solutions.

Q: Alice wants to prove to Bob that she has a Hamiltonian path in a particular graph without revealing the path to Bob. How can she do this?

A: Alice generates an isomorphic graph and presents it to Bob. Bob asks Alice to either reveal the transformation from the original graph to the new graph or he asks her to reveal the Hamiltonian path in the new graph. Each time they do this, Alice generates a new isomorphic graph. If Alice is always able to do this, Bob becomes increasingly confident that Alice has a Hamiltonian path.

Homework exercise and solutions.

Implement a simple prover and verifier class in python that will verify the language NON-ISO