© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Quantum Reports

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

Christoph Graebnitz, Valentin Pickel, Holger Eble, Frank Morgner, Hannes Hattenbach, Marian Margraf

Published Dec 22, 2024• 0 citations

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≤32) output bits.

DOI: 10.3390/quantum6040043

Related papers

Deutsch-Jozsa Algorithm Revisited in the Domain of Cryptographically Significant Boolean Functions

Subhamoy Maitra, Partha Mukhopadhyay

Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let $f$ be an $n$-variable Boolean function and its Walsh spectra is denoted by $W_f(ω)$ at the point $ω\in \{0, 1\}^n$. The Boolean function is available in the form of an oracle. We like to find an $ω$ such that $W_f(ω) \neq 0$ as this will provide one of the linear functions which are correlated to $f$. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in $n$. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.

arXiv:quant-ph/0410042•Oct 6, 2004•4 citations

Quantum Decoherence-Driven Cryptanalysis

Jincheng Zhang

This paper investigates the potential of leveraging quantum decoherence for cryptanalysis. The core claim is that exploiting the properties of quantum decoherence can accelerate the rate at which cryptographic keys are compromised. The proposed mechanism involves designing a novel algorithm that directly targets the vulnerabilities introduced by decoherence. Specifically, this algorithm aims to disrupt cryptographic keys by manipulating the quantum state and inducing decoherence, thereby facilitating the decryption process. The research delves into the theoretical aspects of this approach, focusing on the mathematical formulation of decoherence effects and their impact on key security. We explore scenarios where precisely controlled decoherence can significantly reduce the computational complexity of breaking certain cryptographic schemes. The work highlights the potential of directly applying fundamental quantum principles to cryptanalysis, offering a new avenue for attack strategies. The presented analysis provides a foundational understanding of this emerging field, emphasizing the need for further research into the practical implementation and optimization of decoherence-based cryptanalytic techniques.

•Sep 3, 2026•0 citations

THE DEUTSCH–JOZSA ALGORITHM REVISITED IN THE DOMAIN OF CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS

Subhamoy Maitra, PARTHA MUKHOPADHYAY

Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems, one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let f be an n-variable Boolean function and its Walsh spectra is denoted by Wf(ω) at the point ω ∈ {0, 1}n. The Boolean function is available in the form of an oracle. We like to find a ω such that Wf(ω) ≠ 0 as this will provide one of the linear functions which are correlated to f. We show that the quantum algorithm proposed by Deutsch and Jozsa7 solves this problem in constant time. However, the best known classical algorithm to solve the problem requires exponential time in n. We also analyze certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch–Jozsa algorithm performs on them.

International Journal of Quantum Information•May 31, 2005•13 citations

Classical and Quantum based Differential Cryptanalysis Methods

Priyanka Jojan, Kapil Kumar Soni, Akhtar Rasool

The security of a significant proportion of cryptography in use today depends directly or indirectly on the presumed difficulty of either factoring or extracting discrete logarithms in polynomial time on quantum computers. This paper discusses a quantum version of differential cryptanalysis which propounds quadratic speedup over the existing classical one. Linear cryptanalysis and differential cryptanalysis are general form cryptanalysis which is primarily applicable to block cipher, but also to stream ciphers and cryptographic hash functions. Linear cryptanalysis is a known-plaintext attack, in which attacker studies probabilistic linear relations known as linear approximations between some bits of plaintext, some bits of cipher text and some bits of cipher key. And in differential cryptanalysis the role of attacker is to analyze how differences in input information can affect the resulting difference at the output. Differential Cryptanalysis is a chosen-plaintext attack. However, differential cryptanalysis is more compelling so in this paper we are proposing a quantum version of the same. The computational complexity of classical differential cryptanalysis reaches O(NK). But by applying variations of Grover's search that is either full or partial Quantum Search the number of queries required to find the cipher key will be reduced.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 6, 2021•5 citations

Quantum Algorithm to Construct Linear Approximation of an S-Box

Ashwini Kumar Malviya, Namita Tiwari

Linear cryptanalysis, a Known-Plaintext Attack, for symmetric block cipher works by constructing linear approximations of the non-linear components of the cipher. The only component which introduces non-linearity in the symmetric block cipher is an S-box. Using classical computing algorithms, the best known solution to find a linear approximation of a non-linear function, in this case an S-box, requires queries to the S-box and time-complexity, where is the input size of the S-box and is the output size. In this paper, a quantum algorithm is presented which can produce best linear approximations of a non-linear S-box using only queries to S-box with time-complexity. The proposed algorithm shows a significant improvement over the classical algorithm. Correctness proof of the proposed quantum algorithm is presented along with an example.

International Journal of Recent Technology and Engineering (IJRTE)•Nov 30, 2019•1 citation

Quantum Paths to Cryptanalysis

Cezary Pilaszewicz

Quantum computers offer a novel approach to data processing, which poses both opportunities and threats for modern cryptography. While Shor’s algorithm for prime factorisation demonstrated the possible impact of quantum cryptanalysis, the complete quantum significance in the cryptanalytical context still needs further research. This thesis compiles a series of recent publications, each of which examines a distinct application of quantum advantage in cryptography. Collectively, these contributions constitute a non-exhaustive compendium of recent advancements in quantum cryptanalysis. We first examine applications of the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear equation systems. We propose two approaches in which the quantum advantage of the HHL algorithm could be leveraged to investigate structural properties relevant to symmetric cryptanalysis. In the subsequent chapter, an analysis is conducted on the significance of adiabatic quantum computing and its role in the cryptanalytical setting. Together, these results offer novel insights into the capabilities and limitations of quantum-enhanced cryptanalysis of symmetric ciphers. Turning to asymmetric settings, two quantum attacks are proposed that result in the complete break of the underlying ciphers. The first one exploits the recipient’s encryption process to extract the secret key used in the Quantum Encryption Method. The second targets an Identity-Based Encryption scheme whose security relies on isogenies. We demonstrate that the distinct use of isogenies introduces new attack vectors for both classical and quantum adversaries. Collectively, these contributions deepen the understanding of quantum-enhanced cryptanalysis, thereby clarifying both its potential and current boundaries.

