CS 647B Advanced Cryptography

Problem set #1

due on __Tuesday Februay 1, 2000__

- 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 c
_{e}lg 1/d times and returns the most frequent answer, for some constant c_{e}depending only on e. Show that a proper choice of c_{e}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. - Let
**QR**be the set of Quadratic Residues modulo n. Give a perfect Zero-Knowledge interactive proof for the language_{n}**QR**._{n} - 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.)
- Let Extended-RSA numbers be positive integers with only two distinct prime factors. Give a perfect Zero-Knowledge interactive proof for the language

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.

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.

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

Hints:

• Extended-RSA numbers have
the form p^{a}q^{b} 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.