Here's the UK Government stating—like NIST did—that 128 bit keys are enough against quantum computers. No need to migrate to 256 "because quantum".
https://www.ncsc.gov.uk/whitepaper/next-steps-preparing-for-post-quantum-cryptography#section_4
For those of us following along at home, can you provide a little more context? I am also curious to know if you agree that 128 bits is enough. I always thought 256 was the greed upon number of bits.
@dangoodin @filippo 128 bit is enough, as long as you are not defending against adversaries with access to a Dyson swarm. 256 bit is enough for defense against a Kardashev III civilizations, with room to spare.
@sophieschmieg @dangoodin @filippo "secure until computers are made of something other than matter and occupy something other than space"
@sophieschmieg @dangoodin @filippo though 128 bit symmetric seems a bit iffy on security margin to me, given that 256 bit isn't that much slower.
@ryanc @sophieschmieg @filippo
My very foggy and distant recollection is that quantum computing effectively cuts the number of bits in symmetric encryption by half. Am I just dreaming that, or is that right? If so, seems like cutting 128 in half wouldn't be enough entropy. Sorry if I'm completely wrong on all accounts here.
@dangoodin @ryanc @filippo that's what Filippo is commenting on. You have two different attacks that are enabled by a quantum computer: first is Shor's algorithm, which breaks RSA and elliptic curves on polylogarithmic time, which means increasing key sizes is of very limited use.
The second algorithm is Grover's search, which is a generic brute forcing algorithm that takes O(√n) time (classic brute forcing is O(n)). That'd suggest that you need to double the key size (since n = 2^k, where k is the key size). But this is only true for an asymptotic analysis, and does not take into consideration the structure of the algorithm. Brute forcing is lazily parallel, and is the best case scenario for scaling. Meanwhile Grover's search cannot be parallelized at all, the entire computation has to happen on a single quantum computer. We couldn't even build a classical computer that by itself can handle that large of a computation, much less a quantum one.
@sophieschmieg @dangoodin @ryanc @filippo do we think Grover is the last word on symmetric-relevant quantum algorithms? How well-explored is this algorithm space?
@neilmadden @dangoodin @ryanc @filippo There is a proof that you can't do better than O(√n). It doesn't necessarily say anything about the parallelization opportunities, but it shows that fundamentally quantum computers aren't magic NP oracles.
@sophieschmieg @neilmadden @dangoodin @ryanc We do have a proof that Grover doesn't parallelize beyond naive key space partitioning. I am not familiar enough with the space to tell how likely an AES-specific quantum algorithm is, but I think Grover is optimal for black-box functions.
@filippo @sophieschmieg @neilmadden @dangoodin @ryanc
Do you have a pointer to the proof (or a way of searching for it: Grover does trivially parallelize if you can transfer qubits between the various parallel computers, and I don't know how the setup of multiple quantum computers with only classical links between them is called)?
@filippo @sophieschmieg @neilmadden @dangoodin @ryanc
Huh, I don't know how I got the notion that you can trivially parallelize it if you pass qubits between the computers; this paper seems to prove _that_ impossible. Thanks.
@robryk @filippo @neilmadden @dangoodin @ryanc I think you'd violate the no cloning theorem, unless you want to teleport the qbits.
@sophieschmieg @robryk @filippo @neilmadden @dangoodin @ryanc … but teleporting would still mean that those states are unique… because no-cloning. (Just completing your argument.)
@sophieschmieg @filippo @neilmadden @dangoodin @ryanc
For some stupid reason I thought that you can do a few "steps" of Grover in parallel (as in starting from not copies, but entangled copies of the previous step). This is not trivially possible though, and the paper @filippo pointed out claims to prove that it's impossible (as in, that oracle search with a quantum oracle has to be at least sqrt(search space size) oracle invocations deep).
@robryk @sophieschmieg @filippo @neilmadden @dangoodin @ryanc Hey, that's not that stupid actually! ;-)
Indeed some algorithms can be done "in hybrid" with different parts being quantum and others not. But not only is quantum cloning one problem, but even if you can do a "clean cut" like measuring intermediate results, doing some non-quantum step and then doing another round of quantum, this often ends up being less efficient, especially with compounding errors IIRC.
@robryk @sophieschmieg @neilmadden @dangoodin @ryanc https://arxiv.org/abs/quant-ph/9711070