… 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.
> 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…
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.
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.
> 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.