[oconnore]

> Additionally, SPHINCS+ will be standardized to avoid only relying on the security of lattices for signatures

> Both BIKE and HQC are based on structured codes, and either would be suitable as a general-purpose KEM that is not based on lattices

What's up with this caveat? Why would the standard require algorithms not based on lattices assuming there is confidence in the lattice based approach?

Is this a security concern, or is there some performance (ops/sec or size) related trade-off?

[nullc]

The security story for lattices hasn't been very stable.

Consider the graph in the Classic McEliece marketing materials, showing the exponent in the attack costs for lattice-based crypto:

https://classic.mceliece.org/comparison.html

Because of communication cost considerations the lattice candidates use problems small enough that another substantial improvement in attacks could leave them vulnerable (no shock that they use small problems: if you're really not communication cost constrained use McEliece and don't worry about it).

If you do use lattice key agreement, be sure to use it in a hybrid configuration (combined with ECC like ed25519 or Curve448) to avoid the (small but hard to assess) risk that your security upgrade could actually be a security downgrade.

[bawolff]

Presumably to hedge their bets. If suddenly someone finds a major problem with latices, its good to have an alternative waiting in the wings.

See also sha-3 vs sha-256

[oconnore]

If NIST feels the need to hedge their bets, why are they publishing at all? The whole point of these recommendations is so that I, a non-expert, don't have to reason about cryptographic bets.

[kickling]

Well, most modern cryptography is based on assumptions that can not be proven, so having different standards based on different assumptions is probably the only way to safeguard against if one of the assumptions would be proven false in the future.

[bawolff]

To nitpick, afaik, its not that they cannot be proven, its that they have not been, and look very hard to prove, which is slightly different (not my area of expertise, but i assume this would be tied to p vs np)

[adastra22]

I it not tied to P vs NP as far as I’m aware. But it is the same sort of situation: number theory assumptions that are completely unproven despite many attempts.

[pezezin]

According to Wikipedia, all the proposed PQC schemes are proven to be NP-Hard, so you could say that their security depends on P != NP: https://en.wikipedia.org/wiki/Post-quantum_cryptography#Secu...

[bawolff]

I was thinking, if you could definitively prove these assumptions are hard, that would prove P != NP, because if P=NP that would imply there would be an algorithm to solve these types of problems, since they are the type of thing that can be solved in polynomial time with the key, but cannot without a key. (I'm a bit out of my depth here)

[oconnore]

Maybe it safeguards them from looking like they've screwed this up, but in terms of providing a concrete recommendation to system implementers, how does this safeguard anything? How does offering multiple algorithms in the PQC category help me make systems safer? What am I actually supposed to do here (how do I reflect this hedge in a system design)?

They didn't feel the need to provide multiple recommendations during the AES, or the SHA-3 process, even though Rijndael and Keccak used different constructions relative to RC6/TwoFish and SHA-2/Blake2. Why now?

[gdavisson]

The recommendations look clear to me: you should use CRYSTALS-Dilithium (unless you need smaller signatures, in which case use FALCON), but you should also be prepared to switch to SPHINCS+ on short notice if someone breaks CRYSTALS-Dilithium (or structured lattices in general).

So best practice would seem to be to implement both CRYSTALS-Dilithium and SPHINCS+, set CRYSTALS-Dilithium as the default, and provide a switch (config setting, whatever) to switch to SPHINCS+. If you have long-term keys, you should have both forms set up & ready to use.

[bawolff]

> They didn't feel the need to provide multiple recommendations during the AES, or the SHA-3 process, even though Rijndael and Keccak used different constructions relative to RC6/TwoFish and SHA-2/Blake2. Why now?

SHA-3 was explicitly alternative reccomendation. The entire point was to come up with something that was not based on sha-2, because they were worried that the attacks on md5/sha1 could be extended to sha2 (which didn't really happen the way people were worried about). Even to this day, general advice is not to use sha3.

Less clear cut for aes, but at time of standardization (and even now afaik), triple des was considered secure, so its not like there wasn't a secure alternative.

These standards arent meant as implementation guides. You still need cryptography knowledge to securely use them.

[bawolff]

Life's hard and the world is uncertain. If NIST could make an algorithm that they could prove was 100% safe with no possibility of future cryptoanalytical breakthroughs, i am sure they would, but that is beyond current state of the art.

[Beldin]

You mean like a one-time pad? I'm sure the folks at NIST know about it; it is completely unbreakable and had been around for a while. Use is not really practical though, so typically reserved for very specific use cases.

[upofadown]

One time pads fall into the symmetrical encryption category. There is no huge issue with symmetrical encryption with respect to the possibility someone might invent a quantum computer. The things people are working on for a post quantum world and NIST is attempting to standardize are in the asymmetrical encryption category.

[bawolff]

This is a silly nitpick. I think its pretty well understood from context i meant a practical quantum safe key agreement algorithm. One time pad cannot be used for that purpose at all, let alone practically.

[adastra22]

Non-cryptographers should not be implementing NIST standards. You should be using higher level APIs written by cryptographers which do employ NIST standards in the details.

[astrange]

Implementing them for fun might turn you into a cryptographer, though, especially (or only?) if you manage to find everything you get wrong.

[oconnore]

If you're including cryptography in a system design, you are almost certainly relying on NIST standards to select algorithms.

[runjake]

They aren't publishing until 2024 at the earliest. This is just a head's up that they will be publishing in the future.

Presumably, they'll have a better idea by then.

[Spooky23]

Perhaps they want industry to start working on software or hardware to leverage these algorithms?

Cryptography is driven by defense applications. For all us civilian types know, these algorithms have been around for 30 years.

[hinkley]

Particularly sha-3 vs sha-512, which turned out to have issues.

[adastra22]

SHA-512 doesn’t have any issues.

[hinkley]

The selection criteria for SHA-3 included internal state being greater than the output size. SHA-1 and SHA-2 both repeat this mistake of MD5. SHA-2 has variants that don't have this problem, but sha-256 and sha-512 aren't among them.

I'm having trouble finding it now but I recall someone complaining about the constants for 512 leaving something to be desired.

[adastra22]

This isn’t a mistake per se, it’s how that class of hash functions—and really, almost every hash function ever—is implemented. It’s called the Merkle-Damgård construction. It adds some very good properties and is the basis for how hash functions can be used in hash tree constructions and such.

But proving that the input state is evenly mixed among the output state is THE hard thing to prove (the hash function equivalent of the difficulty of factoring integers), so for the sake of ecosystem diversity NIST chose a hash function based on different principles for SHA-3. It’s not a criticism of SHA-2 that the difference was called out.

The constants are the fractional bits of of successive cube roots. This is effectively a nothing-up-my-sleeve random number selection. If there are problems with this, that in itself would be a serious cryptographic result.

[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!

[latenightcoding]

Some people believe you can generalize Shor's algorithm to attack lattice-based cryptography.