Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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 Andrés Figueroa Santos Mar 28 at 8:40
I'd say you'd be right about the efficiency being too low. – Maarten Bodewes Mar 28 at 10:46
up vote 4 down vote accepted

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.

share|improve this answer
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 at 10:50
@MaartenBodewes Thanks, done! – cygnusv Mar 28 at 10:59
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 at 22:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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