A problem about Crypotography: Consider the following protocol for two parties A

Question

A problem about Crypotography:

Consider the following protocol for two parties Alice and Bob to flip a fair coin (more complicated versions of this might be used for Internet gambling): A trusted party T publishes her public key p_k. Alice chooses a random bit b_A leftarrow^random {0, 1} encrypts it using p_k, and sends the cyphertext c_A to Bob and T. Bob chooses a random bit b_B leftarrow^random {0, 1} encrypts it using p_k, sends the cyphertext e_B notequalto c_A to Alice and T. T decrypts both c_A and c_B. and the parties XOR the results to obtain the value of the coin. A Argue that even if Alice is dishonest (but Bob is honest), the final value of the coin is uniformly random^1 Assume the parties use Megamall encryption (where the bit b Element {0, 1} is encoded as the group element g^b). Show how a dishonest Bob can bias the coin to any value he likes. the protocol shows that for any fixed bit b Element {0, 1} and if b' leftarrow^random {0, 1} is randomly picked then b b' is also random bit.

Explanation / Answer

A. If Alice is dishonest, fair certified e-mail (CEM)  would not be an Fair exchange at all, upon learning M, Alice may never return SIGB(M), thus forever depriving Bob of her receipt. Similarly, Honest ECS ( Electronic Contract Signing) is not a Fair ECS protocol at all if Alice is dishonest: upon receiving Bob's digital signature, Alice may not reciprocate, thus seriously damaging Bob. No purely-two-party protocol is a Fair exchange if one of the two participants is malicious. So, the final value of coin is uniformly random. As Alice is dishonest it has no advantage however following the rules of the protocol and honest Bob will always produce a different cipher text.

B. Alice chooses random bit a, and a random integer k modulo q, and announces cA=(gk,gayk). The second half of that encrypted message is equal to gx.k+a. Bob sees these values.

To bias towards 0, Bob can simply send the exact same value (cB=cA). Bob does not know the value of the bit from Alice, but he knows that by sending the same value, he forces the final XOR to be a 0. To make the manipulation less obvious, Bob can choose a random integer f modulo q and send:

cB=(gkgf,(gayk)yf)

If you expand these equations, you will see that cB=(gk',gayk') where k=k+f. Bob knows neither a or k, but he sends a valid ciphertext for the same value a, and with a uniformly chosen random f this cannot even be detected. This is how Bob biases the coin to 0 with 100% success rate.

To bias towards 1, the construction is a bit more complex. Bob computes this:

cB=((gk)q-1gf,(gayk)q-1yfg)

for a random f modulo q. If you expand this equation, you will see that cB is a valid ElGamal encryption of

ga(q-1)+1. Since g has order q, cB is thus the encryption of g1 if a=0, and g0 if a=1. Thus, Bob always sends the bit opposite of the bit from Alice, guaranteeing a coin toss of 1. Furthermore, the random f makes sure that the manipulation is not detectable.

Generally speaking, this exploits the homomorphic property of ElGamal: given the encryptions of m and m, one can compute a valid encryption for mm, without knowing m or m.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.