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.
The quantum vs current computing thermal needs are not linked directly to entropy. For current cryptography, solving faster is more energy by its linear relation nature, quantum is in parallel. It is possible quantum computing could be less wasteful in the future, but currently quantum computing is highly inefficient thermally.
And current computing can solve for the private key, just take a few days of heavy computing
If your assertion were true, why would there be thousands of mathematicians focusing on building quantum safe encryption algorithms? You understand this situation better than scores of PhDs?
Good question. I have no answer to that. Maybe someone points a flaw in my reasoning…
The flaw in your reasoning is that you’re running under the assumption that quantum cracking uses the same amount of energy as conventional and that you have a higher level of understanding than people that are working on this professionally.
You’re acting like you have some gotcha argument against billions of dollars of investment and a huge amount of institutional knowledge. If the problem was as simple as you’re trying to make it, what would be the point of pouring so much time, money, and energy into developing quantum cryptography?
So, youhave nothing? Honestly disappointed.
Your analogy is wrong.
Here’s a silly example to highlight why.
Let’s both stand together on the equator. You walk forward all the way around the earth and stop five feet behind me. You claim that it’ll take me just as much energy to meet you there. But it doesn’t, I just turn around and walk five feet.
Quantum computers, when when brute forcing, do it differently. They take a different path. That’s why they’re so much better at it.
I don’t think I used any analogy at all. Point is, when you have to reduce entropy in one place you have to increase it elsewhere. There’s no shortcut. It’s thermodynamic 101
That’s not the point. Literally doing anything increases entropy. That’s called heat. And it has literally nothing to do with the efficiency of specific approach to breaking encryption.
For most of us, thinking random thoughts about it while in the shower is probably not the most effective way to gain an understanding of the mathematical details of quantum mechanics.
I’m not interested in detail. The question is: Is my claim about thermodynamics valid. If it is, the inner workings of quantum computing are irrelevant.
With regards to extracting the private key from the public key, to my knowledge there is shors algorithm that runs in polynomial time on a quantum computer that solves integer factorisation.
Solve integer factorisation in P and you break RSA in P. I believe there are similar P algorithms that run on quantum computers for the discrete logarithm problem and elliptic curve discrete logarithm problem.
In this sense, if you scale quantum computers resources enough you break modern asymmetric cryptography.
With regards to breaking AES: Quantum computers halve the security. So 256 bit security goes to 128 bits. Still secure.
AES 128 goes to 64 bits of security. Hmmm maybe not secure anymore. Have a read of post quantum cryptography and shors algorithm to see what im on about
EDIT: added important details
Edit 2: so so many typos
there is shors algorithm that runs in polynomial time on a quantum computer
I’m not claiming you can’t do it faster. I’m claiming it’s impossible to skip the related fundamental energy requirements.
Energy requirements scale exponentially on a polynomial time algorithm? That doesnt make sense. I admit however I have only studied quantum computers in relation to what they can do, not how. But I hope what I am saying makes sense.
I admit however I have only studied quantum computers in relation to what they can do, not how
I’m not an expert in quantum computing. The whole point of this thought experiment is to skip all all the mechanics and make an argument based on general fundamental thermodynamic limitations.
Not a physisct, so I dont known how much scaling of quantum computers can actually be done
Why is a private key low entropy and a public one high entropy? Are you talking about Shanon entropy? If so, over what distribution?
Also, as far as I know from the time I was interested in QC, we already can break RSA, you can actually run it on actual quantum computers, although with fewer qubits. That’s why we have quantum safe cryptography.
I really don’t see how any of this violates the second law.
Public key must be high entropy as its sole purpose is to scramble known information, from perspective of a person who doesn’t have a key, scrambled information is a pure random noise.
Private key has to be low entropy, since it has information necessary to revert scrambling. High entropy + information how to undo it isn’t really high anymore.
Are you talking about Shanon entropy?
I’m not deep enough into physics to know what Shanon entropy is. I use definition of entropy as amount of hidden/unreadable information.
Shannon entropy is a concept from information theory. It is mathematically analogous to thermodynamic entropy, but not the same thing. So you’ve identified the Shannon entropy of public and private keys, but I’m also wondering how that relates to their thermodynamic entropy in order for the 2nd law to apply.
It’s relatively easy for modern consumer desktop hardware to crack old encryption in reasonable timeframes.
Time - that’s the limiter. How long you’re willing to wait for a solution.
If quantum computing can apply orders of magnitude greater performance than current systems, the same increase in cracking applies.
Not all encryption is equally complex - it’s all about how long it takes. The end.
Probably a really dumb question, but… it’s been decades since plenty of sites and programs started blocking you for x amount of time if you enter the wrong password x amount of times… isn’t there any security like that against brute-forcing passwords on servers or whatever the brute force runs against?
In most cases the real risk is someone getting access or intercepting the encrypted data. If they have the raw data, there aren’t any other protections in place to prevent brute force attacks.
Similarly, that’s why groups like the FBI will clone devices (like phones) to bypass brute force protections.
When your data is secured by password, the security is only as good as that password. And people are notoriously bad at making strong passwords
Have you considered control, alt and delete?
How often has that successfully broken cryptography for you?
Literally every time
Since quantum computers are using superconductiv materials, do their computations actually consume energy? Obviously their refrigeration uses a bunch of power, but not the chips themselves I think
