Comment by adastra22 | Hacker News Reader

Comment by adastra22 | Hacker News Reader

Parent Full thread

> But even if a quantum computer is never built, new PQ standards are safer, more resilient, and more flexible than their classical counterparts.

lol wat? Nothing could be further from the truth. Just a few years ago, two of the four finalists of the NIST PQC were broken so badly that you could break production key sizes in hours with a 10 year old Mac mini. Most PQC deployments aren’t broken because they double up with classical crypto systems so that you have to break both, but people who were using these schemes were basically wasting their time.

Key sizes and signatures are typically much, much larger than classical cryptosystems.

PQC systems lack the flexibility of classical cryptography. Generally speaking the linear structure of classical schemes is what quantum computers exploit, and so it is gone from most (all?) PQC systems. That linear structure is what lets you do things like make a 2-of-2 by adding pubkeys and signatures. I’m not sure what is meant by flexibility of not stuff like this.

> Just a few years ago, two of the four finalists of the NIST PQC were broken so badly that you could break production key sizes in hours with a 10 year old Mac mini.

SIKE was not a Finalist, it was a Round 4 candidate.

Candidates being broken before the process finishes is a sign of the process working.

https://cacm.acm.org/news/nist-post-quantum-cryptography-can...

"Belgian researchers have cracked the SIKE cryptographic algorithm, a fourth and final-round candidate that the U.S. National Institute of Standards and Technology (NIST) was evaluating for its Post-Quantum Cryptography (PQC) standard."

SIKE was a finalist, it entered final round.

SIKE was probably the most exciting PQC algorithm available, if it hadn't been broken. It made it to the finals for a relatively brief time.

CRYSTALS also now has a possible attack proposed by a recent paper on a similar algorithm, so time will tell if any more of these algorithms is broken.

But SIKE was also broken in, like, a theatrical fashion. It was an explosive break!

It feels like there's some dancing around happening here, where the subtext is that where an algorithm is in a NIST contest process isn't determinative on it's own, and that there are external reasons we tend to trust the lattice stuff (because it's been studied for decades, &c).

Even with lattice stuff, the parameters keep having to be changed to ensure security. It may not be explosive breaks, but the cryptanalysis is advancing at stunning speeds. This stuff is no where near prime time ready.

I think we are agreeing, directionally.

I don't have a strong opinion in either direction and wouldn't be qualified to express one. I'm a vulnerability researcher with a little bit of cryptography to me, so I tend always to err on the side of utterly skeeved out. I assume, regardless of what national standards bodies recommend, this stuff will all be run hybrid for the foreseeable future, but who knows?

I don't think anybody can easily shut down the argument that it's too early for lattice PQC to simply replace ECDLP cryptography.

There is not any reason to NOT run hybrid cryptography schemes right now, when the use case allows for it.

I do worry though that early standardization might lock us into a bad standard, and current PQC systems are too inflexible to allow for many use cases. The latter point means that if you want PQC, you might have to give up some features. E.g. multikey signature schemes, zero knowledge proofs, etc.

There is a very good reason: efficiency. Do you want to have servers carry an extra megabyte of otherwise-useless key material for each incoming connection? What about the extra ~100-1000 microseconds of CPU time for each key exchange?

Now multiply that by 100,000 live connections and 10,000 per second, and you'll see that there's a big problem here.

A lot of cryptography arguments forget that people don't place unlimited value on cryptography (or even security in a general sense). These algorithms are costly, and if they do nothing, should not be used.

Kyber768, which is what I see most people using for hybrid PQC deployments right now, has 1kB keys and is actually faster than elliptic curve cryptography.

4 kB keys, you mean, right? You have to store your private key, too. It's pretty fast otherwise, yes.

You have to store 1 private key. You store/transmit/interact with millions of other public keys, so the concern over size is somewhat asymmetrical.

Many protocols use an ephemeral private key, and protocols like TLS that don't today are moving toward ephemeral private keys faster than they are toward PQC.

The ephemeral key gets signed with your long-lived private key, but that's all your long-lived key is used for.

> There is not any reason to NOT run hybrid cryptography schemes right now, when the use case allows for it.

This is reasonable, but runs contrary to the stance taken by CNSA 2.0.

Gee, I wonder why.

Yeah the break of SIKE was pretty spectacular. The attacks on lattice-based crypto are less so. Still, the math is a lot more complicated than ECC or RSA, so it's plausible that it's also fundamentally broken, but we just haven't found out how.

At this point the only PQC algorithm I would trust with my data on its own is good old McEliece.

I'm not as convinced that the math on RSA is so simple compared to LWE cryptography. You'll see reputable cryptographers (well, one of them at least) confidently opining how we'll never break SHA2 and AES. I've never seen that for RSA or any ECDLP construction.

SIKE, sure, all bets are off.

The math for RSA is dead simple. But the theoretical foundations are not well established, no. It should be said though that SHA2 and AES also have unproven foundations for their security model. In a very strict sense both RSA and AES are equally vulnerable. But I think people would be more surprised if AES was catastrophically broken, and most surprised if SHA2 were, though there is little more than mathematical intuition underlying this.

Reply on news.ycombinator.com