🌠 Motivation
In the world of mathematical logic, the most rigorous and formal proof is a deduction where each line is either an assumption, an instance of an axiom scheme, or a result of applying some inference rules on previous lines depending on the given logic language.
But, normally (& luckily ✨), writing a proof does not require such formality, and the word proof in our daily life requires some form of evidence being passed on from the person who wishes to prove something (the prover) to the person who verifies the evidence (the verifier). The verifier can ask for additional evidence if not convinced.
In short, a proof can be defined as an interaction between two sides.
📕 Basic Definitions
Before diving into how Interactive Proof works with a concrete example and why it is so useful, we first explore the basic machinery needed for learning this topic rigorously.
First, we have Mr.Prover and Mr.Verifier, with the verifier asking questions and the prover responding, and at the end, the verifier can either accept or reject. However, there’s something special about our Mr.Verifier.
🙅 Mr. Verifier is NOT perfect! We allow him to be wrong.
To put it formally, our verifier is probabilistic, and it can be wrong with a small probability. Furthermore, we can regard our verifier and prover as functions (just as everything else in life), and since our verifier is probabilistic, our final output (whether the verifier accepts or not) is a random variable.
To further simply the situation, essentially Mr. Prover comes up with a proof (the answers to Mr. Verifier’s questions), and Mr. Verifier has a final say in if he believed the prover or not, which can be a ❎ false conclusion.
Now we finally introduce the formal definition of the complexity class IP:
📗 Defintion:
A language L is in IP if there is a Turing Machine V such that on inputs x, V runs in polynomial time p with respect to the length of x, i.e. |x|, such that
- (Completeness) x ∈ L ⇒ ∃ P Pr[outᵥ⟨ P, V ⟩(x)=1] =1.
- (Soundness) x ∉ L ⇒ ∀ P Pr[outᵥ ⟨ P, V ⟩(x)=1] ≤ 1/2
Note that here we chose the arbitrary Turing Machine’s name to be V, which is intentional since it is our Verifier.
🔈 To say it in plain English, a language is in the class IP if:
- If the input x we are looking at is in L, then there exists some polynomial length proof such that the Verifier will confirm x’s membership.
- If the input x we are looking at is not in L, then for any possible proof out there, the Verifier rejects x with a probability of at least 1/2.
We can further increase the correctness probability by using the boosting technique of independent repeated trials and returning the majority answer.
📩 Long story short:
- Proof can be an interaction between a Prover and a Verifier.
- If we allow the Verifier to be probabilistic, we have a high chance of solving NP hard problems correctly.
🏃 I.P. In Action: Graph Isomorphism
Now we step through a classic example that demonstrates the power of I.P..
First, we introduce the definition of having graphs being isomorphic.
We say that two graphs (G₁, G₂) are isomorphic if there is a permutation π of the vertices V such that π(G₁)=G₂. To put it it more plainly, if we can rename/recolor the vertices and get the other graph, then they are isomorphic. If G₁, G₂ are isomorphic, we write that G₁ ≡ G₂.
The problem of determining whether if 2 graphs are isomorphic is in the complexity class NP since a valid polynomial length certificate would simply be the description of the permutation/renaming/recoloring π.
The protocol we use in the I.P. strategy for Graph Isomorphism:
- Verifier: Pick i ∈ {1, 2} uniformly at random. Then randomly permute the vertices of the chosen Gᵢ to get the nw graph H. Send H to P.
- Prover: Identify which of G₁, G₂ was used to produce H. Let that graph be Gⱼ, and send the vertex j to the Verifier.
- Verifier: accept if i = j; reject otherwise.
🌱 Correctness Proof:
Now we show that this is a valid Interactive Proof protocol as defined above. First, for Completeness, if G₁≢ G₂, then there must be a prover such that Pr[V accepts] = 1 since if the graphs are non-isomorphic, a powerful prover can recognize which one of the two is isomorphic to H. Second, for Soundness, if G₁ ≡ G₂, then the prover can only guess since a random permutation of G₁ will be the same as the random permutation of G₂. Therefore for all prover out there, Pr[V accepts] ≤ 1/2.
🔖 Zero Knowledge Proofs
A natural next step in studying Interactive Proof related topics would be the Zero-Knowledge Proof. The intuition is that an interactive proof is zero-knowledge if after reading the proof sent by the Prover, our Verifier cannot efficiently perform computational tasks that she could not efficiently perform before. Zero-knowledge is a property that could be desirable for a prover that suspects a malicious verifier.
The prover wants the convince the verifier that he indeed has the correct answer without revealing any part of his answer.
📗 Defintion:
Given an interactive proof system ⟨ P, V ⟩ for a language L and an input x, we define the view of V on x to be all messages sent from P to V as well as all the random bits used by V during the protocol. We write the view on x as
Viewᵥ [P(x) ↔ V(x)]
An interactive proof system ⟨ P, V ⟩ for a language L is zero-knowledge if for any poly-time Turing Machine Verifier V there exists an expected probabilistic poly-time Turing Machine S such that,
∀ x ∈ L, z ∈ {0, 1}*, Viewᵥ [P(x) ↔ V(x, z)] = S(x, z)
As usual, our Prover P is a randomized TM and has unlimited computation power. The intuition here is that an interactive proof system is zero-knowledge if for any verifier V we have, we can find an efficient simulator S that produces a transcript of the conversation that would have taken place between P and V on any given input x. Therefore, even if V had the conversation with P, V will not be able to compute something she could not have computed before the conversation.
The string z here represents “prior knowledge”. It means that V cannot use any prior knowledge to mine information out of its conversation with P since we give the same prior knowledge to our simulator S. Transparency is nice! 🎐
Now we give a zero-knowledge proof system for the same question we explored above with ordinary interactive proof, graph isomorphism.
We take in 2 graphs (G₀, G₁):
🌱 Correctness Proof: For Soundness, there is at most 1/2 chance that we get b=b’, and that’s the only case where if G₁ and G₂ are not isomorphic but we would still have the equivalence to hold on the last line. For completeness, if G₁ ≡ G₂, then the last line will always hold. Therefore the protocol shown above is a valid I.P. system.
Now we show that it is indeed zero-knowledge. We first assume that all the random picking are indeed honest. By definition, we want the following claim to hold ∀ x ∈ L, z ∈ {0, 1}*, Viewᵥ [P(x) ↔ V(x, z)] = S(x, z). We will prove this by defining a simulator S for an arbitrary verifier V.
We define S(G₀, G₁, z) as follows,
- Randomly choose a permutation σ and b ∈ {0, 1}.
- Set H = σ(G_b) and b’ = h*(G₀, G₁, z, H).
- If b’=b, output (b’, H, σ), otherwise restart with a new σ, b.
Now we show that S is indeed a valid simulator by showing if G₀ ≡ G₁, then (a) S runs in poly-time and (b) Viewᵥ [P(x) ↔ V(x, z)] = S(x, z).
For (a), if we have G₀ ≡ G₁, then we have σ is random, therefore b’ and b are chosen independently thus having probability of 1/2 to be equal. Thus S must run only twice before halting. For (b), the fact that Prob[b=b’]=1/2 guarantees that the distribution of S is indeed the same as Viewᵥ.
📚Conclusion
There are immense power to combing interactivity and randomness with certificates for NP problems, and the fact that we can boost up correctness possibility through repeated trials gives us greater hope in returning the correct answer. Furthermore, the fact that we can convey that we have a valid result without revealing any piece of it is quite fascinating. ✨
📖 References
- [interactive proof] https://www.cs.princeton.edu/courses/archive/spring06/cos522/ip.pdf
- [interactive proof] https://www.anilada.com/courses/15251f18/www/slides/lec26slides.pdf
- [zero-knowledge proof] https://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture18.pdf
