Quantum Linear Key-Recovery Attacks Using the QFT

Y.C. Wang, Jianmei Liu

Yaru Wang, Haodong Jiang, Zhi Ma

C Z, Jie Guan, Tairong Shi +3 more

ABSTRACT Since the proposal of the Grover algorithm in 1996, which first combined quantum algorithms with symmetric cryptanalysis, significant progress has been made in the quantization of classical cryptanalysis methods. Differential‐linear cryptanalysis is a hybrid technique combining differential and linear cryptanalysis; however, there has been no prior work on its quantization. This paper presents a quantum differential‐linear key recovery attack framework. We apply this framework to Simon32/64 and Simeck32/64. Considering that the experimental correlation distribution of the differential‐linear distinguisher significantly affects the complexity of quantum attacks, we measure the experimental correlation distributions of Simon32/64 and Simeck32/64. We conduct a quantum differential‐linear key recovery attack on 19‐round Simon32/64. Under the Q1 model, the time complexity of the attack is , the data complexity is , the memory complexity is and the success rate is 60.96%, which achieves the lowest time, memory, and data complexities among all existing 19‐round quantum attacks. In the Q2 model, the time complexity reduces to , with negligible memory complexity. For Simeck32/64, we present a 20‐round quantum key recovery attack under the Q2 model, which is the first quantum key recovery attack on this block cipher.

Ping Zhang

Shinagawa and Iwata are considered quantum security for the sum of Even-Mansour (SoEM) construction and provided quantum key recovery attacks by Simon's algorithm and Grover's algorithm. Furthermore, quantum key recovery attacks are also presented for natural generalizations of SoEM. For some variants of SoEM, they found that their quantum attacks are not obvious and left it as an open problem to discuss the security of such constructions. This paper focuses on this open problem and presents a positive response. We provide quantum key recovery attacks against such constructions by quantum algorithms. For natural generalizations of SoEM with linear key schedules, we also present similar quantum key recovery attacks by quantum algorithms (Simon's algorithm, Grover's algorithm, and Grover-meet-Simon algorithm).

Peter P. Rohde

Aurel Pichollet-Mugnier, André Schrottenloher

This paper focuses on quantum key-recovery attacks on block ciphers. Previous works on quantum differential and truncated differential attacks like [Kaplan et al., ToSC 2016] have shown that classical algorithms for key-recovery, typically based on generating differential pairs and sieving them, can be accelerated by up to a quadratic speedup using variants of quantum search, quantum amplitude amplification, and quantum collision-finding.>br/> In this paper, we introduce a new quantum truncated differential key-recovery attack, which leverages the quantum convolution algorithm introduced in [Schrottenloher, CRYPTO 2022] and previously used in linear cryptanalysis. We adapt this algorithm to the case of differential cryptanalysis, by rewriting the probability of a differential of an n-bit cipher as a convolution of functions with 2n-bit input. We then construct a quantum state whose amplitudes encode the probability of the differential for different key guesses, and use this as the starting point of a quantum search. In some cases (although not on practical ciphers so far), the speedup is better than quadratic compared to classical attacks. We also extend the framework to related-key differential attacks.We give applications to a 9-round attack on QARMAv2-64 adapted from [Ahmadian et al., DCC 2024] and a 12-round related-key attack on AES-256 from [Boura et al., CRYPTO 2023], which show improvement over classical attacks and over Kaplan et al.’s strategy when taking into account the amount of memory and the type of quantum memory used (as our attack requires only quantum-accessible classical memory).