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?

  • $\begingroup$ 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. $\endgroup$ Mar 28 '16 at 8:40
  • 1
    $\begingroup$ I'd say you'd be right about the efficiency being too low. $\endgroup$
    – 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.

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

  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Mar 28 '16 at 10:50
  • $\begingroup$ 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. $\endgroup$ Mar 28 '16 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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