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 Vs 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.
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.
- Let QRn be the set of Quadratic Residues modulo n. Give a perfect Zero-Knowledge interactive proof for the language QRn.
- 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.)
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.
- 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] }.
Hints:
Extended-RSA numbers have
the form p
aqb 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.