Live data from Hacker News

Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

words.filippo.io

51–60 of 116 posts

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#51

Earlier quoted context omitted.

> 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…

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 bi…

The power and heat are the issues for that, though. Think about how much energy and heat are used/generated in the chips we have now. If we tiled out those chips to be 20 orders of magnitude larger… where is the heat going to go, and where is the energy coming from?

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#52

Earlier quoted context omitted.

> 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…

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 bi…

Classical brute force is embarrassingly parallel, but Grover's algorithm (the quantum version) isn't. To the extent you parallelize it, you lose the quantum advantage, which means that to speed it up by a factor of N, you need N^2 processors. The article discusses this in detail, and calculates that "This means we’ll need 140 trillion quantum circuits of 724 logical qubits each operating in parallel for 10 years to break AES-128 with Grover’s."

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#53

I wonder when the OpenSSH developers will change their stance on Ed448.

I'm not familiar with their stance, but bear in mind the costs of introducing new key type on the ecosystem, and on maintenance of SSH implementations.

Imagine if we would've had the same hesitant cost-first reasoning about Ed25519, and then again about ML-KEM and SNTRUP.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#54
Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#55

Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

The only caveat is that AES is not necessarily a black box. It's possible there may be hidden structure to take advantage of, but if there is there's no reason to suspect it's one that's amenable to a quantum speedup.

As far as the Grover speedup goes, it's already optimal. Requiring O(sqrt(N)) queries is the proven lower bound for unstructured search.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#56

Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

Yes and no.

Grover's algorithm is provably optimal [0]. No quantum algorithm will ever find an n-bit key by queries to any reasonable sort of oracle faster than Grover's algorithm, and Grover's algorithm is way too slow to be a serious problem.

But symmetric ciphers are not black boxes. They're mostly built on some variant of a Feistel network, which is a very nice construction for turning a messy function into an invertible function that, in a potentially very strong sense, acts like a cryptographically secure permutation.

When I was in grad school, one project I contemplated but never spent any real time on was trying to either generate a real security proof for quantum attacks on Feistel networks or to come up with interesting quantum attacks. And there is indeed an interesting quantum attack against 3-round Feistel networks [1].

This is interesting, because, depending on what sort of security is needed, three or four rounds of Feistel network are sufficient against classical attack [2].

Now ciphers like AES have many more than 3 rounds, so hopefully they're fine. But maybe they're not. My intuition is that there is probably a reasonably small n1 and a reasonably small n2 >= n1 (probably constants, maybe logarithmic in numbers of bits) for which there is no quantum algorithm that can break symmetric crypto given classical query access even to the round functions (n1) or quantum query access to the round functions (n2) [3], but I'm not aware of any proof of anything of the sort. And my intuition definitely should be be trusted fully! (Maybe, even if I'm wrong, there is still a number of rounds that is sufficient for security against query access to the entire cipher.)

[0] The classic result is https://arxiv.org/abs/quant-ph/9701001 and there are newer, more exact results, e.g. https://arxiv.org/abs/0810.3647

[1] https://ieeexplore.ieee.org/document/5513654

[2] https://en.wikipedia.org/wiki/Feistel_cipher

[3] It would be extremely cool if someone built quantum computers and networks and storage such that two parties that don't trust each other could actually communicate and exchange (interesting [5]) qubits. I've written some fun papers on the possible implications of this. If we ever get the technology, then it might actually be meaningful to consider things like chosen-quantum-ciphertext attacks against a classical symmetric cipher. But that's many, many years away, and, in any case, an attacker will only ever get to do a quantum query attack against a cryptosystem if a victim lets them. [4] Otherwise all queries will be classical.

[4] Or in very complex settings where there is an obfuscated black box, for example. This may be relevant for zk-snarks or similar constructions.

[5] I don’t consider the optical qubits exchanged in commercial devices that supposedly implement quantum key distribution to be interesting. To the vendors of such devices, sorry.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#58
post #56

Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

Yes and no. Grover's algorithm is provably optimal [0]. No quantum algorithm will ever find an n-bit key by queries to any reasonable sort of oracle faster than Grover's algorithm, and Grover's algorithm is way too slow to be a serious problem. But symmetric ciphers are not black boxes. They're mostly built on some variant of a Feistel network, which is a very nice construction for turning a messy function into an in…

I really appreciate the links, this'll give me a lot to read about.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#59

Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

Fun fact: Grover's algorithm is a rare example of an algorithm that was proven optimal before it was invented.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#60
post #14

encryption is not ever to be considered impossible to break. every encryption scheme has at least one way to be decrypted. fidelity of information is one use of encryption, if you apply the solution and get garbage, something is wrong, somewhere. occultation of information is another use, that is commonly abused by extending undue trust. under the proviso that encryption will eventually be broken, you cant trust encr…

> encryption is not ever to be considered impossible to break

One-time pads [0] are actually impossible to break, but they're pretty tricky to use: you must never ever reuse them, they must be truely random, and you need some way to share them between both parties (which isn't that easy since they need to be at least as large as all the data that you ever want to transmit).

[0]: https://en.wikipedia.org/wiki/One-time_pad

Post reply on HN