9
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Have a look on which values $g^b$ can have, and how B can from these derive A's bit. $\endgroup$ Nov 15, 2011 at 22:26
  • $\begingroup$ 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. $\endgroup$
    – Bobby S
    Nov 15, 2011 at 22:33
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 15, 2011 at 22:52
  • $\begingroup$ 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? $\endgroup$
    – Bobby S
    Nov 15, 2011 at 22:58

2 Answers 2

12
$\begingroup$

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'$.

$\endgroup$
1
  • $\begingroup$ if I understand well enough , we choose $m_A = g^a, m_b=g^{a+1}$ . But if $g^a$ is odd then it's lsb is $1$ and therefore to have 1 after the xor with $m_b$ the last bit of $m_b$ should be 0 , shouldn't be? And therefore if $g^a$ is odd , then we should use $g^{a-1}$ for mb $\endgroup$ Jan 9 at 8:13
2
$\begingroup$

@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.).

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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