CS 647B Advanced Cryptography

Problem set #2

due on Tuesday February 29, 2000

  1. Let Peggy and Piggy be two provers in a scenario where it is possible to physically separate them and guarantee that communication is temporarily impossible between them. Peggy and Piggy can meet before an interaction with Vic and exchange as much information as they wish. However, when they are separated, they cannot exchange any information. Afterwards, they may get back together and exchange information again.

    2. • Design a perfectly concealing bit commitment scheme that allows Peggy or Piggy to commit to bits in a statistically binding way with respect to Vic.

     

  2. Consider the following bit commitment scheme:

    3. • Vic picks a random n=p*q, where p,q are secret large primes.

    • Vic sends n and y, a random quadratic residue mod n.

    • Vic proves to Peggy, in Zero-Knowledge, that y is in QRn.

    • Peggy commits to b as r2yb mod n for a random r.

    • Peggy unveils by disclosing b,r.

    Suppose, Peggy uses these bit commitments to run the zero-knowledge proof we have seen for graph 3-COL. We have argued in class that the resulting protocol is statistical zero-knowledge. Explain why this protocol CANNOT be perfect zero-knowledge.

     

  3. Suppose that you have an arbitrary implementation of Rabin’s Oblivious Transfer from Alice to Bob only. Let OT(b) stand for the Oblivious Transfer transmitting bit b from Alice to Bob with probability 1/2. Let OTk(m) stand for the Oblivious Transfer transmitting message m of abitrary size k bits from Alice to Bob with probability 1/2.

    4. • Show how Alice and Bob can implement OTk(m) given the binary primitive OT as a subroutine.

    • Show how Alice can commit to a bit using OT as a subroutine.

    • Show how Bob can commit to a bit using OT as a subroutine.

    • In each case, count the total number of OTs necessary.

     

  4. Remember Rudich’s trick to construct SUPER-Bit Commitment with Equality given Ordinary Bit Commitment. We have shown that if all the 2n lines of SUPER-BC B0 xor to zero and all the 2n lines of SUPER-BC B1 xor to one then the probability of successfully proving B0=B1 is exponentially small. We now consider the intermediate cases. Let MAJ(B)=0 if at least half the lines of SUPER-BC B xor to zero and MAJ(B)=1 otherwise.

• Show that if MAJ(B0)<>MAJ(B1) then the probability of successfully proving B0=B1 is exponentially small in n.

Let B2 be the SUPER-BC remaining after proving B0=B1.

• Show that if MAJ(B0)=MAJ(B1)=b then the probability that MAJ(B2)<>b and successfully proving B0=B1 is exponentially small in n.

• Conclude that Rudich’s construction is a valid implementation of Bit Commitment with Equality regardless of the Prover‘s behavior.