Re:Signal's New PQ Ratchet
by ls612 on Thursday October 02, 2025 @01:05PM
(#45452364)
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?
[ Parent
| on HN ]
128-bit AES is fine. To run Grover’s algorithm against it you’d need to cover the moon with qubits.
which algorithm are you referring to?
Re:Signal's New PQ Ratchet
by dist-epoch on Thursday October 02, 2025 @02:39PM
(#45453614)
> 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.
Re:Signal's New PQ Ratchet
by SAI_Peregrinus on Thursday October 02, 2025 @03:30PM
(#45454314)
And 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.
You can trivially parallelize Grover's search by assigning each quantum computer it's own search space.
Yes, 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.
Well, 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.
Re:Signal's New PQ Ratchet
by SAI_Peregrinus on Monday October 06, 2025 @06:53PM
(#45497216)
They 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.