CS 647B Advanced Cryptography

Problem set #1

due on Tuesday Februay 1, 2000



  1. Let e and d be two positive real numbers such that d<e<1/2. Let [P,V](x) be an interactive proof of membership of x to language L such that V’s error probability is no more than e. Let x be an instance to be proven. Consider the interactive proof that calls [P,V](x) at least ce lg 1/d times and returns the most frequent answer, for some constant ce depending only on e. Show that a proper choice of ce yields a resulting interactive proof with error probability no more than d. Conclude that if we want d=2-|x| it is sufficient to repeat only poly(|x|) times [P,V](x) and take the most frequent answer.
  2. For the next three problems, I do not expect a formal proof of the zero-knowledge property, but I want at least some explanation as why it should be ZK.

  3. Let QRn be the set of Quadratic Residues modulo n. Give a perfect Zero-Knowledge interactive proof for the language QRn.
  4. Give a computational Zero-Knowledge interactive proof for the Hamiltonian circuit problem. (A graph G is Hamiltonian if its edges contain a circuit visiting each vertex exactly once.)
  5. Notes: This result follows from the fact that 3-COL has a CZK interactive proof, however I want you to solve this problem from scratch. It is simpler than 3-COL... I removed the condition that the graph be directed.

  6. Let Extended-RSA numbers be positive integers with only two distinct prime factors. Give a perfect Zero-Knowledge interactive proof for the language

{ [n,y] : n is an Extended-RSA number and y in QNRn[+1] }.


• Extended-RSA numbers have the form paqb for any odd primes p,q and positive integers a,b.

• use question 2. (even if you have not solved it).

• use (without proof) the fact that if n (which is not a square) has exactly k+1 distinct prime factors then exactly 2-k of the integers modulo n with Jacobi symbol +1 are quadratic residues modulo n.