I am really curious about this one problem 10.12 from Katz/Lindell's book. It goes as follows: enter image description here

I am quite sure we can assume that $\textsf{Enc}_k(m) \in \mathbb{G}$, as the authors devoted the whole subsection to this issue (p.367). Now, my best shot was to use this $\textsf{Enc}_k(m)$ kind of like an exponent $r$, so that the tuple sent is $\langle g^{x\cdot\textsf{Enc}_k(m)}\cdot k, \textsf{Enc}_k(m) \rangle $, and the decryption is then a division by $(g^{\textsf{Enc}_k(m)})^x$. But then I realized it is very easy to extract $k$ from $g^{x\cdot\textsf{Enc}_k(m)}\cdot k$, because an attacker knows $g^x, \textsf{Enc}_k(m)$, and exponentiation/finding inverse is assumed to be easy in $\mathbb{G}$. I'd be grateful for any hint.

  • $\begingroup$ Hint: $k$ needs not be chosen arbitrarily. It can be obtained by e.g. a hash of some element of $\mathbb G$ that the sender and receiver both get to know. Independently: I don't think that the book means $\textsf{Enc}_k(m)\in\mathbb{G}$; rather, I think that $\textsf{Enc}_k(m)\in\{0,1\}^*$, as common in private-key encryption schemes. $\endgroup$
    – fgrieu
    Commented Jan 25 at 16:45
  • $\begingroup$ @fgrieu If I understand you correctly, there should be some kind of prior agreement about an element of $\mathbb{G}$ whose hash should then be used as a key for symmetric encryption. But what is the point of hybrid encryption if there is some kind of prior agreement between sender and reciever? Wouldn't be easier in this case to just agree upon a symmetric key and call it a day? $\endgroup$ Commented Jan 25 at 18:05
  • $\begingroup$ No prior agreement is needed beyond the algorithm, and the transfert of public key from receiver to sender (much like in the scheme described in preamble of the quote). The cipher text is $\langle u, \textsf{Enc}_{H(v)}(m) \rangle$ where $u\in\mathbb G$, $v\in\mathbb G$, and you are tasked to determine how sender generates $u$ and $v$ knowing the public key, and how the receiver finds $v$ knowing $u$ and the private key. $u$ and $v$ are much as inside ElGamal. Once you figured it out, you can answer your own question. $\endgroup$
    – fgrieu
    Commented Jan 25 at 18:09
  • $\begingroup$ This is a section about hybrid encryption, where ElGamal is the public-key KEM and $\textsf{Enc}$ is an arbitrary symmetric-key DEM. So I don't believe it is safe to assume that $\textsf{Enc}_k(m)$ is in the cyclic group. It is probably a very long string. $\endgroup$
    – Mikero
    Commented Jan 25 at 18:38

2 Answers 2


Are you comfortable with the connection between ElGamal encryption and the Diffie-Hellman Key Agreement (DHKA)?

ElGamal is just DHKA + OTP, just "repackaged" in a different way:

  • The ElGamal receiver's public key $X = g^x$ is like their DHKA message.
  • The first component of the ElGamal ciphertext $R = g^r$ is like the sender's DHKA message.
  • Given these two DHKA messages, the sender and receiver can agree on the DHKA key $g^{xr}$.
  • The second component of the ElGamal ciphertext $X^r \cdot m$ is like a OTP encryption of $m$ using the DHKA key $g^{xr}$ as the OTP key, and using the cyclic group operation instead of XOR.

Now take the "natural way" to use ElGamal as KEM in hybrid encryption, which they describe in the problem, and understand it in terms of the analogy to DHKA+OTP:

  • Run DHKA to agree on a key (receiver's public key + first ElGamal ciphertext component)
  • Use that key as a OTP to encrypt $k$ (second ElGamal ciphertext component)
  • Use $k$ as a symmetric key to encrypt $m$ using $\textsf{Enc}$ (DEM ciphertext component)

Can you now see a way to simplify this approach?

  • $\begingroup$ I think I get what you mean. Just to check: the tuple sent is then $\langle g^k, \textsf{Enc}_{g^{kx}} (m) \rangle$, right? $\endgroup$ Commented Jan 26 at 14:31
  • $\begingroup$ @MichaelHammer: ding! By George, I think you've got it! $\endgroup$
    – poncho
    Commented Jan 26 at 19:48

So, thanks to @fgrieu and @Mikero, I was able to figure it out. Two important points:

  1. It was pointed out to me that, fairly enough, it is not safe to assume $\textsf{Enc}_k (m)\in \mathbb{G}$, as I was thinking prior to this discussion.
  2. Following the exercise description, I mistakenly assumed that the improved version of the "natural way" should also stick to $k \leftarrow \{0,1\}^n$ being chosen uniformly at random, and the second component of the hybrid encryption should be $\textsf{Enc}_k (m)$. That is, of course, not the case, and the exercise is actually about finding a clever way to choose this symmetric key.

As pointed out by @Mikero, El Gamal is kind of DHKE combined with "OTP" in this group (see also Lemma 10.20 from the book). So, the "natural way" suggests to agree upon an asymmetric key and then use it to encrypt a symmetric key that in turn is used to encrypt a message. The solution is, rather then discarding the asymmetric key, to use it as an symmetric key, and then there is no need to do the "OTP" step of the Elgamal. More to the point, the tuple sent is $\langle g^r, \textsf{Enc}_K (m)\rangle$, where $r \leftarrow \mathbb{Z}_q$ and $K := (g^x)^r$. So, basically the whole scheme has boiled down to run a DHKE and then use it as a key for some symmetric encryption algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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