Random Coin Flip using ElGamal and a Trusted Party 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.
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&#183;y^k)$ (encryption of $g^a$ with ElGamal). The second half of that encrypted message is equal to $g^{x&#183;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&#183;g^f, (g^a&#183;y^k)&#183;y^f)$$ (i.e. values computed from those sent by A). If you expand these equations, you will see that $c_B = (g^{k&#39;}, g^a&#183;y^{k&#39;})$ where $k&#39; = 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}&#183;g^f, (g^a&#183;y^k)^{q-1}&#183;y^f&#183;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&#183;(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&#39;$, one can compute a valid encryption for $m&#183;m&#39;$, without knowing $m$ or $m&#39;$.