Score:1

Why does ECIES use "Key Encapsulation"? Does it?

in flag

In yet another twist that is the terminology around key establishment I found out that ECIES is often denoted as key encapsulation followed by data encapsulation. I'm wondering how the term "key encapsulation" can be applied to ECIES.

ECIES consists of the following:

  1. key agreement using ECDH, giving the master secret;
  2. key derivation using a KBKDF which results in the symmetric data key being established;
  3. some kind of data encapsulation using the derived symmetric data key.

Now I've always thought that "encapsulation" is almost synonymous with encryption. You protect a pre-established value using a mechanism. However, that doesn't seem to be the case with ECIES; the value is instead agreed upon by both parties; it isn't known in advance by one of the parties. This does seem to be the case for RSA-KEM, where the master secret is created in advance.

Is this yet another instance where cryptographers (kuch cryptologists kuch) don't seem to care what the term actually implies? Should the general term "key establishment" be used if both ECIES and RSA-KEM are implied? Or does key encapsulation somehow mean that a key derivation mechanism is implied?

Maarten Bodewes avatar
in flag
I'm probably too logical to ever be a linguist. I mean, when symmetric keys are referred to as "private keys" instead of secret keys - which means you are likely to end up with a "shared private key" - I'll get into a fuss.
knaccc avatar
es flag
I too am unsettled by the use of the term encapsulation instead of agreement. I found a non-paywalled pdf of [ISO/IEC 18033-2:2006](https://www.shoup.net/iso/std4.pdf) where they define key encapsulation and data encapsulation. I'm guessing it felt like too much work to do anything other than keep the terminology consistent when dealing with EC-based instead of RSA-based schemes. The term "EC discrete log" also bugs me. We refer to EC "scalar multiplication", yet still talk about the EC DL assumption.
Marc Ilunga avatar
tr flag
I guess ECIES is more a KEM/DEM than just a KEM. But, I would argue that ECIES quite similar to any RSA based KEM/DEM scheme. For the encapsulation part, the sender gets to choose the randomness that goes into the KDF. Furthermore, the sender knows in advance the key (maybe in a less obvious manner than RSA). So in that regard, they have the same "shape". Which contrasts with ephemeral DH like in SIGMA,TLS1.3 or Noise. Other than that, from a definition standpoint, ECIES has the right "interfaces" to qualified as being constructed from a KEM.
poncho avatar
my flag
"Now I've always thought that "encapsulation" is almost synonymous with encryption. You protect a pre-established value using a mechanism"; that isn't the way the term is used. knaccc cited the ISO/IEC definition, which doesn't assume shared secret transport; in addition, if we look at the recent postquantum KEMs (such as Kyber), they also don't allow the sender to select the shared secret (and instead both sides generate it via a hash). It appears that the use of the term 'encapsulation' with ECIES is consistent with how the term is used elsewhere
Maarten Bodewes avatar
in flag
@poncho They define it initially as: "key encapsulation mechanism: similar to an asymmetric cipher, but the encryption algorithm takes as input a public key and generates a secret key and an encryption of this secret key." And then they provide a `KEM-Encrypt` function that **only** takes a public key and options (???). If anything, that definition is even weirder. I'd even argue that it is somewhat outlandish to define an encryption routine that doesn't take any secret or data to encrypt and then actually not encrypt anything. Mathematically sound though, nothing wrong with the interface.
SAI Peregrinus avatar
si flag
IIUC: A KEM *creates* a shared secret key as part of its operation. The transmitted value is an encrypted group element (or similar) which gets turned into the shared secret key via a KDF. Unlike a key exchange, a KEM is non-interactive: the sending party can find the resulting shared secret key without waiting for a response from the receiving party. RSA-KEM, ECIES, and the post-quantum KEMs all work this way AFAICT.
Score:3
dz flag

Now I've always thought that "encapsulation" is almost synonymous with encryption. You protect a pre-established value using a mechanism.

This is not how the term has ever been used in the literature.

The definition of public-key key encapsulation has been consistent since Shoup introduced it in 2000 (emphasis added):

We describe here a general method for constructing a hybrid encryption scheme. To this end, it is convenient to define the notion of a key encapsulation scheme. This is a scheme that allows a party to generate a random bit string and send it to another party, encrypted under the receiving party’s public key.

A key encapsulation scheme works just like a public key encryption scheme, except that the encryption algorithm takes no input other than the recipient’s public key. Instead, the encryption algorithm generates a pair $(K, \psi)$, where $K$ is a random bit string of some specified length, say $l$, and $\psi$ is an encryption of $K$, that is, the decryption algorithm applied to $\psi$ yields $K$.

One can always use a public key encryption scheme for this purpose, generating a random bit string, and then encrypting it under the recipient’s public key. However, as we shall see, one can construct a key encapsulation scheme in other ways as well.

—Victor Shoup, “Using Hash Functions as a Hedge against Chosen Ciphertext Attack”, in Bart Preneel (ed.), Advances in Cryptology—EUROCRYPT 2000, Springer, Lecture Notes in Computer Science, vol. 1807, ISBN 978-3-540-67517-4, ISSN 0302-9743, § 4.2 “A General Hybrid Construction”

This definition has been maintained consistently in the literature in the decades since then. See, for example:

Abstract … A KEM is a probabilistic algorithm that produces a random symmetric key and an asymmetric encryption of that key. …

A KEM is a triple of algorithms: …

  • a encapsulation algorithm, $\mathit{KEM.Encap}$, that takes as input a public-key $\mathit{pk}$ and outputs an encapsulated key-pair $(K, C)$ ($C$ is sometimes said to be an encapsulation of the key $K$),

—Alexander W. Dent, “A Designer's Guide to KEMs”, Cryptology ePrint Archive, Paper 2002/174, 2002.

3.26 key encapsulation mechanism: similar to an asymmetric cipher, but the encryption algorithm takes as input a public key and generates a secret key and an encryption of this secret key. (See Clause 8.1.)

8.1 Key encapsulation mechanisms

A key encapsulation mechanism KEM consists of three algorithms: …

  • An encryption algorithm $\operatorname{\mathit{KEM.Encrypt}}(\mathit{PK}, \mathit{opt})$ that takes as input a public key $\mathit{PK}$, along with an encryption option $\mathit{opt}$, and outputs a secret-key/ciphertext pair $(K, C_0)$. Both $K$ and $C_0$ are octet strings.

—Draft ISO/IEC 18033-2: Information technology—Security techniques—Encryption algorithms—Part 2: Asymmetric Ciphers, Victor Shoup (ed.), 2004. (Final version hidden behind ISO paywalls.)

This draft goes on to detail ECIES in particular as a key encapsulation mechanism in § 10.2—combined with a data encapsulation mechanism to make an encryption scheme.

Your factoring of ECIES is a legitimate view:

ECIES consists of the following:

  1. key agreement using ECDH, giving the master secret;
  2. key derivation using a KBKDF which results in the symmetric data key being established;
  3. some kind of data encapsulation using the derived symmetric data key.

But you can also view steps (1) and (2) as a function only of the public key—the message to be encrypted is not involved yet, not until step (3)—that turns out to be a key encapsulation method. Combining the KEM of steps (1) and (2) with the DEM of step (3) gives public-key encryption.

(Note: Key agreement, or key exchange, as in Diffie–Hellman, always has two parties contributing non-secret inputs to agree on a secret output. As you see, you can derive key encapsulation from key agreement by using one of the non-secret inputs as a public key, generating the other non-secret input independently for each message, and sending the per-message non-secret input as a key encapsulation alongside the ciphertext. Whether it's secure depends on the details, but it always syntactically works out.)

The term has plenty of more recent examples—it is now the dominant paradigm for designing public-key encryption schemes today, including all NIST PQCRYPTO candidates. For instance:

A key encapsulation mechanism is a triple of algorithms $\mathcal K = (\mathsf{KeyGen}, \mathsf{Encaps}, \mathsf{Decaps})$ and a corresponding key space $K$. …

  1. The probabilistic encapsulation algorithm $\operatorname{\mathsf{Encaps}}(\mathit{pk})$ takes as input a public key $\mathit{pk}$ and outputs a ciphertext $c$ as well as a key $k \in K$.

—Nina Bindel, Jacqueline Brendel, Marc Fischlin, Brian Goncalves, and Douglas Stebila, “Hybrid Key Encapsulation Mechanisms and Authenticated Key Exchange”, in Jintai Ding and Rainer Steinwandt (eds.), proceedings of Post-Quantum Cryptography: 10th International Conference, PQCrypto 2019, Springer, Lecture Notes in Computer Science, vol. 11505, ISBN 978-3-030-25510-7, ISSN 0302-9743.

A cursory search of the cryptology eprint archive will reveal arbitrarily many other papers in the decades since it was introduced that all agree on the definition of key encapsulation.

You may find the use of the word linguistically distasteful, but the literature is consistent on its technical meaning.

Marc Ilunga avatar
tr flag
The username seems rather on topic given the question ; )
Maarten Bodewes avatar
in flag
I'm at least happier with $\text{Encaps}$, $\text{Decaps}$ than with $\text{Encrypt}$, $\text{Decrypt}$. Alright, I guess the person that names the scheme has first say in it, and it has been confirmed by regular use. By the way, I wasn't arguing for "key agreement"; it's just that functionally DH key agreement is being used within (EC)IES. "Key establishment" seems more logical to me, but maybe that's *too* generic.
Score:1
in flag

It seems clear from the responses that KEM means that some secret is being encapsulated / protected by the algorithm. How this happens within the algorithm itself seems irrelevant.

In [the standard "ISO/IEC 18033-2: Information technology — Security techniques — Encryption algorithms — Part 2: Asymmetric Ciphers" by Victor Shoup linked to within this comment some definitions are given.

key encapsulation mechanism: similar to an asymmetric cipher, but the encryption algorithm takes as input a public key and generates a secret key and an encryption of this secret key. (See Clause 8.1.)

Which shows that no given value is being protected even though it is indicated as encryption similar to an asymmetric cipher.

This is further expanded to by Clause 8.1:

Key Encapsulation Mechanism KEM consists of three algorithms:

  • A key generation algorithm $KEM.\text{KeyGen()}$, that outputs a public-key/private-key pair $(PK , pk)$. The structure of $PK$ and $pk$ depends on the particular scheme.

  • An encryption algorithm $KEM.\text{Encrypt}(PK , \text{opt})$ that takes as input a public key $PK$, along with an encryption option $\text{opt}$, and outputs a secret-key/ciphertext pair $(K, C_0)$. Both $K$ and $C_0$ are octet strings. The role of $\text{opt}$ is analogous to that for asymmetric ciphers (see Clause 7.4).

  • A decryption algorithm $KEM.\text{Decrypt}(pk , C_0)$ that takes as input a private key $pk$ and a ciphertext $C_0$, and outputs a secret key $K$. Both $K$ and $C_0$ are octet strings.

The decryption algorithm may fail under some circumstances.

A key encapsulation mechanism also specifies a positive integer $KEM.\text{KeyLen}$ — the length of the secret key output by $KEM.\text{Encrypt}$ and $KEM.\text{Decrypt}$.

Although I would still argue that encapsulation as well as encryption are not the correct terms linguistically nor logically, I'll have to concede at this point that some value is being protected by the algorithm. If that's called "encapsulation" then the term makes sense.

I'd use the term "establish" instead of encapsulate as that seems to better convey what is happening, but by now the term "encapsulation" has been firmly encapsulated. It is for instance used in the "encryption" algorithms within the NIST PQC competition. Newcomers will have to get used to the jargon.

Maarten Bodewes avatar
in flag
Also, that's a **section** not a **clause**. Thanks for all the comments.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.