The PQC “Lord of the Rings”

Kyber (now known with the boring name of ML-KEM) won the NIST PQC KEM competition as it outperformed virtually every other method in terms of performance and key size. It is based on the classic LWE (Learning With Errors) problem, but has other things added in. This included the addition of a ring structure and which moved it away from a pure implementation of LWE. With a Ring LWE approach, we use polynomials in our operations, whereas an LWE approach uses integers (eg mod q). This considerably speeds up operations as it avoids integer computations.

But, some worry about this ring approach, and that there may be a future weakness. Overall, FrodoKEM does not have the ring structure, and is a more pure form of LWE — hence the derivation of its name from the “Lord of the Rings” — and gives a conservative approach to security.

In terms of performance, we can see that FrodoKEM is around two times slower than ML-KEM for key generation, and around 16 times slower for key decapsulation:

In terms of key and ciphertext sizes, we see a massive difference between ML-KEM and FrodoEM: