5 ms·
What is the state of PQ symmetric crypto? My layman's understanding is that 128 bit AES is known to be broken by a quantum computer and that 256 AES may be OK b
by ls612 1y ago
What is the state of PQ symmetric crypto? My layman's understanding is that 128 bit AES is known to be broken by a quantum computer and that 256 AES may be OK but that isn't certain? Is this an additional vector for the "harvest and wait" strategy in the future?
- twiggers 1y ago128-bit AES is fine. To run Grover’s algorithm against it you’d need to cover the moon with qubits.
- ziofill 1y agowhich algorithm are you referring to?
- dist-epoch 1y ago> My layman's understanding is that 128 bit AES is known to be broken by a quantum computer Weakened, not broken. Quantum computers turns 128 bit AES into 64 bit equivalent. Which will still be extremely difficult for quantum computers due to the large computer size/number of steps required.
- SAI_Peregrinus 1y agoAnd it's 64-bit equivalent in a way that's inherently impossible to parallelize, so 2^64 sequential quantum operations. Those operations are much, much slower than classical ones.
- cyberax 1y agoYou can trivially parallelize Grover's search by assigning each quantum computer it's own search space.
- upofadown 1y agoYes, but then you give up the advantage that Grover's gives you in the first place. The advantage is sqrt(n). You are reducing n by parallelizing.
- cyberax 1y agoWell, you get sqrt(n / N) as a result. It works like any other parallel computation. E.g. if you have 256 quantum computers, then each one of them needs to search only 60 bits of the key space to crack a 128-bit key (each one of them will only need to search 2^120 keys). It's not really going to make much difference with near-future quantum computers. Especially since Grover's algorithm _has_ to complete all the 2^60 steps to produce a reliable result, you can't just run a quantum computer for a while, stop it, and then restart it.
- SAI_Peregrinus 1y agoThey still take the same amount of time to run it. You don't get a result by running for 1/n of the steps, so adding more QCs lets you attack more keys at once but doesn't let you attack any given key any faster.