•Jan 1, 2025•0 citations

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≤32) output bits.

Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let

f

be an

n

-variable Boolean function and its Walsh spectra is denoted by

W_f(ω)

at the point

ω\in \{0, 1\}^n

. The Boolean function is available in the form of an oracle. We like to find an

ω

such that

W_f(ω) \neq 0

as this will provide one of the linear functions which are correlated to

f

. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in

n

. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.

This paper investigates the potential of leveraging quantum decoherence for cryptanalysis. The core claim is that exploiting the properties of quantum decoherence can accelerate the rate at which cryptographic keys are compromised. The proposed mechanism involves designing a novel algorithm that directly targets the vulnerabilities introduced by decoherence. Specifically, this algorithm aims to disrupt cryptographic keys by manipulating the quantum state and inducing decoherence, thereby facilitating the decryption process. The research delves into the theoretical aspects of this approach, focusing on the mathematical formulation of decoherence effects and their impact on key security. We explore scenarios where precisely controlled decoherence can significantly reduce the computational complexity of breaking certain cryptographic schemes. The work highlights the potential of directly applying fundamental quantum principles to cryptanalysis, offering a new avenue for attack strategies. The presented analysis provides a foundational understanding of this emerging field, emphasizing the need for further research into the practical implementation and optimization of decoherence-based cryptanalytic techniques.

Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems, one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let f be an n-variable Boolean function and its Walsh spectra is denoted by Wf(ω) at the point ω ∈ {0, 1}n. The Boolean function is available in the form of an oracle. We like to find a ω such that Wf(ω) ≠ 0 as this will provide one of the linear functions which are correlated to f. We show that the quantum algorithm proposed by Deutsch and Jozsa7 solves this problem in constant time. However, the best known classical algorithm to solve the problem requires exponential time in n. We also analyze certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch–Jozsa algorithm performs on them.

The security of a significant proportion of cryptography in use today depends directly or indirectly on the presumed difficulty of either factoring or extracting discrete logarithms in polynomial time on quantum computers. This paper discusses a quantum version of differential cryptanalysis which propounds quadratic speedup over the existing classical one. Linear cryptanalysis and differential cryptanalysis are general form cryptanalysis which is primarily applicable to block cipher, but also to stream ciphers and cryptographic hash functions. Linear cryptanalysis is a known-plaintext attack, in which attacker studies probabilistic linear relations known as linear approximations between some bits of plaintext, some bits of cipher text and some bits of cipher key. And in differential cryptanalysis the role of attacker is to analyze how differences in input information can affect the resulting difference at the output. Differential Cryptanalysis is a chosen-plaintext attack. However, differential cryptanalysis is more compelling so in this paper we are proposing a quantum version of the same. The computational complexity of classical differential cryptanalysis reaches O(NK). But by applying variations of Grover's search that is either full or partial Quantum Search the number of queries required to find the cipher key will be reduced.

Linear cryptanalysis, a Known-Plaintext Attack, for symmetric block cipher works by constructing linear approximations of the non-linear components of the cipher. The only component which introduces non-linearity in the symmetric block cipher is an S-box. Using classical computing algorithms, the best known solution to find a linear approximation of a non-linear function, in this case an S-box, requires queries to the S-box and time-complexity, where is the input size of the S-box and is the output size. In this paper, a quantum algorithm is presented which can produce best linear approximations of a non-linear S-box using only queries to S-box with time-complexity. The proposed algorithm shows a significant improvement over the classical algorithm. Correctness proof of the proposed quantum algorithm is presented along with an example.

Quantum computers offer a novel approach to data processing, which poses both opportunities and threats for modern cryptography. While Shor’s algorithm for prime factorisation demonstrated the possible impact of quantum cryptanalysis, the complete quantum significance in the cryptanalytical context still needs further research. This thesis compiles a series of recent publications, each of which examines a distinct application of quantum advantage in cryptography. Collectively, these contributions constitute a non-exhaustive compendium of recent advancements in quantum cryptanalysis. We first examine applications of the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear equation systems. We propose two approaches in which the quantum advantage of the HHL algorithm could be leveraged to investigate structural properties relevant to symmetric cryptanalysis. In the subsequent chapter, an analysis is conducted on the significance of adiabatic quantum computing and its role in the cryptanalytical setting. Together, these results offer novel insights into the capabilities and limitations of quantum-enhanced cryptanalysis of symmetric ciphers. Turning to asymmetric settings, two quantum attacks are proposed that result in the complete break of the underlying ciphers. The first one exploits the recipient’s encryption process to extract the secret key used in the Quantum Encryption Method. The second targets an Identity-Based Encryption scheme whose security relies on isogenies. We demonstrate that the distinct use of isogenies introduces new attack vectors for both classical and quantum adversaries. Collectively, these contributions deepen the understanding of quantum-enhanced cryptanalysis, thereby clarifying both its potential and current boundaries.