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
(or Kyber for short), was co-submitted by NXP security experts.
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
One such approach, called FrodoKEM, made it to the final round
of NIST’s standardization process, but wasn’t chosen as a winner. Nevertheless,
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
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
), 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
. 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
Memory (RAM, bytes)
Secret key size (bytes)
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
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
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