CRYPTO LECTURE #17       20-MAR-06       Manuel Blum
          SAMPLE (TOO-HARD) MIDTERM with PARTIAL SOLUTIONS


1. Give a poly(n)-length proof showing, for given n-bit prime p and element g in Zp*, that g is a generator of Zp*.

SOLUTION: Exhibit the complete factorization of p-1. Check its correctness. 
Then show that g^((p-1)/q) mod p <> 1 for all primes q that divide p-1.


2. As in Problem 1, but this time give a 0-knowledge proof of the above, that for given prime p and element g in Zp*, g is a generator of Zp*.  For this problem 2, assume the (simpler) case of an exponentially powerful prover and (the usual) polynomial-time verifier.

SOLUTION 1 (INCOMPLETE but CAN BE COMPLETED): If g is not a generator of Zp*, then it generates a proper subgroup of Zp* containing at most half the elements of Zp*. This suggests the following protocol:
Verifier selects a random "a" in Zp* and asks for an e such that g^e mod p = a.  An exponentially powerful prover can recover e. There is exactly one e iff g is a generator of Zp*.
This protocol is repeated k times for a 1/2^k probability of failure (this is the probability that the prover gets away with cheating).
As it stands, the above protocol is not 0-knowledge because a dishonest verifier could have chosen "a" not according to protocol, and then learned  log base g (a)  from the prover. One way to make this fully 0-knowledge is to have verifier give prover a zero-knowledge proof that she knows e. (How can she do that?)

SOLUTION 2: If g is not a generator of Zp*, then every element of the form g^e mod p has at least two different exponents, e=e1, e2,...  This suggests the following protocol:
Verifier selects a random "e" in Zp-1*, computes a = g^e mod p  and sends "a" to prover.  An exponentially powerful prover can recover e.  For given fixed 1-way permutation, f, prover computes f(e) and gives f(e) to verifier. The verifier can tell if her e is encrypted by f (by computing
f(e) herself).  If not, she rejects.  This protocol is repeated k times for a 1/2^k probability of failure.
This is a proof, since prover would have no way to choose the correct e if there is more than one possibility. This is 0-knowledge because it is
simulatable: Verifier could have generated a junk encryption, f(e), herself.



3. As in Problem 2, give a 0-knowledge proof showing, for given prime p and element g in Zp*, that g is a generator of Zp*.  Do this, however, for the
(harder) case of a poly bdd prover who, however, knows the factorization of p-1. (Note: this is uninteresting if p-1 = 2*q for some prime q. Why?)  It is enormously interesting, however, if p-1=2*q1*q2, where q1 and q2 are large primes, since in that case the verifier, as far as I know, has no way to decide for herself whether or not g is a generator.

SOLUTION: Suppose g is not a generator of Zp*. Then g^x mod p = a has at least two distinct roots if it has any (root). Verifier chooses "e" at random in Zp-1*, say e = 11010, computes a=g^e mod p and gives "a" to prover. If g is NOT a generator, then prover cannot identify which of the two or more possible roots is the one that verifier chose. Prover supplies a root x. (How? Prover cannot compute discrete log by himself. Verifier assists Prover in constructing e (How? Prover reconstructs e with Verifier's help to distinguish principal from non-principal roots)). x must be the root that verifier chose, else prover is cheating. This is repeated k times to reduce probability of cheating to 1/2^k.

Above is 0-knowledge because simulatable: a (even dishonest) verifier could help herself to construct e the way she helps the prover. Another way to make this fully 0-knowledge is to have verifier give prover a zero-knowledge proof that she knows e. (How?)