Comment by ls612

Comment by ls612 19 hours ago

7 replies

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 19 hours ago

128-bit AES is fine. To run Grover’s algorithm against it you’d need to cover the moon with qubits.

dist-epoch 17 hours 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 17 hours ago

    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.

    • cyberax 16 hours ago

      You can trivially parallelize Grover's search by assigning each quantum computer it's own search space.

      • upofadown 16 hours ago

        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.

        • cyberax 16 hours ago

          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.