[kvathupo]

A point rendering the choice even more curious: Germany and the Netherlands have recommended the use of encryption not relying on the shortest vector problem [1]. The two suggestions of FrodoKEM (relying on hardness of the learning with errors problem) and Classic McEliece (relying on hardness of decoding random codes?) aren't lattice-based apparently.

Perhaps NIST knows something we don't ; ^ )

[1] - https://twitter.com/CJTjhai/status/1544398903591796736

[markschultz]

LWE's hardness is based on SVP (ignoring issues of tightness, which isn't unique to FrodoKEM). The difference between FrodoKEM + Kyber/Saber isn't relying on SVP/not (they all essentially do), but is on relying on LWE over structured lattices or not.

At a very high level, all of the three rely on an n x n matrix at a certain point. The "structured lattice" schemes (Kyber/Saber) make structural assumptions about this matrix, say that each row is a cyclic shift of the previous row. This turns an O(n^2) object into an O(n) object, giving many performance improvements. The downside is that the additional structure can plausibly be used for attacks (but the best attacks ignore the structure, so this is a "potential issue", not a current issue).

[kvathupo]

Ah, thanks for the clarification!