Quantum Meet-in-the-Middle Attacks on Two-Key 3DES
摘要
Quantum algorithms can accelerate cryptanalysis and reduce the security strength of symmetric ciphers. Increasing the key length is a common approach to enhance the security of symmetric ciphers. Triple DES (3DES), a block cipher derived from DES, achieves this by applying triple encryption with extended key lengths. A quantum meet-in-the-middle (MITM) attack is specifically proposed for two-key 3DES. This attack utilizes Grover’s quantum algorithm to accelerate the key-recovery process and, through a classical preprocessing process, reduces the complexity of the online quantum computation to \(\text{O}({2}^{28})\) , which is significantly lower than the optimal classical attack complexity \(\text{O}({2}^{56})\) . Since the quantum security strength of DES is \(\text{O}({2}^{28})\) , this attack demonstrates that two-key 3DES cannot provide more security than DES in quantum setting. The attack is only feasible in the Q2 model and requires \(\text{O}({2}^{56})\) quantum random access memory (QRAM). Based on this attack, a time-QRAM tradeoff variant is also proposed, which balances the time complexity and QRAM. This results in an attack complexity and QRAM size both at \(\text{O}({2}^{42})\) , which is still better than optimal classical attack.