We have seen nondeterministic algorithms, which allow a prover to convince a verifier of a fact by providing the verifier with evidence.
For example, the prover could convince the verifier that an integer n is composite by providing the verifier with factors of n.
Of course, the evidence is only considered valid if it is of the kind that the verifier expects and the verifier finds it convincing.
Nondeterministic algorithms are a special case of a more general notion of interactive proof.
An interactive proof is a protocol that a prover and verifier use to communicate back and forth. For example, the protocol can indicate that the verifier should ask a question of the prover, and the prover must respond in a particular way.
The verifier is only convinced when the protocol reaches its end without the verifier rejecting the conversation as invalid.
In general, an interactive proof allows for randomness. The protocol can call for the prover or verifier or both to choose random values.
Suppose that an interactive proof protocol is designed to allow a prover P to convince a verifier V that fact F is true. An interactive proof protocol is considered to work provided, for any positive real number ε, there is a parameter k to the protocol so that:
If F is true, and both P and V follow the protocol to its end, then V will be convinced that F is true.
If F is false, then the probability that P convinces V that F is true is no larger than ε, even if the prover breaks the rules of the protocol.
An interactive proof is polynomial-time if the verifier only needs polynomial time in the length of the input (the fact F to be proved). There is no such restriction on the prover.
We will see an example of an interactive proof below.
An interactive proof is zero-knowledge if it does not allow the verifier V to obtain any information from the prover P that V could not have obtained on his or her own, even if the verifier breaks the rules of the protocol.
For example, an interactive proof that a number n is composite would allow V to be convinced that n is composite without learning any information about factors of n or about any way to prove that n is composite.
Let n = pq, where p and q are large prime numbers, and let R be an integer where 0 < R < n and gcd(R, n) = 1.
A prover P says that R is a quadratic residue mod n, and wants to convince V that it is. R is shared by the two of them.
The protocol is to perform the following for k times, where k is the confidence parameter.
P selects a random value x where 0 < x < n and gcd(x, n) = 1. P sends Rx2 mod n to V. V calls the received number y.
V selects, at random, either 0 or 1, each equally likely, and sends the selected value to P.
If V has sent 0 to P then P sends x to V. V computes Rx2 mod n and checks that it is equal to y. V also checks that gcd(x, n) = 1.
If V has sent 1 to P then P sends sx to V, where s is a square root of R. V calls the received value z, and checks that y ≡ z2 (mod n).
V accepts the interactive proof if every one of the k rounds leads to correct checks.
But why does that work? Why is it zero-knowledge?
First, look at it from V 's perspective.
V sends 0 to P in step 2 half of the time. If P cheated, then with high probability, P would get caught, unable to respond with the value of x.
So, V concludes that, in at least one of the rounds where V sends 1 to P in step 2, y ≡ Rx2 (mod n) for some x that P knows.
Now look at a time when V sends 1 in step 2. Because of (1), V believes that
But P sends a value z to V such that z2 ≡ y ≡ Rx2 (mod n), because V checked that.
Let u be the inverse of x (mod n). Multiplying both sides of the above congruence by u2 gives
Now look at it from P's perspective.
In one scenario, where V sends 0 in step 2, V has received x and y ≡ Rx2 (mod n), where x is chosen at random among all values such that gcd(x, n) = 1.
But V did not need any help to get that information. V could choose a random x and compute y = Rx2 mod n. So V has received no information from P in this case.
In the other scenario, where V sends 1 in step 2, V has received z = sx and y ≡ Rx2 ≡ z2 (mod n).
But, because x was chosen at random, sx is also chosen at random. V can choose a random z and compute z2 mod n without any help from P. Once again, V has received no information.
(To see that z is effectively chosen at random, it suffices to show that each number that is relatively prime to n can be chosen as z. Any desired z can be expressed as sx by choosing x = zs−1.)
Passwords have a shortcoming; you need to send them. Someone might intercept them.
Suppose A wants to log into computer B. A password is set up by randomly choosing primes p and q, and randomly choosing s where 0 < s < n and gcd(s, n) = 1. Only A knows s.
B verifies A's password by asking A to act as a prover to show that R = s2 mod n is a quadratic residue.
So instead of sending a password to B, A engages in a zero-knowledge proof with verifier B.
An eavesdropper can see the conversation, but cannot received any information that allows him or her to pretend to be A.
We know that A does not reveal any information about s. But our belief that an eavesdropper cannot compute s without help requires the conjecture that factoring is not solvable in (random) polynomial time.