Many (but not all) of the Lattice-based KEMs that made it far into the NIST competition had quite similar structure.
- start with the LPR "noisy diffie hellman" key exchange as a meta-algorithm
- instantiate it with respect to some variant of LWE (say choosing LWE/LWR, and whether to use algebraic structure, roughly)
- if using an algebraically structured form of LWE, choose the ciphertext moduli $q$ either as a power of two (for fast modular reduction), or NTT friendly (for fast polynomial multiplication)
within this design space, the goal of FrodoKEM is essentially to be as conservative as possible with respect to #2, namely use algebraically unstructured LWE as the underlying hardness assumption. This comes at significant increases of
- the size of ciphertexts, and
- the running time of various operations.
the "benefit" is that if algebraically structured LWE suffers an attack that does not extend to unstructured LWE, FrodoKEM is plausibly secure still, while other schemes would be broken.
So FrodoKEM has the benefit of a more conservative hardness assumption (compared to many other lattice-based KEMs), but the downside of being less efficient.
We can validate this some by looking at the NIST round 3 report.
On page 17, we see the following
NIST also decided to remove FrodoKEM, NTRU Prime and Picnic from consideration
for standardization. FrodoKEM is a lattice-based candidate that had been chosen as an
alternate during the second round. FrodoKEM is mainly distinguished by the fact that it
does not rely on structured lattices (in contrast to the finalists KYBER, NTRU, and Saber).
While NIST intends to select at least one additional KEM not based on structured lattices for standardization after the fourth round, three other KEM alternates (BIKE, HQC, and
SIKE) are better suited than FrodoKEM for this role. FrodoKEM has generally worse per-
formance than these three and so will not be considered further for standardization.
Essentially, while FrodoKEM may survive a novel attack on structured lattice assumptions, so would non-lattice based primitives, and they have better performance.
