CS 647B Advanced Cryptography

Problem set #2

due on __Tuesday February 29, 2000__

- 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.
- Consider the following bit commitment scheme:
- Suppose that you have an arbitrary implementation of Rabin’s Oblivious Transfer from Alice to Bob
. Let__only__**OT(b)**stand for the Oblivious Transfer transmitting bit**b**from Alice to Bob with probability 1/2. Let**OT**stand for the Oblivious Transfer transmitting message_{k}(m)**m**of abitrary size**k**bits from Alice to Bob with probability 1/2. - 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**B**xor to_{0}**zero**and all the**2n**lines of SUPER-BC**B**xor to_{1}**one**then the probability of successfully proving**B**is exponentially small. We now consider the intermediate cases. Let_{0}=B_{1}**MAJ(B)=0**if at least half the lines of SUPER-BC**B**xor to**zero**and**MAJ(B)=1**otherwise.

• 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.

• 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 **QR _{n}**.

• Peggy __commits__ to **b** as **r ^{2}y^{b} mod n** for a random

• 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.

• Show how Alice and Bob can implement **OT _{k}(m)** given the binary primitive

• 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 **OT**s necessary.

• Show that if **MAJ(B _{0})<>MAJ(B_{1})** then the probability of successfully proving

Let **B _{2}** be the SUPER-BC remaining after proving

• Show that if **MAJ(B _{0})=MAJ(B_{1})=b** then the probability that

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