Return to Question

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.

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

2. What exactly makes KEM schemes more efficient than corresponding PKE schemes?
3. 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

4. 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)?

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])

2. What exactly makes KEM schemes more efficient than corresponding PKE schemes?
3. 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

4. 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)?

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.

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

2. What exactly makes KEM schemes more efficient than corresponding PKE schemes?
3. 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 which to achieve the same security that was impossible in the case of a PKE.

My main question is

5. 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)?

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.

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

2. What exactly makes KEM schemes more efficient than corresponding PKE schemes?
3. 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

4. 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)?

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 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 exists, i.e., $\text{one-way function}\implies\text{SKE, KE}$. But this this condition is not enough to say that public key encryption (PKE) schemes exist, i.e, $\text{one-way function}\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 PKE from KEM 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 KEM as a new notion and cryptographic primitive. Now, my question is:

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 alowed 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)
2. What exactly makes KEM schemes more efficient than corresponding PKE schemes?
3. Why is it possible to construct more efficient KEM schemes than PKE schemes? Because the KEM security definition in weaker than the PKE security definition and allows us to achieve the same security by using the same "unkind" hardness assumption which was impossible in the case of proving security for PKE.

My main question is

4. 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)?

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.

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

2. What exactly makes KEM schemes more efficient than corresponding PKE schemes?
3. 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 which to achieve the same security that was impossible in the case of a PKE.

My main question is

5. 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)?