I read that traditional crypto schemes based on prime factorization can theoretically be broken by quantum computers but that lattice based crypto cannot.
Question:
Why the difference?
I don’t really understand Shor’s algorithm, but was simplistically assuming it had to do with just testing many combinations rapidly. It seems that lattice based schemes could be broken by the same type of system if it was that simple. So, I assume it’s not as simple as just trying many combinations rapidly?
Note:
I read some basic info on lattice based crypto, but I’m not a mathematician so I have limited understanding. I think I get what a lattice is (n independent vectors) and the basic thing I read mentions encryption/decryption as shifting lattice points random amounts such that the resulting point is still closest to the base lattice point (versus closest to a different lattice point) but not exactly the same as the original.
The laymen’s explanations for quantum computing describe it as trying all possibilities in parallel, but that’s not really how it works. For the real explanations, well, how many years of quantum mechanics have you studied?
Note that the quantum breakable (in theory) cryptos are based on things like factoring and discrete logarithm.
These problems appear to much simpler than anything truly NP-Hard which is what you really want. I.e., something based on Satisfiability of Boolean Equations, Graph Coloring, Knapsack, Hamiltonian Path, or one of the zillion equivalents.
Some of the early Public Key Crypto systems proposed were based on some of those. But … Adi Shamir and others are very smart and were shooting these down 1, 2, 3 like that.
One difficulty is that there are easy to solve instances of otherwise NP-hard problems. (E.g., a tree is trivially two colorable.) And you don’t want those in your crypto. You want only the hard instances. How can you tell which are the hard instances to base your crypto on? Um, solve P vs. NP or something a lot like it.
So you guess as to what’s hard. Then Adi comes along and you have egg on your face.
Factoring and Discrete Logarithm don’t seem to be so full of holes. Things are somewhat uniformly the same. But still note that are lots of rules of good numbers to choose for your prime factors for RSA. And we don’t know all the good rules yet to be found.
Some suspect this uniformity might be tied to why Shor’s algorithm works in these cases, but not others.
As to lattices. … Well, they’re somewhere in between. Apparently not so easily knocked down by the Ari types but not having the properties that Shor’s Algorithm relies on.
It’s quite hard to compare things that are so different.
I’m not worried about quantum computers breaking the Internet. Qubits don’t scale up well. It’s one thing to make a 4 qubit computer, it’s another to make a 4k qubit computer. Thermodynamics doesn’t play nice with so many quantum things. Ask Schroedinger’s cat.
Here are a bunch of “experts”, and a Prime Minister, attempting to explain quantum computing briefly:
The “real” explanation seems to be “choreographed amplitudes”, although some said “trying all possibilities in parallel”. But if you think about it, perhaps in the context of Shor’s algorithm to be less abstract, the difference between those two “explanations” is just semantics. I think these “experts” simply feel less ridiculous pointing at a physical computer and saying “choreographing amplitudes” rather than “trying all possibilities in parallel”. Something is wrong with the theory: quantum computers are not scaling up to a practically significant number of qubits. I think neither way of phrasing what is going on is happening. Although someone please change my mind: provide links showing quantum computers are going to be a real useable thing, hopefully sooner rather than later. (I think I might be able to get a lucrative job programming them during the period when few people have learned how to program them.)
I can think of plenty of problems that could be solved by “trying all possibilities in parallel”, but most of them can’t be solved by a quantum computer. Thus, what it’s doing can’t be just “trying all possibilities in parallel”.