WRT Shor resistant crypto: which is more likely

Question

In NIST’s ‘competition’ to obtain new public key crypto which resists Shor’s algorithm (aka ‘post quantum cryptography’), two algorithms to make it into the third and fourth rounds have been catastrophically broken (Rainbow over a weekend on a laptop and SIDH/SIKE in an hour on a single core), while others have been shown to have less security than required by NIST (https://zenodo.org/record/6412487#.Y-wEkS-IafA).

Meanwhile, no one has been able to create a single logical qubit stable enough for a cryptographically relevant quantum computer.

The question I have is, what is more, likely to happen first: Will we have a cryptographically relevant quantum computer capable of breaking the weakest (wrt Shor’s algorithm) classical public key systems (i.e., elliptic curve based crypto), or will we be able to break these relatively unstudied new NIST algorithms?

Answer 1

we’ll be able to break these relatively unstudied new NIST algorithms?

Without getting baited into a response regarding this, I'll just say that there are generic techniques to take two encryption schemes, and create a third encryption scheme that is secure if either of the "input" schemes are secure.

This is to say you can build cryptosystems that are both PQC, and as secure as EC cryptosystems. There are some arguments against doing this (roughly implementations get to be more complex, as well as CA's jobs might be harder), but unless you want to bet the future on cybersecurity on "we just can't build quantum computers" for some reason (even though there has been some \$20b in funding various governments have been offering in recent years), we might as well do something proactive.

I would encourage you to view the NIST process via a different lens. The real flaw was that the cryptanalysis occurred so late in the process. We need ways as a community to encourage more cryptanalysis of schemes, so vulnerabilities are discovered sooner. I'm no cryptanalyist, so can't speak to how this should occur, but I'll just point out that encouraging people to post

• "full" implementations of schemes, with
• explicit parameter sets

probably helps (it gives cryptanalysts a "fixed target" to attack). The easiest way to encourage other cryptographers to do this kind of thing is either to

• host a NIST-type competition, or
• have there be some financial incentive (for example current FHE research can be driven by corporations trying to build products).