# 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

## 1 Answer

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.

Regarding the proof: yes, it would be very similar to ElGamal, since you have to construct the challenge ciphertext using a DDH tuple.

• Voted up. Could you also have a look at the question? I'm trying to at least think up a good title for it because the current one is way too generic. – Maarten Bodewes Mar 28 '16 at 10:50
• I am new to cryptography as well as stack exchange. Thank you for framing the question in the correct way. And, thanks for your input, cygnusv. To follow up, I can clearly understand what's happening in the Decryption now. Having trouble with the reduction now, but I will continue to work on it. Also, I was hoping if you could say if my theory that it isn't practical because of its low efficiency was true? I felt that the work done would be much higher and hence, this approach isn't practical. – Tom Corless Mar 28 '16 at 22:26