# ElGamal variant

I came across this problem, while currently reading "Introduction to Modern Cryptography" by Katz and Lindell. I am new to crypto and just trying to go through the book and solve the exercises, unfortunately, got stuck at this one.

Consider the following public-key encryption scheme. The public key is $$(G, q, g, h)$$ and the private key is $$x$$, generated exactly as in the El-Gamal encryption scheme. In order to encrypt a bit b, the sender does the following:

• If $$b = 0$$ then choose a uniform $$y ∈ Z_{q}$$ and compute $$c_{1} := g^{y}$$ and $$c_{2} := h^{y}$$. The ciphertext is $$(c_{1} , c_{2})$$.

• If $$b = 1$$ then choose independent uniform $$y,z ∈ Z_{q}$$ , compute $$c_1 := g^{y}$$ and $$c_{2} := g^{z}$$ , and set the ciphertext equal to $$(c_{1},c_{2})$$.

Show that it is possible to decrypt efficiently given knowledge of $$x$$.

Would appreciate some help

• Hint 1: take $x$-th power of $c_1$. – kelalaka Jan 16 '19 at 19:49
• Thanks, that helped for b=0! Still not sure how to approach for the case b=1 though. – badoo Jan 16 '19 at 20:14
• So you get equality right? – kelalaka Jan 16 '19 at 20:14
• Yes, I do for b=0. – badoo Jan 16 '19 at 20:17
• Then if there is no equality it means? – kelalaka Jan 16 '19 at 20:17

To determine the bit plaintext from $$(c_1,c_2)$$ take $$x$$-th power of the $$c_1$$. There are two options that we don't know

1. $$(c_1,c_2) = (g^y,h^y)$$ then $$(c_1^x,c_2) = (g^{xy},g^{xy})$$
2. $$(c_1,c_2) = (g^y,g^z)$$ then $$(c_1^x,c_2) = (g^{xy},g^{z})$$

Now check whether $$c_1^x = c_2$$ or not.

• If they are equal then than bit $$b=0$$
• If they are not equal than bit $$b=1$$.

There is a small chance that we will have $$g^{xy}=g^{z}$$ as false $$b=0$$. The probability of this event is $$1/g$$.

The cost of operation: if we use Left-to-right binary method for modular exponentiation than the cost is $$\mathcal{O}(\log(x))$$, therefore, it is efficient.

• Note: the question is solved by OP with the hints. – kelalaka Jan 16 '19 at 20:37