CS-235. Problem Set 8


  1. In the Fiat-Shamir protocol, what happens if
    1. Verifier uses predictable coins?
    2. Prover uses predictable coins? (e.g. does not change coins)
  2. a) My Public Key for Rabin Encryption is n=45173. You sneak into my office and compute square root of 4 is 32236. Factor n.
    b) Suppose now that a random error was induced in an unknown step of square root of 1 mod 32236 computation that outputs 399 (assume the standard square root algorithm discussed in class and the error is likely to occur in the sections of the algorithm that take longer). Is it possible for you as a hacker to factor n?  If yes, do it.
  3. Ex.13.5
  4. Extra credit:  Ex. 13.7
  5. Ex. 13.11 (you can use the algorithm we used in class - it is essentially the same)