CS 647B Advanced Cryptography
Problem set #1
due on Tuesday Februay 1, 2000
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 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.