Key Exchange vs Key Encapsulation

Question

From what I understand, the steps of a key exchange protocol are

1. Alice and Bob each encrypt something using their public key and private key and send the result to each other

2. Alice and Bob each do some mechanism with their private key and the result sent by the other

3. They should agree on the secret.

Key encapsulation is

1. Alice generates a secret key and public key and sends the public key to Bob.

2. Bob generates his own secret key and encrypts it using Alice's public key. He sends the result to Alice.

3. Alice decrypts the result using her private key and ends up with Bob's key.

Is this correct and if not, could someone clarify which parts I am misunderstanding or missing?

Looking at the Known Answer Tests for NIST PQC KEM Submissions, when a seed is provided, each algorithm returns the secret key, public key, cipher text, and shared secret.

Is the shared secret Bob's private key and the cipher text what Bob sent to Alice? If not, how does the terminology work? How can the seed guarantee the correct public/secret key generation?

Answer 1

Key exchange: I'll use ECC as an example. Alice and Bob generate ephemeral key pairs and sign their ephemeral public key with their static private key, and then send their signed ephemeral public key to each other.

Both parties receive the others signed ephemeral public key and verify it using the others static public key, stored by a CA or in a PKI. Now they combine their own ephemeral private key with the other's ephemeral public key, using EC Point Multiplication (for this example). Now they both have a shared secret, as both multiplications give the same result.

This is then run through a quick hash like SHA2/3 into the correct length for symmetric encryption. For example with AES-256, the shared secret goes through SHA(3)-256 to get a key of the correct length.

Key encapsulation: I'll use the RSA KEM for this example. Bob knows Alice's public key $(e,n)$. He creates the random number $m$ from a CSPRNG , where $0<m<n$, and converts it into a symmetric key $M$ with a KDF ie symmetric key $M=KDF(m)$. The Ciphertext $$C = m^e (mod \ n)$$ This is transmitted from Bob to Alice, and she can decrypt it by computing $$P = m^d (mod \ n)$$ Alice now has $k$, and derives the symmetric key $M$ with $M = KDF(m)$

Side note: I've seen that you tagged post quantum cryptography, so you could use NTRU for KEM; ECC and RSA can be broken with a powerful enough quantum computer running Shor's algorithm. The NTRU KEM works differently to the RSA KEM however. I'm not familiar with a quantum safe version of the ECC key exchange, though I'm sure one exists.

Answer 2

There is issue in key encapsulation when you say "Bob generates his own secret key and encrypts it using Alice's public key. He sends the result to Alice."

This is encryption not encapsulation. In key encapsulation algorithm, the secret key to be shared by Bob is produced as an output of the “encapsulation” algorithm, which is run on the Alice public key alone. This works as follows:

The input of encapsulation algorithm is the Alice public key and output generated by the encapsulation algorithm on Bob side is the ciphertext c and secret key k. Now, Bob will send ciphertext c to Alice and Alice will decapsulate it with its private key to recover the secret key k.

For more concept clarity see the peikert's KEM and its more clear version by Vikram using lattice based cryptography in post-quantum cryptography. ).