# How to perform decryption in this single-bit PKE scheme?

Consider a cyclic group $G$ of order $q$, and let $g$ be a generator for $G$. Assume $(G, q, g)$ is public. Consider the following 1-bit public-key encryption scheme.

To $generate (pk,sk)$:

1. $x \xleftarrow{\$} {1, , 2, . . . , q}$2.$h ← g^x$3.$pk ← h, sk ← x$4. Return$(pk, sk)$To encrypt the message$M = 0$, we define$E_{pk}(0)$as: 1.$y\xleftarrow{\$} {1, 2, . . . , q}$
2. Return $(g^y, h^y)$

To encrypt message $M = 1$, we define $E_{pk}(1)$ as:

1. $y\xleftarrow{\$} {1, 2, . . . , q}$2.$z\xleftarrow{\$} {1, 2, . . . , q}$
3. Return $(g^y, g^z)$

Define $D_{sk}(C)$ and prove that this 1-bit public key encryption scheme is $IND-CPA$ secure if the DDH assumption holds for $(G, g)$. (To be clear, this means doing a reduction.) (Why would no one ever actually use this scheme in practice?)

I haven't been able to come up with proper decryption yet. And I was thinking proving it to be $IND-CPA$ secure would be along the lines of ElGamal security proof. Am I right about it?

And practically, I don't think this is used much because the work involved in 1-bit encryption multiplied across the number of bits in the message would be much larger than the alternative option of using a multiple bit encryption. Am I right about this?

• I would say it is extremely precipitate to ask why a system is not used in practice when not even correctness has been proven. Once you get a way to decrypt the message, you can start wondering if it actually fits the requirements for $IND-CPA$, and only much later if it's practical. – Sergio A. Figueroa Mar 28 '16 at 8:40
• I'd say you'd be right about the efficiency being too low. – Maarten Bodewes Mar 28 '16 at 10:46

To decrypt, you basically take the $g^y$ component and raise it to the secret key, obtaining $g^{yx}$. Now, if this value is equal to the second component of the ciphertext, you can see that $M$ must be 0, since $g^{yx} = h^y$; otherwise, $M$ is 1.