Quantum key recovery attack on SIMON32/64

Abstract

Abstract The quantum security of lightweight block ciphers is receiving more and more attention. However, the existing quantum attacks on lightweight block ciphers only focused on the quantum exhaustive search, while the quantum attacks combined with classical cryptanalysis methods haven’t been well studied. In this paper, we study quantum key recovery attack on SIMON32/64 using Quantum Amplitude Amplification algorithm in Q1 model. At first, we reanalyze the quantum circuit complexity of quantum exhaustive search on SIMON32/64. We estimate the Clifford gates count more accurately and reduce the T gate count. Also, the T-depth and full depth is reduced due to our minor modifications. Then, using four differentials given by Biryukov in FSE 2014 as our distinguisher, we give our quantum key recovery attack on 19-round SIMON32/64. We treat the two phases of key recovery attack as two QAA instances separately, and the first QAA instance consists of four sub-QAA instances. Then, we design the quantum circuit of these two QAA instances and estimate their corresponding quantum circuit complexity. We conclude that the quantum circuit of our quantum key recovery attack is lower than quantum exhaustive search. Our work firstly studies the quantum dedicated attack on SIMON32/64. And this is the first work to study the complexity of quantum dedicated attacks from the perspective of quantum circuit complexity, which is a more fine-grained analysis of quantum dedicated attacks’ complexity.

Keywords

• Quantum cryptanalysis
• Lightweight block ciphers
• Quantum amplitude amplification
• Differential cryptanalysis
• Key recovery attack
• SIMON32/64