3
$\begingroup$

What are the advantages of FrodoKEM over other NIST PQC candidates? Also, have any critical vulnerabilities been discovered so far?

$\endgroup$

1 Answer 1

4
$\begingroup$

Many (but not all) of the Lattice-based KEMs that made it far into the NIST competition had quite similar structure.

  1. start with the LPR "noisy diffie hellman" key exchange as a meta-algorithm
  2. instantiate it with respect to some variant of LWE (say choosing LWE/LWR, and whether to use algebraic structure, roughly)
  3. 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.

$\endgroup$
1
  • 2
    $\begingroup$ One arguable advantage for some compliance purposes is that FRODO (along with Classic McELiece) is compatible with BSI guidance where other PQA schemes are not as of yet. $\endgroup$
    – Daniel S
    Feb 6, 2023 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.