3
$\begingroup$

We know that key exchange is a less "advanced" cryptographic primitive than public key encryption. In the first paper of public key cryptography, Diffie and Hellman has mentioned that they were able to design a key exchange protocol (Diffie-Hellman key exchange) but they couldn't design a public key encryption scheme as they couldn't find a one-way function (OWF) with a proper trapdoor.

Russell Impagliazzo had introduced five worlds and has shown that (roughly speaking) if one-way functions exist then symmetric key encryption (SKE) and key exchange (KE) schemes exist, i.e., $\text{OWF}\implies\text{SKE, KE}$. But, this this condition is not enough to say that public key encryption (PKE) schemes exist, i.e, $\text{OWF}\not \hspace{-2mm}\implies\text{PKE}$.

Victor Shoup in designing a very efficient public key encryption schemes coined the term "key encapsulation mechanism" (KEM) as a special case of a public key encryption. He claimed that we can build PKEs from KEMs by just encrypting a random message as the shared key which will be the output of the encapsulation algorithm of the KEM. But, we can design KEMs more efficient than PKEs. So, we care about KEMs as a new notion and cryptographic primitive. Now, my questions are:

  1. Is the security definition (like IND-CCA) for a KEM weaker than the same security definition for PKE, since in a KEM just random messages are allowed to be encrypted? (Because the adversary has to distinguish between ciphertexts of two messages where one of them is random and not chosen by themselves.) When we look at them as equivalent primitives, I think it's roughly valid to talk about security definition although they're not same cryptographic notions.

It reminds me of "IND$\color{blue}\\\$$-CPA $\not\hspace{-2mm}\implies$ IND-CPA" but "IND-CPA $\implies$ IND$\color{blue}\\\$$-CPA" [link].

Or, it also similar to the definition of weak pseudorandom function which the adversary has access to probabilistic oracle that cannot be probed at adversary's arbitrary points, only outputs the result of a random input [Katz-Lindel's Book 2021, Question 3.28])

  1. What exactly makes KEM schemes more efficient than corresponding PKE schemes?
  2. Why is it possible to construct more efficient KEM schemes than PKE schemes? Because the KEM security definitions are weaker than the PKE security definitions; so this situation allows us to use the same "unkind" hardness assumption to achieve the same security that was impossible in the case of a proving security for PKE.

My main question is

  1. Can we build PKEs from KEMs in a black-box manner, i.e., $\text{KEM}\implies\text{PKE}$ ? Especially is it trivial to build a PKE counter-part for CRYSTALS-kyber KEM (the NIST's PQC standard, ML-KEM)?
Improve this question
$\endgroup$
1
  • $\begingroup$ I've edited the question and elaborated on the first and third questions. $\endgroup$ Commented Feb 25 at 5:32

1 Answer 1

Reset to default
3
$\begingroup$

Is the security definition (like IND-CCA) for a KEM weaker than the same security definition for PKE?

I don't know if we can say formally that the security definitions are weaker/stronger. We can't say that one implies the other, because they consider different primitives, with different syntax. I would say that the security definitions are completely analogous -- not weaker or stronger, but modified in the most straight-forward way to refer to a different primitive with different syntax.

What exactly makes KEM schemes more efficient than corresponding PKE schemes?

The example of ElGamal makes it quite clear. Why does $(g^r, A^r \cdot m)$ hide plaintext $m$ even given public key $A$? Well, $A^r$ is pseudorandom given $A$ and $g^r$, so it acts as a good one-time pad of $m$. But if $A^r$ is pseudorandom given $A$ and $g^r$, we might as well take $A^r$ to be the plaintext/payload and let the ciphertext be shortened to $g^r$.

This phenomenon happens commonly in cryptography. You have a primitive that supports arbitrarily chosen values. The reason it supports arbitrarily chosen values is because they are masked by some internal random thing. So when you don't need an arbitrarily chosen value, and any randomly chosen value will do, it is often more efficient to just take whatever "falls out of" the primitive.

However, most modern KEMs achieve CCA security via the Fujisaki-Okamoto transformation, which for technical reasons needs to be built from a chosen-message PKE and not a KEM. These KEMs are no more efficient than a plain PKE, but we still refer to them as KEMs because KEM is arguably the better abstraction. For example, if you look at the spec for ML-KEM, you will see that it describes a regular PKE scheme, and the user is instructed to encrypt a random payload.

Why is it possible to construct more efficient KEM schemes than PKE schemes?

Seems like a repeat of the previous question. It's very hard to answer "why" questions.

Can we build PKEs from KEMs in a black-box manner?

Yes of course, this is just hybrid encryption, which is literally the reason to define the KEM abstraction in the first place. (For your question it is also necessary to check that KEM implies SKE in a black-box manner. This is true, but highly non-trivial because it goes all the way down to one-way functions along the way.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm sorry. I've edited the main question: Constructing PKEs (more advanced primitives) from KEMs. But your answer is correct anyway: I totally forgot hybrid encryption. $\endgroup$ Commented Feb 24 at 9:47

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.