Comment by ninjahawk1
15 hours ago
Very good breakdown, if I’m understanding Grover’s algorithm correctly, are you saying essentially that it would require either too much compute or too much time to be feasible but is still much more realistic than a brute force attack?
If that’s the case, would the time eventually be basically irrelevant with enough compute? For instance, if what’s now a data center is able to fit in the palm of your hand (comparing early computers that took up rooms to phones nowadays). So if compute is (somehow) eventually able to be incredibly well optimized or if we use something new, like how microprocessors were the next big thing, would that then be a quantum threat to 128-bit symmetric keys?
I am not an expert, but while you are correct that a fast enough traditional computer (or a parallel enough computer) could brute force a 128 bit key, the amount of improvement required would dwarf what we have already experienced over the last 40 years, and is likely physically impossible without some major fundamental change in how computers work.
Compute has seen in the ballpark of a 5-10 orders of magnitude increase over the last 40 years in terms of instructions per second. We would need an additional 20-30 orders of magnitude increase to make it even close to achievable with brute force in a reasonable time frame. That isn’t happening with how we make computers today.
> That isn’t happening with how we make computers today.
Keep here in mind that computers today have features approaching the size of a single atom, switching frequencies where the time to cross a single chip from one end to the other is becoming multiple cycles, and power densities that require us to operate at the physical limits of heat transfer for matter that exists at ambient conditions.
We can squeeze it quite a bit further, sure. But anything like 20-30 orders of magnitude is just laughable even with an infinite supply of unobtanium and fairy dust.
You don't need to keep shrinking features. Brute forcing is highly parallel; to break a key within a certain time frame all you need is a large enough quantity of chips. While it's in the realm of science fiction today, in a few centuries we might have nanorobots that can tile the entire surface of mars with processors. That would get you enough orders of magnitude of additional compute to break a 128 bit key. 256 bit would probably still be out though.
6 replies →
The calculated DW cost of the quantum attack is 2^104 (with conservative/optimistic assumptions and ignoring the physical cost of a single logical gate), which is "much more realistic than a brute force attack" in the same sense that a 128-bit brute force attack is much more realistic than a 256-bit brute force attack.
None of those are remotely practical, even imagining quantum computers that become as fast (and small! and long-term coherent!) as classical computers.