←back to thread

Willow quantum chip demonstrates verifiable quantum advantage on hardware

(blog.google)
429 points AbhishekParmar | 3 comments | 22 Oct 25 15:16 UTC | HN request time: 0.685s | source
Show context
ashleyn ◴[22 Oct 25 15:46 UTC] No.45670927[source]▶
We're all asking it: any impact on AES?
replies(2): >>45671151 #>>45671168 #
jonathanstrange ◴[22 Oct 25 16:01 UTC] No.45671151[source]▶
The rule of thumb is that a working quantum computer that can run Grover's algorithm reduces the security of a symmetric cipher to half of its key size. That is, AES-128 should be considered to have a 64 bit key size, which is why it's not considered "quantum-safe."

Edit: An effective key space of 2^64 is not secure according to modern-day standards. It was secure at the times of DES.

replies(1): >>45672069 #
1. adgjlsfhk1 ◴[22 Oct 25 17:04 UTC] No.45672069[source]▶
AES-128 is quantum safe (more or less). 64 bit security in the classical domain isn't safe because you can parallelize across 2^20 computers trivially. Grover gives you 2^64 AES operations on a quantum coputer (probably ~2^70 gates or so before error correction or ~2^90 after error correction) that can't be parallelized efficiently. AES-128 is secure for the next century (but you might as well switch to aes-256 because why not)
replies(1): >>45674788 #
2. msm_ ◴[22 Oct 25 20:32 UTC] No.45674788[source]▶
Is AES-256 more quantum resistant? It still has 16byte block size, so intuitively it should be equally vulnerable to Grover.
replies(1): >>45675079 #
3. adgjlsfhk1 ◴[22 Oct 25 21:00 UTC] No.45675079[source]▶
Grover's algorithm is sqrt(N) wrt domain size and the key is part of the domain of the function.