An Extended Analysis of the Correlation Extraction Algorithm in the Context of Linear Cryptanalysis

Abstract

In cryptography, techniques and tools developed in the subfield of linear cryptanalysis have previously successfully been used to allow attackers to break many sophisticated cryptographic ciphers. Since these linear cryptanalytic techniques require exploitable linear approximations to relate the input and output of vectorial Boolean functions, e.g., the plaintext, ciphertext, and key of the cryptographic function, finding these approximations is essential. For this purpose, the Correlation Extraction Algorithm (CEA), which leverages the emerging field of quantum computing, appears promising. However, there has been no comprehensive analysis of the CEA regarding finding an exploitable linear approximation for linear cryptanalysis. In this paper, we conduct a thorough theoretical analysis of the CEA. We aim to investigate its potential in finding a linear approximation with prescribed statistical characteristics. To support our theoretical work, we also present the results of a small empirical study based on a computer simulation. The analysis in this paper shows that an approach that uses the CEA to find exploitable linear approximations has an asymptotic advantage, reducing a linear factor to a logarithmic one in terms of time complexity, and an exponential advantage in terms of space complexity compared to a classical approach that uses the fast Walsh transform. Furthermore, we show that in specific scenarios, CEA can exponentially reduce the search space for exploitable linear approximations in terms of the number of input bits of the cipher. Neglecting the unresolved issue of efficiently checking the property of linear approximations measured by the CEA, our results indicate that the CEA can support the linear cryptanalysis of vectorial Boolean functions with relatively few (e.g., $n\le 32$) output bits.