This isn't true - only methods based on Discrete Log are at risk, which includes RSA and ECC, but there are a lot of PK algos that are not at risk, like NTRU.
Here's a bunch of stuff related https://en.wikipedia.org/wiki/Post-quantum_cryptography
But if you prefer, you could imagine that I said "all modern PK crypto [that is actually in use today] is broken". Because, at the end of the day, that's all that really matters.
[As an aside, for RSA the security is provided by the hardness of factorisation which also breaks under QC attackers, not discrete log (it's discrete log for DH, and EC discrete log for ECDH).]
Classic McEliece (https://classic.mceliece.org) was created in 1978 and is in the 2nd round of NIST's PQ-crypto contest ( https://csrc.nist.gov/projects/post-quantum-cryptography/rou...).
The PQCrypto conference started 13 years ago: https://pqcrypto.org/conferences.html
Chrome ran large scale experiments with NewHope support 3 years ago: https://security.googleblog.com/2016/07/experimenting-with-p...
I wrote a decently cited paper summarizing all this when I worked in quantum computing research around 2005, on arxiv. Track it down if you’re interested. I’ve followed the field for decades, giving talks once in a while on it. So I do know a bit of the details.
The computational power of QC is very well studied. It is certain that it cannot crack certain (most) problems any faster than a classical computer. Thus algorithms not isomorphic to the few problems QC is better at are just as secure on both classical and quantum computers. There is consensus on this - there is no question about it.
>all modern PK crypto [that is actually in use today]
NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms. NTRU is also used in many commercial products from chat to relays.
Other non DLP methods are also used in commercial products and standards.
But is it not the case that the original Shor algorithm was specifically about using periodicity for integer factorisation (and the wiki page for "RSA problem"[1] also refers to integer factorisation, not discrete log).
> It is certain that it cannot crack certain (most) problems any faster than a classical computer.
Yes, I was already well-aware of that. My point was that the overwhelming majority of PK crypto used today depends on the hardness of problems that are exponentially accelerated by QC algorithms.
> NTRU is an IEEE standard, and is in wolfSSL, which is on many platforms.
Okay, maybe then it has some non-academic use. But the overwhelming majority of PK crypto in use today (TLS, PGP, the vast majority of E2EE systems) is not secure against quantum attackers. Can we agree on that at least?
Periodicity is discrete log.
Discrete log is defined as given a mathematical group G, a generator g in G, and an element h in G, find the power of g that gives h. This is a logarithm, over a discrete set, a finite group. This is equivalent to finding the power of h so h^r = 1, since given either, the extended euclidean algorithm gives an efficient way to get the other number. This number r is called the order of h, and there is no (in general) known classical efficient algorithm to do it.
This can be easy or hard, depending on the group.
Shor period finding is taking a the integers mod N (which is a group, called an abelian group, about the simplest class of groups), and an integer a, and finding the power r of a that is so a^r is 1 mod N. This is exactly the discrete log problem. You found the order of the element h.
Shor is a special, easy case of the more general problem - he solves it efficiently for Abelian cyclic groups, but it has been extended to many, many other groups.
In fact, researchers realizing this was exactly the general problem Shor solved is why all discrete log problems are vulnerable to QC. His method of using a quantum Fourier transform (which has a nice generalization to groups) to find period (which FFT does nicely) is directly applicable to any group. Shor is not some odd outlier algorithm; it is exactly the core (and almost the only) algorithm QC is exponentially faster at.
>But the overwhelming majority of PK crypto in use today (TLS, PGP, the vast majority of E2EE systems) is not secure against quantum attackers. Can we agree on that at least?
Yes, but that is a far cry from your original claim. We only use those systems because they are not widely broken, and like all crypto, if one gets broken, we simply replace. This is not new.
Each is easily replaced by algorithms that quantum cannot touch (unless classical can too), so much so, that many places already use QC resistant algorithms to prevent nation-states messing with them.
Based on your statement (I don't recall offhand), it might be said that it is widely believed RSA and ECC algorithms are vulnerable in a world where quantum computing is plausible. The safety of other systems would require a more rigorous proof; the absence of known vulnerability does not imply safety.
I am not an expert in this field, but the understanding I have from the last time I spent an afternoon reading about it might be summarized as:
* Known/Suspected vulnerable systems use "classically-hard" problems with vulnerability based on small key (or subkey) size.
* Most of the 'theoretically more secure' systems make the working set size large enough, and complex enough, to eclipse the scope of stable quantum computers.
* Thus, the two attack vectors to consider for 'post quantum' cryptography are currently unthinkably large systems or weaknesses in algorithms that allow for attacking a subset which does fit within a quantum system.
If my understanding/memory is incorrect updates would be very helpful.
And many systems do not reduce to this.
RSA's security is based on the presumption that factorization is hard, which is a different problem than finding the discrete log. To attack RSA you would use Shor's algorithm, and to attack ECC you would use Grover's.
See page 2 of this paper:
To attack ECC it is directly discrete log, where quantum is exponentially faster than classical.
Grover reduces unstructured search from O(N) to O(sort N), only a quadratic speedup, insufficient to weaken crypto more than 1 bit out of a key length, which is too weak to be a threat.
Page 2 of your link does not state how QC attacks problems; it dies say ECC is discrete log, though.
Both systems break precisely because QC solve DLP in these cases exponentially faster than classical, and this is all that’s needed.