The Mechanics Behind a Post-Quantum Key Encapsulation Mechanism

Secure communication over the Internet relies on two parties being able to agree on a secret key without having met beforehand. This is made possible by key exchange algorithms, which form the backbone of protocols such as TLS. The challenge these algorithms solve is acute: if a key were transmitted physically, it could be intercepted or stolen. Key exchange algorithms allow two parties to derive a shared secret value that an eavesdropper cannot determine, even with access to all the messages exchanged.

Deep dive into a post-quantum key encapsulation algorithm

Current widely used key exchange algorithms depend on problems like integer factorization and the discrete logarithm problem. These, however, are vulnerable to quantum computers. To build systems secure against such adversaries, cryptographers have turned to problems based on lattices and isogenies, which are believed to remain hard for quantum machines.

The core tool for this task is a Key Encapsulation Mechanism (KEM). A KEM works through three operations: Generate, which creates a public/private keypair; Encapsulate, which uses a public key to produce a shared secret and an encrypted version of it (the ciphertext); and Decapsulate, which uses the private key to recover the shared secret from the ciphertext. KEMs are distinct from general Public Key Encryption (PKE) in that they are designed specifically to agree on a single symmetric key, which is then used with more efficient symmetric encryption. This is what we need instead of a full PKE scheme, and it solves the key exchange problem more directly.

The Mathematical Foundation: Learning With Errors

We will examine FrodoKEM, a post-quantum KEM whose design illustrates how these constructions fit together. Its security rests on the hardness of the "Learning with Errors" (LWE) problem. In LWE, one must recover a secret vector s, where each of its elements is in the set of integers from 0 to q, given a set of random, "approximate" linear equations. These equations are not exact; they are off by a small, random integer error e. If the error were known, the secret could be recovered with standard linear algebra like Gaussian elimination. The deliberate introduction of this unknown error makes the problem computationally intractable, even for quantum adversaries.

LWE's importance comes from its connection to lattice problems. An efficient solution to LWE would imply a quantum algorithm for problems like the Shortest Vector Problem (SVP). In particular, LWE can be viewed as an average-case form of the Bounded Distance Decoding (BDD) problem, where, given a lattice point perturbed by noise, you must find the original nearest lattice point.

Image of a lattice.

Building the PKE: FrodoPKE

The second layer is constructing a Public Key Encryption (PKE) scheme from this mathematical base. FrodoKEM uses a scheme called FrodoPKE. Its operation follows a standard pattern with three parts:

  1. Generation: A keypair is generated from an LWE sample. The public key comprises the values A and B = As + e mod q, while the private key is the secret vector s.
  2. Encryption: To encrypt a message, one generates secret vectors and uses them to create new LWE samples. The ciphertext consists of a first sample b1 and a value v1, which is the message added to the most significant bit of another sample.
  3. Decryption: The receiver calculates m = v1 - b1 * s. This yields the message plus the error matrix. The message is recoverable through a rounding step, which works correctly if the error term is small enough.

FrodoPKE, like many PKEs, only achieves IND-CPA security (Indistinguishability under chosen-plaintext attack). This means a passive listener learns nothing from a ciphertext. However, this level of security is insufficient for the Internet, where adversaries can actively modify messages in transit and trick legitimate parties into decrypting them. This enables a chosen-ciphertext attack, where an adversary can use a decryption oracle to gain information about other ciphertexts. This is not a theoretical concern; practical attacks like Bleichenbacher's attack rely on this weakness.

Strengthening the Scheme: FrodoKEM

A KEM that only resists chosen-plaintext attacks is not enough. It needs to be secure against chosen-ciphertext attacks, providing IND-CCA security. The typical method for this is an altered version of the Hofheinz, Hovelmanns, and Kiltz (HHK) transformation, which turns an IND-CPA-secure PKE into an IND-CCA-secure KEM along with hash functions.

The internal workings of a KEM built this way trace a full cycle, with the key insight being a verification step during decapsulation.

  • Generation: The Generate function of the PKE is called to create a keypair (pk, sk). The public key is then hashed, and an additional random value s is chosen. The full private key becomes (sk, s, pk, pkh).
  • Encapsulate: A receiver creates a random message u. It then hashes the hashed public key pkh together with u to produce values r and k. It encrypts u using the public key and the randomness r, creating the ciphertext.
  • Decapsulate: The holder of the private key decrypts the ciphertext to get the message. Then, it hashes pkh with this recovered message to get (r, k) and re-encrypts the message. If the re-encrypted ciphertext matches the one received, the shared secret is derived from k and the ciphertext. If not, a random secret s is used instead.

This final re-encryption step is critical. It ensures that any ciphertext that has been modified in transit, or was never valid to begin with, will produce a completely different shared secret. This prevents an attacker from using the receiver as a decryption oracle to learn information about other messages. This construction is what blocks the decryption-failure attacks that could otherwise break the scheme, ensuring secure communication in a post-quantum world.

FrodoKEM and Its Competitors

FrodoKEM is not the only scheme of its kind; it is a candidate in the NIST post-quantum standardization process. The current landscape includes several other approaches based on similar foundations.

  • Lattice-based KEMs such as Kyber, NTRU, and Saber, which also derive their security from variants of the LWE problem. Their main advantage is speed and a small footprint for keys and ciphertexts, though their security assumptions need rigorous scrutiny.
  • Code-based KEMs such as Classic McEliece, whose security rests on decoding error-correcting codes, a problem that is older than RSA and thus has been studied for a long time. Its public keys, however, are dramatically larger. For instance, a Classic McEliece instance for 128-bit security has a public key of 261,120 bytes, while Kyber512, with a similar security claim, uses only 800 bytes.

The construction of these algorithms follows a common pattern, showing how cryptography is not about a single perfect primitive, but rather a layered process. Each layer, from a hard mathematical problem, to a PKE, to a KEM, builds on the previous one, contributing to the overall goal of providing secure communication against any adversary, quantum or not.