Quantum is unimportant to post-quantum
blog.trailofbits.com
blog.trailofbits.com
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.
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.
"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.
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.
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).
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.
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.
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.
The ephemeral key gets signed with your long-lived private key, but that's all your long-lived key is used for.
This is reasonable, but runs contrary to the stance taken by CNSA 2.0.
At this point the only PQC algorithm I would trust with my data on its own is good old McEliece.
SIKE, sure, all bets are off.
I disagree.
First of all they are far more inconvenient. They keynotes and signature sizes are bigger. With Curve25519 ECC we can have 256 bit keys.
Secondly, flexibility is mentioned, but I think the last serval years have shown that flexibility is huge vulnerability in crypto systems.
Finally, I feel pretty confident that the NSA doesn’t know too much more than we do about RSA or ECC which have been studied, studied, implemented, and analyzed for decades in the open. I worry with Post-Quantum algorithms, that there is a good chance that the NSA knows far more about them than does the public cryptography community.
All the criticism of cryptographic agility that I have seen has involved an attacker negotiating a downgrade to a broken protocol. But if the protocol is not yet broken, then being agile isn't a concern, and if/when the protocol does become broken, then you can remove support for the broken protocol, which is what you'd be forced to do anyway, so a flexible approach just seems like a more gradual way to achieve that future transition.
Being distrustful of untested post-quantum algorithms is fair. But you can always double-encrypt a message with both classical and post-quantum algorithms, which requires an attacker to break both of them in order to decipher it. This guards against both short-term algorithmic weaknesses in our nascent post-quantum algorithms, as well as long-term threats to classical algorithms from hypothetical quantum computers.
Key sizes are larger, yes, but not show-stoppingly large; on par with secure RSA key sizes, which is tolerable. Kilobytes, not megabytes.
Consider this an additional data point, then: https://paragonie.com/blog/2019/10/against-agility-in-crypto...
In the years since I wrote that, several people have pointed out that "versioned protocols" are just a safe form of "crypto agility". However, when people say "crypto agility', they usually mean something like what JWT does.
What JWT does is stupid, and has caused a lot of issues: https://www.howmanydayssinceajwtalgnonevuln.com/
If you want to use JWT securely, you have to go out of your way to do so: https://scottarc.blog/2023/09/06/how-to-write-a-secure-jwt-l...
> But if the protocol is not yet broken, then being agile isn't a concern, and if/when the protocol does become broken, then you can remove support for the broken protocol, which is what you'd be forced to do anyway, so a flexible approach just seems like a more gradual way to achieve that future transition.
This makes sense in situations where you have versioned protocols :)
This doesn't work if you're required to support RSA with PKCS1v1.5 padding until the heat death of the universe.
Maybe something more like "cryptographic mobility" instead of "agility"? You can carefully decamp and move from one suite (versioned protocol) to another without changing all your software, but you're not negotiating algorithms and semantics on the fly.
And no, you shouldn’t be using RSA but they completely gloss over that we have very very good ECC standards that in no way seem to be suffering the same problem as RSA (ie needing to regularly increase the key size) which is why afaict everyone has pretty much switched to ECC signatures unless they have some legacy reason.
… or was there a quantum computer somewhere and it was just kept hush hush, hence the push for PQ?
The answer turns out to be: it doesn’t matter if there is a quantum computer! The set of PQ algorithms has many other beneficial properties besides quantum resistance.
So there may not be quantum computers now. But if there’s going to be in 20years we need our crypto to be resilient now.
That said, the entire field is still so far from a seriously useful QC that I still wouldn’t bet there’s a secret one somewhere in some government lab. Those are my two cents, and I may be wrong of course.
There is a viable pathway to low error rate, scalable quantum computers on a less than 10 year time horizon though.
The basic idea is that they use scanning probe microscopes to create structures on a silicon surface with atomic precision, which can then be manipulated by the surrounding chip as a solid-state qubit. You still need error correction, but it ends up being a small constant factor rather than combinatorial blowup.
Full disclosure: I’m fundraising a startup to pursue a different manufacturing process that would enable the same type of quantum computer, but with nitrogen vacancies in diamond instead of silicon (and therefore still higher reliability).
One way or the other, highly reliable quantum computers are right around the corner and are going to take a lot of people by surprise.
This is also something that people outside academia apparently don't understand. Peer review doesn't tell you anything about the validity of the science. It only ensures the methodology was correct. The original Pons & Fleischmann paper passed peer review and was published in the Journal of Electroanalytical Chemistry. It only got retracted after other people tried and failed to reproduce it. If you want to know whether science is legit or not, look out for reproduction by independent actors - not peer review.
In this case, three separate labs have replicated this work. It's solid.
> California-based startup PsiQuantum was given an “inside run” to a controversial $1 billion investment by Australian taxpayers as the only company that government engaged with in a thorough due diligence process.
Which tells you one thing…
> This variety of different trade-offs gives developers a lot of flexibility. For an embedded device where speed and bandwidth are important but ROM space is cheap, McEliece might be a great option for key establishment. For server farms where processor time is cheap but saving a few bytes of network activity on each connection can add up to real savings, NTRUSign might be a good option for signatures. Some algorithms even provide multiple parameter sets to address different needs: SPHINCS+ includes parameter sets for “fast” signatures and “small” signatures at the same security level.
I also think the article is overly optimistic claiming that ECC is “hard” because of the need for careful curve selection (even though we have very good established curves), but I find it hard to believe that PQ algorithms are immune to parameter selection problems and implementation challenges.
[0] https://web.archive.org/web/20110401080052/https://www.cdc.i...
[1] https://news.ycombinator.com/item?id=33925383 I wrote about this "Dahmen-Krauß Hash-Chain Signature Scheme" (DKSS) algorithm previously in a comment a couple of years ago
To be clear my comment is specifically only relating to signature schemes, not encryption.
> The state is enormous
The scheme I linked to points towards efficient "pebbling" and "hash chain traversal" algorithms which minimize the local state required in quite a fascinating way (e.g. see https://www.win.tue.nl/~berry/pebbling/).
> tracking state across components and through distribution channels
Assuming you have reliable ordering in those channels I don't see how the stateful nature of such schemes makes it hugely more complex than the essential hard problem of key distribution.
Lattice-based algorithms are around 1kb.
If there were a quantum computer somewhere, or close to one, it would be reasonably likely for it to be secret.
I look at the history of crypto in the mid to late 20th century for example. Small groups in the Allies and the NSA and etc. had certainly more knowledge than was public by a wide margin, years to decades.
Like the sibling comment points out, you're overstating the weakness of DES as well.
I assume they mean the hidden subgroup problem for abelian groups? Later they mention short integer solutions (SIS) and learning with errors (LWE), which by my understanding both rely on the hardness of the shortest vector problem, corresponding to the hidden subgroup problem for some non-abelian groups. I haven't read into this stuff for a while, though
If information remains interesting to an adversary long-term, they can always archive classically ciphered text and apply future hardware and algorithmic advances to cracking it.
This is why "post-quantum" cryptography may well be "quantum cryptography". QC must be broken at the time of transmission for an adversary to obtain any information at all. If you're trying to communicate something that will remain sensitive long-term, with QC you aren't betting against the future producing something surprising.
QC already works, it's getting cheaper and faster, and more network friendly. It's not ready for the internet yet, but it's getting there. We don't need it for information that changes every few years, like credit card info, but that's not all people use cryptography for, even today.
In all seriousness, QKD also has huge SNR problems over long range. QKD is really a layer 1 protocol that needs you to entangle qubits far away from each other, and that relies on having a very clean physical layer. You can sort of do it over short-range fiber right now with a known-to-be-direct connection, but any other medium is still off the table. Once you have done the QKD layer 1, put any protocol you want on top of it.
So, no, it's not a viable replacement for anything.