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 O (22n/5) and classical memory complexity of O (2n/5) without the need for quantum random access memory, where n 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 O (2n/3) and quantum random memory complexity of O (2n/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 O (2n/3). Compared with the classical slide attack, this method achieves sub-exponential acceleration; compared with Grover’s search, the query complexity reduces from O (2n/2) to O (2n/3).
Abstract By introducing the BHT algorithm into the slide attack on 1K-AES and the related-key attack on PRINCE, we present the corresponding quantum attacks in this paper. In the proposed quantum attacks, we generalize the BHT algorithm to the situation where the number of marked items is unknown ahead of time. Moreover, we give an implementation scheme of classifier oracle based on Quantum Phase Estimation algorithm in presented quantum attacks. The complexity analysis shows that the query complexity, time complexity and memory complexity of the presented quantum attacks are all
O(2n/3) when the success probability is about
63%, where
n is the block size. Compared with the corresponding classical attacks, the proposed quantum attacks can achieve subquadratic speed-up under the same success probability no matter on query complexity, time complexity or memory complexity. Furthermore, the query complexity of the proposed quantum slide attack on 1K-AES is less than Grover search on 1K-AES by a factor of
2n/6. When compared with the Grover search on PRINCE, the query complexity of the presented quantum attack on PRINCE is reduced from
O(2n) to
O(2n/2). When compared with the combination of Grover and Simon’s algorithms on PRINCE, the query complexity of our quantum attack on PRINCE is reduced from
O(n⋅2n/2) to
O(2n/2). Besides, the proposed quantum slide attack on 1K-AES indicates that the quantum slide attack could also be applied on Substitution-Permutation Network construction, apart from the iterated Even-Mansour cipher and Feistel constructions.