Conservative Post-Quantum Security with FrodoKEM

In our August 2022 blog, Standardization of Post-Quantum Cryptography, we discussed the risk that quantum computers pose to present-day public-key cryptography and described the effort, led by the National Institute of Standards and Technology (NIST), in the US, to create a standard for post-quantum cryptography (PQC).

In the time since we posted that blog, the NIST announced four “winners” of their standardization process, and we’re pleased to say that one of the winners, named CRYSTALS-Kyber (or Kyber for short), was co-submitted by NXP security experts.

Lattice-Based Winners

Of the four winners, three use a security approach based on what’s termed “lattice-based cryptography,” which is a method that uses the mathematical concept of a lattice – a collection of regularly arranged points – to encrypt and decrypt data.

And, of the three lattice-based methods the NIST selected, the two main winners (Kyber for key exchange and Dilithium for digital signatures) use a special structure designed to increase efficiency in terms of performance, key size and memory. In some cases, though, this special structure could be a benefit to attackers, making it desirable to more generic versions of lattice-based cryptography.

One such approach, called FrodoKEM, made it to the final round of NIST’s standardization process, but wasn’t chosen as a winner. Nevertheless, multiple  European governments have expressed strong interest in FrodoKEM and propose adding it to the toolkit to enable a quantum-safe feature.

So we thought we’d take a look at FrodoKEM from an embedded perspective.

FrodoKEM Is Conservative Security

FrodoKEM is a key encapsulation mechanism (KEM) based on the Learning With Errors problem (LWE). The security of a cryptographic public-key scheme typically relies on the difficulty of solving a mathematical problem which forms the security foundation. Solving the LWE problem can be reduced to solving lattice-based problems that are time-conjectured to be difficult, even for an adversary with access to a large-scale quantum computer.

FrodoKEM was submitted to the NIST competition demonstrating that this approach is “conservative, yet practical.” Conservative, because it relies on the most generic form of this mathematical problem while other approaches make use of special structure introduced to make the schemes faster. Practical, because the submission team showed that FrodoKEM can be considered ready for usage in the real-world, even though it is slower and bigger compared to schemes which were selected for standardization, such as Kyber.

When looking purely at the performance numbers, Kyber is a clear winner over FrodoKEM: Kyber is smaller in key and ciphertext sizes, and faster in both hardware and software. However, it should be noted that Kyber is based on a problem related to LWE. It has an added mathematical structure to it. This added structure might be a double-edged sword; its main benefit is that it allows for smaller key sizes and faster operations, while it has the potential drawback that this added structure could potentially be exploited by an adversary. (It’s worth pointing out that nothing, so far, indicates it could be exploited, but the possibility of exploitation still exists.) Since FrodoKEM is designed without this added “ring” structure (hence the designation Frodo, since, like its “Lord of the Rings” namesake, the scheme purposefully avoids using a ring ), it is considered to be a more conservative choice in terms of security.

EU Interest in Standardization

Even though the NIST is not going to standardize FrodoKEM, the promise of conservative security has motivated various European authorities to recommend its use. This includes the German BSI   and the French ANSSI . Furthermore, FrodoKEM is one of the schemes currently under consideration for standardization by the International Organization for Standardization (ISO). Since PQC is still a developing area, schemes with a conservative security approach are favorable for the migration from current to post-quantum schemes. This is emphasized by the observation that some PQC schemes may be vulnerable to new attacks and can be broken unexpectedly. The two most prevalent examples of this occurrence are Rainbow, a round 3 NIST signature scheme , and SIKE, a round 4 NIST signature scheme . Both were ultimately broken.

FrodoKEM on Embedded Devices

The increased sizes and runtimes of post-quantum schemes, compared to the pre-quantum schemes that they aim to replace (such as RSA and ECC), brings many challenges. Table 1 highlights the significant differences between pre- and post-quantum public-key cryptography schemes.

A significant amount of academic research goes into optimizing cryptographic schemes. In most engineering disciplines, optimizing tends to focus on making an algorithm faster. This makes sense for a lot of applications, such as reducing latency and increasing throughput in high-end cloud services.

Performance is a key requirement for embedded devices, too, but there’s the added challenge of working within a resource-constrained environment. Oftentimes, the first priority is to make sure the algorithm can run on the amount of available memory (SRAM). This requires optimizing in a different direction, by reducing peak stack usage of the target PQC algorithm.

This is especially true with FrodoKEM, which requires the storage of large matrices for intermediate computations. Small embedded systems used in (Industrial) IoT and other applications, have very limited amounts of memory available. On the lower end of the spectrum, this can range from 4kB to 16kB (an example would be the NXP LPC800 series). Table 1 shows that a straight-forward implementation of FrodoKEM cannot execute on such small devices.

However, our research, as part of NXP’s PQC team, shows it’s possible to greatly reduce memory usage by deploying various time-memory trade-offs, such as on-the-fly computations and changing the order of operations in the matrix multiplications. Using these techniques, some parameter sets of FrodoKEM can be deployed on embedded devices with as little as 16kB of SRAM, with only a negligible cost of performance compared to non-optimized implementations. Moreover, this allows the cryptographic engineer to set target peak memory consumption levels and generate target implementations within this memory limitation. Such low-memory FrodoKEM approaches do, however, come at the cost of performance. For full details, see our scientific paper Enabling FrodoKEM on Embedded Devices.

Future Challenges of FrodoKEM in Embedded

We’ve already discussed the side-channel security of post-quantum secure cryptographic algorithms (see Post-Quantum Cryptography: Physical Attacks and Countermeasures and Protecting Post-Quantum Cryptography Against Side-Channel Attacks). Most designs need to include countermeasures against side-channel attacks (and this is true for virtually all relevant scenarios we consider), and the new PQC standards (including FrodoKEM) are no exception. Also, Kyber and FrodoKEM both use the Fujisaki-Okamoto (FO) transform, which makes these schemes particularly vulnerable to physical attacks. The well-vetted countermeasure of masking will increase the memory requirement further.

Challenges like these mean there’s still work to be done before we can efficiently enable these new security standards on resource-constrained devices. At NXP, we’re using our combined expertise in security and embedded to make sure we provide the most efficient solutions. Learn more about post-quantum cryptography.

Authors