I don't keep tabs on quantum computing at all, but I get the distinct feeling that it isn't going to turn into anything important. Is there any reason to believe this will be relevant to regular developers in the next 20 years?
If quantum computers happen (which is still a big if) then mostly two things will happen:
1. Cryptographers will have to switch many of their algorithms and things like TLS will get a bit slower and will need a bit more data transmitted.
2. It's interesting for science, e.g. for simulations.
For the regular dev I'm pretty sure it won't have any meaningful impact.
Also even if quantum computers happen they won't be on our desks any time soon. It'll probably more like "you can rent a QC for specialized tasks in the cloud, but it will be relatively expensive and if you don't really need one you'll use something else".
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.
I'm not aware of any symmetric cipher that the industry in broad consensus would consider "better" than AES-256.
As to whether it will be usable within 20 years, time will tell.
[0] - https://www.nature.com/articles/nature23879
[1] - https://ai.google/research/teams/applied-science/quantum/ - see 'Near-Term Applications'
I don't really know much about the topic but my understanding is that it could potentially be more dense then the theoretic limit of current transistor sizes.
Science fiction has hypothesized about quantum computing that involves macroscopically-sized bits of carefully constructed matter running a number of qubits best described with scientific notation, but it's not clear how one would set up problems or read anything out of such a thing.
Current sizes of quantum bits: cavities are cm to mm scale; transmons and photonics can be much smaller, but nowhere near the size of modern transistors; ions need to be trapped in something and usually the scale is not better than the other options.
There is the hope that qubits can be made in silicon and use lithographic technologies, but then at best we will reach the density of current CPUs (but such a thing is science fiction at the moment).
Wait.. patent pending. There's probably an unreasonably large some of money to be made being able to sell that label to unwitting trend-hoppers.
I think the biggest change will be that quantum computing can really kill at machine learning, upping the numbers of nodes in neural networks with an exponential relationship to the number of qubits.
It might turn neural nets into a neat toy that Facebook uses to show us sort-of good ad predictions to something that really cuts into a wide range of things that only humans are capable of doing.
This is not true. Some parallelizable tasks will benefit from massive speed ups but most won't.