Skip to main content
edited body
Source Link
Mikero
  • 15.6k
  • 2
  • 37
  • 60

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 KEMs from 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.)

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 KEMs from PKEs 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.)

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

Source Link
Mikero
  • 15.6k
  • 2
  • 37
  • 60

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 KEMs from PKEs 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.)