Submitted by giuliomagnifico t3_zuxy0d in technology
sumguysr t1_j1n9e5c wrote
Reply to comment by itdood in An IBM Quantum Computer Will Soon Pass the 1,000-Qubit Mark by giuliomagnifico
Source please? My understanding was quantum computing only halves the difficulty of breaking symmetric encryption like AES but completely breaks current asymmetric encryption like RSA
nagareteku t1_j1njxg2 wrote
Grover's algorithm more than "halves" the difficulty of AES, it square roots it.
For a brute-force attack, 128-bit AES will now take 2^(64) rather than 2^(128) operations, and 256-bit AES will now take 2^(128) rather than 2^(256) operations.
To visualise the difference, 2^(128) is 18,446,744,073,709,551,616 times larger than 2^(64) and 2^(256) is that amount squared times larger than 2^(128).
Given a rate of a billion guesses per second, a single 6600-qubit quantum chip can crack AES-128 in 585 years. If we run a million cores of quantum chips in parallel, then in about 5 hours AES-128 is broken even when using a naive brute force attack. A well funded state actor could cuild such a machine, and easily decrypt anything encrypted on less than 128-bit of cipher.
256-bit AES will take a little longer, since 2^(128) is still quite a large number (3.4*10^(28)). Fortunately (or unfortunately), there exists a quantum attack on 256-bit AES with only 2^(100) operations required, although it might take 2^(100) bits (1.268 quettabytes) of storage and still require 2^(36) times more computational power than cracking AES-128.
For now, AES-256 is safe, but AES-128 is vulnerable. AES-256 may be slower than AES-128 but do not skimp on cybersecurity!
KAMSPioneer t1_j1npnnm wrote
All completely true, but the last paragraph should probably be taken with a grain of salt. For non-PQ threat models, AES-128 is totally fine. In fact key schedule attacks against AES-256 that could bring attacks down to 2^70 time (!!) do not affect AES-128.
None of that is to say that AES-256 is broken -- it's still quite safe. But unless you have strong and imminent concerns about quantum attacks on your cryptosystem, AES-128 is almost definitely not vulnerable. Most experts agree that your time is better spent worrying about everything around the primitive than the choice of primitive itself.
I just don't want anyone alarmed by the idea that there is a nearly-practical attack on AES or something. That's a long, long way off.
nicuramar t1_j1nw5o7 wrote
> Grover's algorithm more than "halves" the difficulty of AES, it square roots it.
Yes, but unfortunately it also makes it impossible to run the algorithm in parallel, making it more or less useless in practice.
itdood t1_j1n9mik wrote
KAMSPioneer t1_j1nrm7d wrote
This source says 6600 error-corrected qubits and the source article OP posted appears (though it's not completely clear to me) to not be utilizing error correction. I suspect this dampens the usefulness of IBM's new machine in implementing Grover's.
Viewing a single comment thread. View all comments