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 @filippo
It shows that quantum computers can't magically find a value accepted by an _oracle_, but doesn't say anything about finding a value accepted by a program, and so also about BQP vs. BPP, NP or coNP though (even if many (most?) people think it's very likely that BQP is not larger than NP).
