Quantum slide attack on 1K-AES structure

Abstract

<p indent="0mm">With the continuous development of quantum technology, the quantum security of symmetric ciphers has attracted widespread attention. This study focuses on the security of 1K-AES, employing both quantum and classical slide attacks to analyze its security. On the one hand, for the 1K-AES with MixColumns in the last round, using the CNS algorithm achieves a success rate of 74%, an improvement from 63%, under a query complexity of <inline-formula id="INLINEA8"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="8.0pt"><mml:mrow><mml:mi mathsize="8.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2^{2<italic>n</italic>/5}) and classical memory complexity of <inline-formula id="INLINEA9"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="8.0pt"><mml:mrow><mml:mi mathsize="8.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2^{<italic>n</italic>/5}) without the need for quantum random access memory, where <italic>n</italic> denotes the block size. When using a quantum random access memory, the universal quantum claw-finding algorithm improves the success rate to 100% with a query complexity of <inline-formula id="INLINEA10"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="8.0pt"><mml:mrow><mml:mi mathsize="8.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2^{<italic>n</italic>/3}) and quantum random memory complexity of <inline-formula id="INLINEA11"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="8.0pt"><mml:mrow><mml:mi mathsize="8.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2^{<italic>n</italic>/3}). Additionally, under the chosen plaintext attack, the success rate of the classical slide attack is also increased to 100%. On the other hand, for the 1K-AES with no MixColumns in the last round, the universal quantum claw-finding algorithm is used to perform a quantum slide attack, with both time and memory complexity of <inline-formula id="INLINEA12"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="8.0pt"><mml:mrow><mml:mi mathsize="8.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2^{<italic>n</italic>/3}). Compared with the classical slide attack, this method achieves sub-exponential acceleration; compared with Grover’s search, the query complexity reduces from <inline-formula id="INLINEA13"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="8.0pt"><mml:mrow><mml:mi mathsize="8.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2^{<italic>n</italic>/2}) to <inline-formula id="INLINEA14"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" mathsize="8.0pt"><mml:mrow><mml:mi mathsize="8.0pt" mathvariant="script">O</mml:mi></mml:mrow></mml:math></inline-formula>(2^{<italic>n</italic>/3}).</p>

References