Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

An old exam question I am trying to figure out:

Consider the following protocol for two parties to flip a fair coin.

  • Trusted party T publishes her public key pk
  • A chooses a random bit $b_A$, encrypts it under pk, and announces the ciphertext $c_A$ to B and T
  • B does the same and announces a ciphertext $c_B$
  • T decrypts $c_A$ and $c_B$, and announces the results. Both parties XOR the results to obtain the random value $b_A \oplus b_B$.

(a) Argue that even if A is dishonest (but B is honest) the final value of the coin is uniformly distributed.

(b) Assuming that T uses ElGamal (where bit $b$ is encoded as $g^b$ before encryption), show that a dishonest B can bias the coin to any value he likes.

I can figure out a, but I am having trouble with b.

share|improve this question
    
Have a look on which values $g^b$ can have, and how B can from these derive A's bit. –  Paŭlo Ebermann Nov 15 '11 at 22:26
    
Yeah, I think I have it figured out. Thanks for the help. g^b can be 1 or g. If it's 1, then A chose 0, if it's g, then A chose 1. –  Bobby S Nov 15 '11 at 22:33
1  
This encoding of $b$ by $g^b$ is not Elgamal encryption, but this might be the encoding step to derive $m$ from $b$ before actually encrypting. –  Paŭlo Ebermann Nov 15 '11 at 22:52
    
Oh right, so my comment is incorrect. Does the same sort of principle stand that if b = 0 then m = 1 and if b = 1, then m = g. If B knows that information, how can he use it to bias the value of the coin? –  Bobby S Nov 15 '11 at 22:58

2 Answers 2

up vote 8 down vote accepted

ElGamal encryption works like this:

  • We work in a cyclic group $G$ of order $q$ (a prime integer), with $g$ being a generator. Here, we note the operation multiplicatively. For instance, we work with integers modulo $p$ (a big prime such that $q$ divides $p-1$) and $g$ is one of the $q$-th roots of $1$ modulo $p$.

  • Private key is $x$, an integer modulo $q$.

  • Public key is $y = g^x$ (i.e. $g^x \mod p$ if we use integers).

A chooses random bit $a$, and a random integer $k$ modulo $q$, and announces $c_A = (g^k, g^a·y^k)$ (encryption of $g^a$ with ElGamal). The second half of that encrypted message is equal to $g^{x·k+a}$. B sees these values.

To bias towards 0, B can simply send the exact same value ($c_B = c_A$). B does not know the value of the bit from A, but he knows that by sending the same value, he forces the final XOR to be a 0. To make the manipulation less obvious, B can choose a random integer $f$ modulo $q$ and send: $$c_B = (g^k·g^f, (g^a·y^k)·y^f)$$ (i.e. values computed from those sent by A). If you expand these equations, you will see that $c_B = (g^{k'}, g^a·y^{k'})$ where $k' = k+f$. B 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 B biases the coin to 0 with 100% success rate.

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

$$ c_B = ((g^k)^{q-1}·g^f, (g^a·y^k)^{q-1}·y^f·g) $$

for a random $f$ modulo $q$. If you expand this equation, you will see that $c_B$ is a valid ElGamal encryption of $g^{a·(q-1)+1}$. Since $g$ has order $q$, $c_B$ is thus the encryption of $g^1$ if $a = 0$, and $g^0$ if $a = 1$. Thus, B always sends the bit opposite of the bit from A, 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 $m·m'$, without knowing $m$ or $m'$.

share|improve this answer
    
Wow, thanks. That makes perfect sense. What a beautiful answer. –  Bobby S Nov 15 '11 at 23:30

@Thomas has a great answer and I don't want to detract from it. However I wanted to better highlight how, as he notes, you are just exploiting the homomorphism of Elgamal.

The variant of Elgamal with the message in the exponent is often called exponential Elgamal [CGS]. It is additively homomorphic which means two things:

  • $\mathsf{Enc}(x)\cdot\mathsf{Enc}(y)=\mathsf{Enc}(x+y)$
  • $\mathsf{Enc}(x)^a=\mathsf{Enc}(a\cdot x)$

This is a slight abuse of notation since Elgamal ciphertexts are a pair of values, but it just means component-wise multiplication/exponentiation.

Given $\mathsf{Enc}(b)$ where $b=\{0,1\}$, one can either perserve the bit or flip it [Neff] as follows:

  • Preserve: $\mathsf{Enc}(b)\cdot\mathsf{Enc}(0)=\mathsf{Enc}(b+0)=\mathsf{Enc}(b)$
  • Flip: $\mathsf{Enc}(b)^{-1}\cdot\mathsf{Enc}(1)=\mathsf{Enc}(b(-1)+1)=\mathsf{Enc}(1-b)$

In both cases, in addition to perserving/flipping, the ciphertext is rerandomized and indistinguishable from the original. This can be done by anyone, without knowing the value of $b$ (e.g., by Bob using Alice's encrypted bit in the exam question).

By abstracting away the details of Elgamal, you can see how it can be applied to any additively homomorphic encryption (e.g., Paillier, BGN, lattice-variants of BGN, etc.).

share|improve this answer
    
I should add to be careful using exponential Elgamal: decryption involves solving a discrete log, so the message space must be small. Paillier, while less efficient, allows decryption of messages of any size. –  PulpSpy Nov 16 '11 at 16:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.