CS-235. Problem Set 11


  1. Prove Theorem 9.2 and that if 0R = 1R then R={0R}.
  2. Ex.9.1
  3. Ex.9.2
  4. Extra Credit: Ex. 9.3
  5. Ex. 9.4
  6. In the Schnorr's protocol, what happens if
    1. Verifier uses predictable coins?
    2. Prover uses predictable coins? (e.g. does not change coins)
  7. In principle, Diffie-Hellman and Schnorr protocols can be defined for any group, not just Zp*
    Describe how these protocols would look if Zp+ were used instead. Is it a good idea to use this group? Why or why not (be very specific and formal)
    How about Zn*  for some n=pq for two large primes p,q?
    [in fact, in cryptography we do commonly use groups other than Zp* - they are defined using elliptic curves]