3
$\begingroup$

I am studying a thesis on the design of a key encapsulation mechanism (KEM). In section 2.6 (page 18) of this thesis, the following explanation is given about the difference between KEM and common methods:

KEM is a method used by two parties to derive a symmetric key using public-key cryptography. In practice, this asymmetric technique produces a random key K and an "encapsulation" C of that key. The latter is a cipher, which can be used to derive the generated random key. This mechanism may seem very similar to a two-step cryptosystem in which we first generate a random value before encrypting it with the other party’s public key. However, encapsulation and decapsulation functions perform more operations in practice and usually result in a more flexible and optimized way of performing those operations than the traditional approach.

The author of the thesis has one of the reasons for the concepts of flexible and optimized as follows:

One of the reasons why it could be considered sufficiently better than a traditional PKE approach is that the symmetric key is the result of the encapsulation method and that there is no need for further padding. That is an essential aspect since when padding is not performed appropriately, it could lead to disastrous attacks.

My Question: What other advantages does the use of KEM have compared to traditional PKE approach, except the advantage of padding?

My try: One of the interesting points I noticed is the following paragraph, which is sourced from KEM Wikipedia page. If I'm not mistaken, the following property makes KEM have the forward secrecy property.

Note that while M can be calculated from m in the KEM approach, the reverse is not possible, assuming the key derivation function is a secure one-way function. An attacker who somehow recovers M cannot get the plaintext m. With the padding approach, he can. Thus KEM is said to encapsulate the key.

Thank you for participating in the discussion and explaining other advantages of KEM to traditional PKE approach.

$\endgroup$

2 Answers 2

2
$\begingroup$

Note that the Wikipedia article somewhat confusingly uses $m$ for the actual random value that is encapsulated while $M$ is the derived key.

I don't really see the advantage of not being able to calculate $m$ if $M$ can be found, as usually the $m$ is only used to calculate one particular value of $M$. This is of course not always the case: it is possible to derived two session keys instead of one, or reuse $m$ (as indicated in the Wikipedia article). However, I would argue this is easy to avoid, and running a KDF afterwards is always possible as well.

Similarly, forward secrecy mainly depends on the value of the private key and $M$ to be ephemeral. So it is perfectly possible to create an ephemeral scheme that is based on - for instance - RSA encryption. In practice RSA key pair generation is probably too inefficient to use it for this purpose. The private keys within KEM schemes don't need to be ephemeral, forward security is not an inherent property of KEM nor is it particular to KEM.


I'd say that not using a padding mechanism has some advantages, mainly due to simplicity. There is no need for a padding mechanism to be present which allows for simplified implementation, and an implementation that is more likely to resist oracle attacks. There is no need for a hash, for instance, which also means that no hash doesn't need to be configured to calculate $m$.

Obviously the presence of the required KDF will somewhat diminish this advantage. This KDF needs to be present and needs to be configured. As long as those kind of choices are not well-defined it may be harder to actually perform a KEM. For instance, KEMs require specific KDF settings for deriving the keys within a HSM.

Another issue of KEM's is that they may also require a larger random. Quite often this is mathematically defined to be a random in a range [0, N) where N is not necessarily a power of two. This requires both more random bits and possibly a fast and secure method to create such a random.

Usually this is taken care of in the algorithms themselves - e.g. CRYSTALS-Kyber doesn't require an intricate method. However, in other instances such as RSA or a KEM based on ECDH/Brainpoool curves a smarter generation method such as my "Optimized Simple Discard Method" (aka RNG-BC)" could be used.


Otherwise I don't see many other advantages of a KEM over an encryption scheme. The whole idea seems to me to avoid padding. So any advantage of a KEM over an encryption scheme must therefore be related to the padding.

In the other answer an advantage is shown where the KEM ciphertext may be smaller than one for encryption at the same security level. If that's possible then that's certainly an advantage of course.

$\endgroup$
1
  • $\begingroup$ Your point of view is absolutely correct. Thank you for your comment. $\endgroup$
    – User0258
    Apr 30 at 19:08
2
$\begingroup$

A KEM ciphertext can be smaller than a PKE ciphertext. For example:

  • In ElGamal PKE, an encryption of $M$ has the form $(g^r, A^r \cdot M)$, where $A$ is the public key. The security reasoning is that $A^r$ is pseudorandom given $A$ and $g^r$, so it ($A^r$) can effectively mask the payload $M$.

  • An ElGamal KEM ciphertext is simply $g^r$. The reasoning is that if $A^r$ is pseudorandom given $A$ and $g^r$, why not just take $A^r$ to be the (random) KEM payload?

So ElGamal KEM ciphertexts are half as long as their PKE counterparts. Not all KEMs are shorter than their corresponding PKE (most lattice-based KEMs are not), but the possibility exists.

Additionally, a KEM is just a simpler object. In 99.9% of everyday usage, if you are using a public-key encryption scheme, you are using it just to encapsulate a key for a symmetric-key scheme. So a KEM simply models common usage more minimally.

If I'm not mistaken, the following property makes KEM have the forward secrecy property.

This is not what forward secrecy means. Forward secrecy for a PKE would mean that the decryption key is constantly updated, so that if a ciphertext $C$ was decrypted at time $t$, and later the victim's decryption key is stolen at time $t+1$, the attacker would not be able to decrypt $C$.

What you describe instead is simply some one-way property.

$\endgroup$
0

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.