The whole promise is that reversible computation is theoretically free (in quantum information theory) , quantum computer can exploit it by using quantum superposition to brute force 256bit key (and larger) in a single computation cycle.
There’s a massive fundamental flaw in the reasoning behind this.
It’s the second law of thermodynamics - entropy always increases. While computation is free, reversal of entropy isn’t. What we’re being promised is a 21st century version of perpetual motion machine.
Additional explanation:
Think about private key as low entropy, and public key as high entropy. Owner of the private key has cheat code in the form of missing information which allows reversing the entropy of public key.
However in order to break the cryptography you have to reverse public key back into private key without having access to it. The regualr way is to search for flaws in the cryptography scheme that allow reasoning about missing information and consecutively - private key recovery.
But if you do a brute force attack you are 100% forced to pay full thermodynamical price of reversing the entropy. And 2^256 is way, way more than you could ever afford. Even Planck scale values multiplied by that number grow into universe size and beyond.
In summary, quantum computing can skip time component of brute forcing a key, but it can’t skip the energy costs. So it will never happen.
I think you’re almost right about the high level principles, you’ve just forgotten that entropy scales as the log of the combinations not linearly.
So the entropy of a 128 bit key is not 2^128, it’s just 128 and therefore the fundamental limit on the cost required to recover it that you’re talking about is very small.
See landauer limit (which isn’t quite the same thing since it’s about irreversible computers which some quantum computers might not be, but gets at the idea of there being an energy cost to have information)
I believe the specifics of your thoughts about entropy of public vs private keys is also incorrect but not necessary to the core of what you’re saying.
Keep in mind that the Landauer limit applies to the number of operations (specifically number of overwrites), not key size, and if you have no attack which is more efficient than bruteforce then bruteforce itself is directly limited by key size.
That is, for AES128 it actually is 2^128 that sets the energy limit. For algorithms like RSA the limit is below their key size, for RSA2048 it is somewhere above 2^128 at the last estimate because of attack algorithms like sieves. Assuming classical attack algorithms.
I agree, I was trying to respond without getting too much in the weeds. The argument being made was that the entropy (information content) of the key itself is the problem. I was saying that isn’t true because entropy is defined differently.
But there is a lower bound for any algorithm who’s output produces something with a certain amount of information, and that’s the information->energy cost of that output. The specifics of the algorithm being irrelevant. I believe even with something like thermodynamically reversible computing you still pay the cost at the end for storing your result? (Which gets into one of the most mind blowing things I remember from stat mech about Szilard engines. Essentially that if I know the microstate of a system [or even a macrostate I believe?] I can slowly burn that information to extract energy from the system equal to the information I had)
You’re right that in the classical case with irreversible computation you can argue that there’s a thermodynamic impossibility to the brute forcing based on the Landauer limit.