Homework 11, due Monday April 18

  • Rework the socialist millionaire algorithm (Wiki summary), adapting it to work for elliptic curves.
  • Show how solving the discrete log problem leads to a successful attack on the socialist millionaire problem.
  • Instead of using the socialist millionaire algorithm, why couldn’t Alice (with net worth x) and Bob (with net worth y) get the same effect by simply sending each other the hashes (H(x) and H(y)) of their net worths?
  • Use the Blum-Micali algorithm to generate a 10-bit pseudo-random sequence starting with the prime number p=7919, generator g=7, and initial seed x0=5.
  • Team up with another member of the class or a friend and go through the steps together for a few rounds of the zero knowledge proof of the 3-colorability of the Peterson graph.  For the homework writeup, write a few sentences about the activity.
  • In this online interactive demo the zero-knowledge proof of 3-colorability is not at all convincing (at least for me).  Why not? Can you think of how to make it more convincing?