Grover, a quantum algorithm, weakens AES and ChaCha20. Is it possible to use multiple symmetric keys to encrypt a message multiple times to achieve 256-bit security for quantum computers?
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ And why do you think that you need 256 bit security for Quantum Computers? $\endgroup$– ponchoCommented Feb 21, 2023 at 14:40
-
$\begingroup$ Kyber1024 provides 256-bit security, but symmetric key ciphers only provides 128-bit security, it's unfair. To be fair, it must ensure that symmetric key encryption provides the same security level as Kyber1024. $\endgroup$– Flan1335Commented Feb 23, 2023 at 6:33
-
$\begingroup$ Kyber1024 is generally believed to be "NIST level 5"; and that is defined as "as strong as AES-256". Hence, if you insist on something with approximately the same security level, you can just use AES-256 $\endgroup$– ponchoCommented Feb 23, 2023 at 13:31
-
$\begingroup$ ambit.inc/pdf/KyberDrive.pdf This research says: "Kyber-1024 is known to have 254 bits of classical security and 230 bits of quantum security (coreSVP hardness). It is a NIST Level 5 security level." "Not all modes of AES are post-quantum secure." Therefore, Kyber1024 is much more secure than AES256 for quantum computers, but has similar security for classical computers. $\endgroup$– Flan1335Commented Mar 17, 2023 at 12:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
10
As mentioned in a comment, 256-bit quantum security is overkill. Even AES-128 is unlikely to be broken by a quantum computer, as discussed here. Briefly: Grover's algorithm is the best possible; it doesn't parallelize efficiently; and it's unlikely that quantum computers will reach similar clock speeds as classical computers.
But assume you're really paranoid and want 256-bit quantum security anyway, so you'll need 512-bit classical security. You could either design a new 512-bit symmetric cipher, or use a composition of 256-bit symmetric ciphers. A similar situation had to be considered a few decades ago, when DES was standardized but AES didn't exist yet, and it became clear that 56 bits was within reach of motivated attackers, as concretely demonstrated by the EFF DES Cracker and distributed.net.
It turns out that, somewhat counterintuitively, double-DES does not have $2 \times 56 = 112$-bit security, but rather 57-bit security due to a very simple meet-in-the-middle attack. To achieve 112-bit security, triple-DES was required, and indeed was used in practice.
So, if you really want 512-bit classical security, you'd have to use triple-AES. In principle you could use only 2 different keys (although still using 3 chained encryption/decryption operations), but there exist attacks on that scenario, so for the truly paranoid, you'll have to use 3 different keys. Thus, a total of 768 bits of key material to achieve 512-bit classical security and 256-bit quantum security.
-
$\begingroup$ I'm pretty sure double AES is enough for 256 bits of quantum security. The double DES meet in the middle attack isn't practical for an attack against AES 256 since it would require roughly 2^256 bits of storage while the best estimates for the world's hard drive capacity is a bit hard to pin down, but almost certainly under 2^100 bits. $\endgroup$ Commented Feb 21, 2023 at 18:30
-
1$\begingroup$ By that logic, and given the arguments about Grover's algorithm, 256-bit single AES is effectively unbreakable, so whether to use double or triple AES is a moot point. If someone is that worried about a quantum attack to 256-bit AES, the extra 50% execution time to go from double to triple AES is certainly warranted. $\endgroup$– swineoneCommented Feb 21, 2023 at 19:28
-
-
$\begingroup$ @Flan1335 I'll answer if you give me one reasonable argument for going beyond 512-bit classical security. $\endgroup$– swineoneCommented Feb 27, 2023 at 5:19
-
$\begingroup$ Bruce schneier found classical attack method schneier.com/blog/archives/2011/08/new_attack_on_a_1.html to reduce the security with classical computers, can quantum computers borrow that attack method? If it's possible with quantum computers, it may need several AES keys. $\endgroup$– Flan1335Commented Mar 11, 2023 at 8:06