Abstract

Translate

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 \leq 32$ ) output bits.

Full text

Turn on search term navigation

Translate

1. Introduction

Quantum computing has the potential to enhance computations in different domains, particularly in cryptanalysis [1]. One of the most significant approaches in cryptanalysis is Shor’s algorithm, which can be used to break asymmetric cryptography based on the prime factorization problem and the discrete logarithm problem [2,3,4,5]. Another approach is to use Grover’s algorithm to determine the key of cryptographic primitives such as AES [6]. The progress in cryptanalysis using quantum computing impacts the research and usage of cryptographic primitives. For example, research into post-quantum cryptography has been massively accelerated mainly due to Shor’s algorithm [7].

As quantum computing in cryptanalysis advances, a growing area of research is exploring whether it can enhance traditional cryptanalytic methods, such as algebraic [8,9,10,11], differential [11,12,13,14,15], and linear [11,16,17,18] cryptanalysis. With that in mind, this paper focuses on analyzing the potential of a quantum algorithm to improve a crucial aspect of linear cryptanalysis. Before discussing the potential of that quantum algorithm, we first briefly introduce the essentials of linear cryptanalysis.

In 1993, Matsui and Yamagishi introduced the research field of linear cryptanalysis with a known plaintext attack on FEAL [19] to the public. Subsequently, Matsui showed that linear cryptanalysis could also be used to break the Data Encryption Standard (DES), requiring $2^{47}$ plaintext–ciphertext pairs to recover the encryption key [20]. Moreover, there are several extensions to linear cryptanalysis [21,22,23], but for the sake of simplicity, this paper focuses on Matsui’s prototypical concept [20], which is introduced in the following paragraph.

Due to its statistical approach, applying linear cryptanalysis to a cipher or a vectorial Boolean function $f : F_{2}^{m} \to F_{2}^{n}$ with m input and n output bits involves using a uniformly distributed random variable X with sample space $F_{2}^{m}$ . In detail, linear cryptanalysis requires at least one mask $(α, β) \in F_{2}^{m} \times F_{2}^{n}$ such that the linear approximation $〈 α, X 〉 = 〈 β, f (X) 〉$ , expressed in terms of canonical inner products in $F_{2}^{m}$ , holds with a probability not equal to one half. In addition, the mask $(α, β)$ with only zeros $α = β = 0$ is called the trivial mask. Furthermore, the deviation from one half, specified as $ε_{f} : F_{2}^{m} \times F_{2}^{n} \to [- 1 / 2, 1 / 2]$ , is called the bias of a mask, and a mask with $ε_{f} (α, β) \neq 0$ is called biased. The success of linear cryptanalysis depends on the size of the absolute bias of the mask used. Larger absolute biases are the most effective (see Section 2.1 for details), except for the trivial mask with $ε_{f} (0, 0) = 1 / 2$ , which provides no information. Therefore, finding nontrivial masks with a prescribed absolute bias is crucial for linear cryptanalysis.

Since there are overall $2^{m + n}$ masks, finding specific ones is assumed to be computationally hard in general. A standard approach to finding suitable masks is to calculate and check the bias of all masks using the fast Walsh transform (FWT) by Brown [24]. The exhaustive search utilizing the FWT has a time complexity of $O ((n \cdot T_{f} + m) \cdot 2^{m + n})$ , where $T_{f}$ denotes the cost of executing f (see Section 2.1 for details). In some cases, the time complexity of mask-seeking algorithms, e.g., the FWT, is acceptable for small vectorial Boolean functions $(m = n = 8)$ like S-boxes of substitution–permutation networks. However, it is assumed that there is no classical algorithm that finds suitable masks in plain generality within feasible time and space constraints.

An efficient quantum algorithm that may assist in finding appropriate masks for arbitrary vectorial Boolean functions is the Correlation Extraction Algorithm (CEA) [16,17]. Specifically, executing the CEA returns a biased mask, while the absolute bias of a mask monotonously relates to the probability of measuring it. Remarkably, simplified, the CEA computes the correlation, defined as $2 \cdot ε_{f} (α, β)$ , of all masks and encodes them into the amplitude of the quantum state using only one call to a quantum oracle that realizes f. Despite the fact that we cannot directly access the amplitudes of a quantum state, the CEA has an exponential speed-up in calculating the correlation of all masks compared to the classical standard approach with FWT.

Although we cannot directly access the correlations calculated by the CEA, the algorithm demonstrates the potential to enhance linear cryptanalysis. In the current literature, the CEA is used as a (sub-)routine in specific quantum versions of linear cryptanalysis [16,17,18] or property testing of vectorial Boolean functions [25,26]. However, none of the aforementioned works quantify the success rate of the CEA for measuring masks with a prescribed absolute bias, leaving this as an open problem that this paper addresses. Overall, this paper aims to analyze the capabilities and limitations of the CEA to understand its potential to find masks with a prescribed absolute bias for linear cryptanalysis.

1.1. Contribution

Our contribution investigates the capabilities of the CEA in finding a mask with a prescribed absolute bias within r executions. The following outlines the contributions of this paper.

We formalize the probability of the CEA to output a mask with a prescribed absolute bias within r executions.
We prove lower and upper bounds on r for a given fixed success probability to obtain at least one mask with a prescribed absolute bias.
Based on the lower and upper bounds on r, we prove the asymptotic behavior of CEA regarding time, query, and memory complexity.
Using CEA, we introduce an algorithm to find a mask with a prescribed absolute bias and prove its asymptotic behavior.
We verify the behavior of CEA to measure a mask with a prescribed absolute bias by means of an empirical study on two vectorial Boolean functions with $m = 8$ input and $n = 8$ output bits each.
We compare two approaches that use the FWT or CEA to find a mask with a prescribed absolute bias while discussing the potential of the CEA in linear cryptanalysis.

Overall, our contribution provides comprehensive insights about the CEA, enabling sound statements about its suitability in linear cryptanalysis.

1.2. Related Work

Malviya and Tiwari [16] introduced the algorithmic idea of the CEA for finding biased masks. Besides finding biased masks, CEA has applications in linear cryptanalysis using quantum computers: Malviya and Tiwari [18] presented a full quantum version of a linear cryptanalytic attack on an 8-bit SPN toy cipher using the CEA to find biased masks. Moreover, Hosoyamada [17] describes how to speed up multidimensional linear and integral distinguishers using the CEA. In addition to applying the CEA to attack a cipher, the CEA can also be used in the context of property testing of vectorial Boolean functions [25,26].

1.3. Organization

This paper begins by presenting the preliminaries for this work in Section 2, with some essential notations and definitions regarding linear cryptanalysis and the CEA. Section 3 then formalizes the success probability of the CEA to output a mask with a prescribed absolute bias. Section 4 analyzes the asymptotic behavior of the CEA, and Section 5 empirically verifies the statements from Section 3 and Section 4. Afterward, Section 6 discusses the potential of the CEA to find masks with a prescribed absolute bias by comparing the CEA with a standard classical approach that uses the FWT. Ultimately, Section 7 shows the conclusions of this paper.

2. Preliminaries

2.1. Linear Cryptanalysis

Matsui [20] demonstrated that the data complexity, i.e., the number of plaintext–ciphertext pairs required to achieve a fixed success rate with Algorithm 1 depended on the bias of a mask. Table 1 highlights this relationship by displaying Table 2 of Matsui [20]. In particular, Table 1 illustrates the correlation between success rates, data complexity, and bias $ε_{f}$ for Matsui’s Algorithm 1. More precisely, Table 1 shows the reciprocal relation between absolute bias and data complexity.

As a result of the relationship between bias and data complexity, performing linear cryptanalysis requires masks with a sufficiently large absolute bias. Problem 1 formalizes the search for such masks.

Problem 1.

For a function $f : F_{2}^{m} \to F_{2}^{n}$ , a uniformly distributed random variable X with sample space $F_{2}^{m}$ , a threshold $τ \in (0, 1 / 2]$ , and a bias $ε_{f} : F_{2}^{m} \times F_{2}^{n} \to [- 1 / 2, 1 / 2]$ , determine a nontrivial mask $(α, β) \in F_{2}^{m} \times F_{2}^{n}$ that satisfies

(1) $\begin{matrix} p_{α, β} \Pr [〈 α, X 〉 = 〈 β, f (X) 〉] = \frac{1}{2} + ε_{f} (α, β) \end{matrix}$

with $| ε_{f} (α, β) | \geq τ$ .

All algorithms that solve Problem 1 share the need to determine the bias of masks. This can be achieved by evaluating the Walsh transform of f. The following introduces the relation of Problem 1 to the Walsh transform, starting with its definition.

Definition 1

(Walsh transform (see [27])). The Walsh transform of $f : F_{2}^{m} \to F_{2}^{n}$ is given by

(2) $\begin{matrix} W_{f} : F_{2}^{m} \times F_{2}^{n} \to Z; (α, β) \mapsto \sum_{x \in F_{2}^{m}} {(- 1)}^{〈 α, x 〉 \oplus 〈 β, f (x) 〉} . \end{matrix}$

Next, using Definition 1, Theorem 1 establishes a relation between the bias and the Walsh transform of f at a given mask.

Theorem 1 (Calculation of $p_{α, β}$ ).

Let $f : F_{2}^{m} \to F_{2}^{n}$ be a function and $(α, β) \in F_{2}^{m} \times F_{2}^{n}$ a mask. Then, for $p_{α, β}$ , the following holds

$\begin{matrix} p_{α, β} = \frac{1}{2} + \frac{W_{f} (α, β)}{2^{m + 1}} \end{matrix}$

and therefore, $ε_{f} (α, β) = \frac{W_{f} (α, β)}{2^{m + 1}}$ .

Proof of Theorem 1.

Let X be a uniformly distributed random variable with sample space $F_{2}^{m}$ , $C_{f}^{=} (α, β) : = | {x \in F_{2}^{m} ∣ 〈 α, x 〉 = 〈 β, f (x) 〉} |$ , and $C_{f}^{\neq} (α, β) : = | {x \in F_{2}^{m} ∣ 〈 α, x 〉 \neq 〈 β, f (x) 〉} |$ . It holds that

$\begin{matrix} p_{α, β} & = \Pr [〈 α, X 〉 = 〈 β, f (X) 〉] \\ = \frac{C_{f}^{=} (α, β)}{2^{m}} \\ = \frac{C_{f}^{=} (α, β) + C_{f}^{=} (α, β) + C_{f}^{\neq} (α, β) - C_{f}^{\neq} (α, β)}{2^{m + 1}} \\ = \frac{1}{2} + \frac{W_{f} (α, β)}{2^{m + 1}} . \end{matrix}$

Further, from the definition of $p_{α, β}$ , it follows

$\begin{matrix} ε_{f} (α, β) = \frac{W_{f} (α, β)}{2^{m + 1}} . \end{matrix}$

□

Now, we focus on a quantity related to the bias, the correlation of f.

Definition 2.

The correlation of $f : F_{2}^{m} \to F_{2}^{n}$ for $(α, β) \in F_{2}^{m} \times F_{2}^{n}$ is given by

(3) $\begin{matrix} C_{f} (α, β) \frac{W_{f} (α, β)}{2^{m}} . \end{matrix}$

Gathering implicit information about the bias, the correlations appear in the amplitudes of the quantum state of the CEA before measurement, as described in Section 2.2.

After showing the connection between the Walsh transform, correlation, and bias, we now give the time complexity of calculating the Walsh transform of f. To clarify, according to Theorem 1 and Definition 2, the correlation and bias depend on the Walsh transform. Since proving the time complexity for calculating Definition 1 is straightforward, Corollary 1 states its time complexity.

Corollary 1.

For $f : F_{2}^{m} \to F_{2}^{n}$ with a time complexity of $T_{f}$ and an arbitrary but fixed mask $(α, β) \in F_{2}^{m} \times F_{2}^{n}$ , the time complexity to calculate $W_{f} (α, β)$ according to Definition 1 is $O ((m + n + T_{f}) \cdot 2^{m})$ .

Using Corollary 1 allows us to find the time complexity of the brute-force approach for solving Problem 1. Specifically, the brute-force approach for solving Problem 1 involves checking masks until a solution is found. In the worst case, the brute-force approach has a time complexity of $O ((m + n + T_{f}) \cdot 2^{2 m + n})$ . Further note that, in this article, the complexity analyses of classical algorithms are based on one-processor Real Random Access Machines (RRAMs). To clarify, in this paper, complexity analyses involving RRAMs that use basic arithmetic operations on reals ( $R$ ), such as addition and multiplication, have a complexity of $O (1)$ .

In addition to the brute-force approach, we discuss Brown’s FWT algorithm [24], a classical algorithm that can be used to solve Problem 1. Before moving on to further details, we introduce the following convention: let $f (0, \dots, 0), f (0, \dots, 1), \dots, f (1, \dots, 1)$ denote the evaluations of f for all $x \in F_{2}^{m}$ , ordered with respect to the binary input vectors in ascending order. For a fixed $β \in F_{2}^{n}$ , using the vector

(4) $\begin{matrix} v : = {({(- 1)}^{〈 f (0, \dots, 0), β 〉}, {(- 1)}^{〈 f (0, \dots, 1), β 〉}, \dots, {(- 1)}^{〈 f (1, \dots, 1), β 〉})}^{T} \end{matrix}$

as input, the FWT computes the vector

(5) $\begin{matrix} w : = {(W_{f} ((0 \dots 0), β), W_{f} ((0 \dots 1), β), \dots, W_{f} ((1 \dots 1), β))}^{T} \end{matrix}$

as output. As displayed in Equation (5), the FWT calculates the Walsh transforms for all

α \in F_{2}^{m}

and a fixed

β

. Thus, to solve Problem 1, executing the FWT for all

β \in F_{2}^{n} ∖ {0}

is required in the worst case.

Based on this idea, Algorithm 1 specifies an approach to solve Problem 1 utilizing the FWT. For better understanding, we briefly introduce two essential notational conventions. By interpreting $α \in F_{2}^{m}$ as an integer, $w_{α}$ denotes the entry $α$ of the $2^{m}$ dimensional vector w. In addition, $FWT (v)$ denotes the execution of the FWT for the $2^{m}$ dimensional vector as input. Subsequently, Theorem 2 gives the time complexity of Algorithm 1.

Algorithm 1: Pseudocode description of solving Problem 1 using the FWT

[Figure omitted. See PDF]

Theorem 2.

For $f : F_{2}^{m} \to F_{2}^{n}$ with a time complexity of $T_{f}$ , solving Problem 1 using Algorithm 1 has a worst-case time complexity of $O ((n \cdot T_{f} + m) \cdot 2^{m + n})$ , an oracle complexity of $O (2^{m + n})$ , and a space complexity of $O (2^{m})$ .

Proof of Theorem 2.

Calculating the time complexity of Algorithm 1 is straightforward. However, for completeness, we list the complexity of each line and then combine them. The following presents the time complexities of lines 1–11 for only one arbitrary but fixed $β \in F_{2}^{n} ∖ {0}$ :

Line 1: $O (m + n)$ ;
Line 2: $O (m + n)$ ;
Line 3: $O (n \cdot T_{f} \cdot 2^{m})$ ;
Line 4: $O (m \cdot 2^{m})$ (according to Brown [24]);
Lines 5–11: The iteration considers $2^{m}$ values for $α$ . For each value, evaluating the condition of line 5 has a time complexity of $O (m)$ . Thus, checking all entries of w gives the worst-case complexity of $O (m \cdot 2^{m})$ .

In the worst case lines 2–11 must be executed for all $β \in F_{2}^{n} ∖ {0}$ , leading to a time complexity of $O ((n \cdot T_{f} + m) \cdot 2^{m + n})$ .

For the oracle complexity, we require $2^{m}$ oracle calls to initialize v in line 1, which is repeated for all $β \in F_{2}^{n} ∖ {0}$ , giving the oracle complexity of $O (2^{m + n})$ .

The space complexity is again determined solely by the initialization of v in line 1. Brown’s FWT algorithm requires $O (1)$ additional space, as its calculations involving v are in-place [24]. Thus, the space complexity is $O (2^{m})$ .

Finally, we show how Algorithm 1 solves Problem 1. According to Theorem 1, line 5 finds a mask that solves Problem 1. Thus, if one exists, Algorithm 1 returns a mask that solves Problem 1. □

2.2. The Correlation Extraction Algorithm (CEA)

The algorithm presented in this section appears in several publications [17,18,25,26] with different naming conventions. This paper uses the name Correlation Extraction Algorithm from Hosoyamada [17]. However, before we move on to the quantum circuit of the CEA, we introduce some notational conventions related to quantum computing.

A ket $| ϕ 〉 \in C^{2^{m}}$ denotes the quantum state of an m-qubit quantum register. In particular, ${| 0 〉}^{\otimes m}$ specifies the zero state on such a register according to the standard basis. Moreover, this paper utilizes the convention to label the vectors of quantum registers with binary vectors, i.e., $| α 〉 = ⨂_{i} | α_{i} 〉$ with $α_{i} \in {0, 1}$ for all i. As usual in quantum computing, the operators $H^{\otimes m}$ and $I^{\otimes m}$ , for example, describe the Hadamard and identity gate for the whole m-qubit register, respectively. Finally, using ⊕ as the bitwise XOR, $U_{f} : C^{2^{m + n}} \to C^{2^{m + n}}$ , $| x 〉 | y 〉 \mapsto | x 〉 | y \oplus f (x) 〉$ , defines the quantum oracle version of f.

Using the notational conventions related to quantum computing, Algorithm 2 specifies the CEA in pseudocode, and Figure 1 illustrates the quantum circuit of the CEA. In particular, the primary purpose of the CEA is to measure biased masks for vectorial Boolean functions. Specifically, the CEA exclusively outputs masks $(α, β) \in F_{2}^{m} \times F_{2}^{n}$ with $ε_{f} (α, β) \neq 0$ , as the probability of measuring a mask relates to its absolute bias.

Algorithm 2: Pseudocode description of the CEA

[Figure omitted. See PDF]

Based on the CEA specification, we highlight the quantum state of the CEA before measurement, explicitly $| ψ_{4} 〉$ , as displayed in Figure 1. In essence, Section 3 utilizes the state $| ψ_{4} 〉$ to describe the probability of measuring a mask that solves Problem 1. However, recalling the relationship between the bias and correlation of f, expressed by $2 \cdot ε_{f} (α, β) = C_{f} (α, β)$ , Theorem 3 specifies $| ψ_{4} 〉$ by underlining its relation to $C_{f} (α, β)$ .

Theorem 3

([17] Proposition 3). The quantum state of the CEA before the measurement is

(6) $\begin{matrix} | ψ_{4} 〉 = \frac{1}{\sqrt{2^{n}}} \sum_{α, β \in F_{2}^{m} \times F_{2}^{n}} C_{f} (α, β) | α 〉 | β 〉 . \end{matrix}$

The proof of Theorem 3 has already been provided by Hosoyamada [17]. Nonetheless, we restate it here as it serves as a step-by-step analysis of Algorithm 2.

Proof of Theorem 3.

The following proof is a detailed step-by-step analysis of Algorithm 2. Note that the line numbers from Algorithm 2 correspond to those in the following enumeration. Further, let $a \in {0, 1}^{m}$ and $b \in {0, 1}^{n}$ be bitstrings and $a | b$ denote their concatenation.

Initialize an m- and n-qubit register with $| ψ_{1} 〉 = {| 0 〉}^{\otimes m} {| 0 〉}^{\otimes n}$
$| ψ_{2} 〉 = (H^{\otimes m} \otimes I^{\otimes n}) | ψ_{1} 〉 = \frac{1}{\sqrt{2^{m}}} \sum_{x \in F_{2}^{m}} | x 〉 {| 0 〉}^{\otimes n}$
$| ψ_{3} 〉 = U_{f} | ψ_{2} 〉 = \frac{1}{\sqrt{2^{m}}} \sum_{x \in F_{2}^{m}} | x 〉 | f (x) 〉$
After applying $(H^{\otimes m} \otimes H^{\otimes n})$ to $| ψ_{3} 〉$ , the register $| ψ_{4} 〉$ is in the state
(7) $\begin{matrix} | ψ_{4} 〉 & = (H^{\otimes m} \otimes H^{\otimes n}) \frac{1}{\sqrt{2^{m}}} \sum_{x \in F_{2}^{m}} | x 〉 | f (x) 〉) \end{matrix}$

(8) $\begin{matrix} = \frac{1}{\sqrt{2^{2 m + n}}} \sum_{x \in F_{2}^{m}} \sum_{μ \in F_{2}^{m + n}} {(- 1)}^{〈 μ, x | f (x) 〉} | μ 〉 . \end{matrix}$
For $α, β \in F_{2}^{m} \times F_{2}^{n}$ , let $μ = α | β$ . Thus, Equation (8) can be rearranged as
(9) $\begin{matrix} | ψ_{4} 〉 & = \frac{1}{\sqrt{2^{2 m + n}}} \sum_{x \in F_{2}^{m}} \sum_{(α, β) \in F_{2}^{m} \times F_{2}^{n}} {(- 1)}^{〈 α | β, x | f (x) 〉} | α 〉 | β 〉 \end{matrix}$

(10) $\begin{matrix} = \frac{1}{\sqrt{2^{2 m + n}}} \sum_{(α, β) \in F_{2}^{m} \times F_{2}^{n}} \sum_{x \in F_{2}^{m}} {(- 1)}^{〈 α, x 〉 \oplus 〈 β, f (x) 〉} | α 〉 | β 〉 . \end{matrix}$
According to Definition 1, $W_{f} (α, β) = \sum_{x \in F_{2}^{m}} {(- 1)}^{〈 α, x 〉 \oplus 〈 β, f (x) 〉}$ holds and thus
(11) $\begin{matrix} | ψ_{4} 〉 = \frac{1}{\sqrt{2^{n}}} \sum_{(α, β) \in F_{2}^{m} \times F_{2}^{n}} \frac{W_{f} (α, β)}{2^{m}} | α 〉 | β 〉 . \end{matrix}$
Finally, Definition 2 leads to
(12) $\begin{matrix} | ψ_{4} 〉 = \frac{1}{\sqrt{2^{n}}} \sum_{(α, β) \in F_{2}^{m} \times F_{2}^{n}} C_{f} (α, β) | α 〉 | β 〉 . \end{matrix}$

□

Using the proof of Theorem 3, we highlight the techniques used in the CEA and its time complexity. In particular, step 3 shows that applying $U_{f}$ to the superposition of all $x \in F_{2}^{m}$ evaluates f for all inputs with one single oracle call (see Section 4 for a discussion of the time complexity of $U_{f}$ ). Further, utilizing $(H^{\otimes m} \otimes H^{\otimes n})$ , step 4 encodes the correlation of f for all masks in the amplitudes of the quantum state. As shown by Malviya and Tiwari [16], encoding the correlations of f for all masks with the CEA has an asymptotic time complexity that depends only on the depth of the circuit of $U_{f}$ .

As a result of Theorem 3, measuring $| ψ_{4} 〉$ using the standard basis, Algorithm 2 outputs a mask $(α, β) \in F_{2}^{m} \times F_{2}^{n}$ , whereby the probability of measuring it depends on its absolute correlation. To clarify, according to $2 \cdot ε_{f} (α, β) = C_{f} (α, β)$ , the greater the absolute bias of a mask, the more likely it is to be measured. Therefore, the CEA theoretically does not output masks with $ε_{f} (α, β) = 0$ . Section 3 and Section 4 examine the relationship between the absolute bias of a mask and the probability of measuring it with the CEA, demonstrating that the CEA can help address Problem 1.

3. Formalizing the Success Probability of the CEA

This section elaborates on the CEA, focusing on its probability of measuring a mask that solves Problem 1. More precisely, it investigates the success probability of measuring at least one mask that solves Problem 1 using $r \geq 1$ CEA samples. Describing the success probability of the CEA relies on the set S of all masks that solve Problem 1, formally introduced in Definition 3.

Definition 3.

The set of masks solving Problem 1, for $f : F_{2}^{m} \to F_{2}^{n}$ and $τ \in (0, 1 / 2]$ , is given by

(13) $\begin{matrix} S : = \{(α^{'}, β^{'}) \in F_{2}^{m} \times F_{2}^{n} | | ε_{f} (α^{'}, β^{'}) | \geq τ \land (α^{'}, β^{'}) \neq (0, 0)\} . \end{matrix}$

Incorporating the quantum state of the CEA before measuring a mask, as stated in Theorem 3, and the set S of masks that solve Problem 1, Theorem 4 specifies the probability of measuring at least one mask that solves Problem 1.

Theorem 4.

For $f : F_{2}^{m} \to F_{2}^{n}$ , $τ \in (0, 1 / 2]$ and r samples ${(α, β)}^{(1)}, \dots, {(α, β)}^{(r)} \in F_{2}^{m} \times F_{2}^{n}$ from the CEA, the probability to solve Problem 1 with at least one sample is

(14) $\begin{matrix} \Pr [⋁_{i = 1}^{r} {(α, β)}^{(i)} \in S] = 1 - {(1 - \frac{1}{2^{n}} \sum_{(α, β) \in S} C_{f} {(α, β)}^{2})}^{r} . \end{matrix}$

Proof of Theorem 4.

In order to solve Problem 1, only masks with $| ε_{f} (α, β) | \geq τ$ are relevant. Thus, from Theorem 3, it follows

(15) $\begin{matrix} \Pr [| ε_{f} (α, β) | \geq τ] = \frac{1}{2^{n}} \sum_{(α, β) \in S} C_{f} {(α, β)}^{2}, \end{matrix}$

which is the probability that a single execution of the CEA solves Problem 1. Further, utilizing Equation (15), the probability of solving Problem 1, with r repeated independent executions of the CEA, is given by

(16) $\begin{matrix} \Pr [⋁_{i = 1}^{r} {(α, β)}^{(i)} \in S] = 1 - {(1 - \frac{1}{2^{n}} \sum_{(α, β) \in S} C_{f} {(α, β)}^{2})}^{r} . \end{matrix}$

□

4. Complexity Analysis of the CEA

The CEA is a probabilistic algorithm that outputs biased masks. In detail, Theorem 4 shows that the probability of measuring a mask with bias threshold $τ$ depends on the number of nontrivial masks of f that satisfy $τ$ and the magnitude of $τ$ . Thus, analyzing the complexity of the CEA requires estimating the number of CEA samples needed to measure a mask, which solves Problem 1 with a fixed probability.

Estimating the lower and upper bounds on the number of CEA samples uses the following definitions of the worst and best cases to solve Problem 1. According to Theorem 4 and Definition 3, the best case occurs when

(17) $\begin{matrix} \frac{1}{2^{n}} \sum_{(α, β) \in S} C_{f} {(α, β)}^{2} = \frac{2^{n} - 1}{2^{n}} . \end{matrix}$

To clarify, Equation (17) follows by excluding the trivial mask. In contrast, we define the worst case by conservatively limiting the number of elements in the set S to $| S | = 1$ . As a remark, the conservative definition of the worst case ensures that estimating the upper bound of CEA samples includes the actual worst case. Using the best and worst cases, Theorem 5 describes the lower and the upper bounds of the number of CEA samples to measure a mask, which solves Problem 1 with a fixed probability.

Theorem 5.

Let $f : F_{2}^{m} \to F_{2}^{n}$ , $τ \in (0, 1 / 2]$ and $(1 - δ) \in (0, 1)$ . Then, there is a number r of CEA samples, satisfying

(18) $\begin{matrix} \frac{log (δ^{- 1})}{log (2^{n})} \leq r \leq \frac{log (δ)}{log (1 - 4 τ^{2} / 2^{n})}, \end{matrix}$

such that at least one sample solves Problem 1 with probability $(1 - δ)$ .

Proof of Theorem 5.

From Theorem 4, it follows that

(19) $\begin{matrix} 1 - {(1 - \frac{1}{2^{n}} \sum_{(α, β) \in S} C_{f} {(α, β)}^{2})}^{r} = 1 - δ . \end{matrix}$

To give an upper bound of samples, it is sufficient to assume the worst case $| S | = 1$ , in which only one nontrivial mask with $| ε_{f} (α, β) | \geq τ$ exists. For $| S | = 1$ , the following holds:

(20) $\begin{matrix} 1 - {(1 - \frac{4 τ^{2}}{2^{n}})}^{r} = 1 - δ \Leftrightarrow r = \frac{log (δ)}{log (1 - 4 τ^{2} / 2^{n})} . \end{matrix}$

The lower bound of samples is derived by the best case for the CEA. Specifically, the best case follows from Theorem 4, and excluding the trivial mask yields

(21) $\begin{matrix} \frac{1}{2^{n}} \sum_{(α, β) \in S} C_{f} {(α, β)}^{2} = \frac{2^{n} - 1}{2^{n}} . \end{matrix}$

Hence, in the best case, the CEA needs

(22) $\begin{matrix} 1 - {(1 - (\frac{2^{n} - 1}{2^{n}}))}^{r} = 1 - δ \Leftrightarrow r = \frac{log (δ^{- 1})}{log (2^{n})} \end{matrix}$

samples. From Equations (20) and (22), it follows that

(23) $\begin{matrix} \frac{log (δ^{- 1})}{log (2^{n})} \leq r \leq \frac{log (δ)}{log (1 - 4 τ^{2} / 2^{n})} . \end{matrix}$

□

Next, using the bounds of Theorem 5, this section provides the asymptotic number of samples required by the CEA to measure at least one mask that solves Problem 1, with Corollary 2 and Theorem 6 describing the best- and worst-case scenarios, respectively.

Corollary 2.

In the best case, with a probability of $(1 - δ) \in (0, 1)$ , at least one of $O (log (δ^{- 1}) / n)$ CEA samples solves Problem 1.

Theorem 6.

In the worst case, with a probability of $(1 - δ) \in (0, 1)$ and $τ \in (0, 1 / 2]$ , at least one of $O (log (δ^{- 1}) \cdot 2^{n} / τ^{2})$ CEA samples solves Problem 1.

Proof of Theorem 6.

This direct proof consists of two stages. The first stage presents an upper bound for Theorem 5 suitable for asymptotic estimation. The second stage then demonstrates the asymptotic upper bound using the bound from the first stage.

For the upper bound of Theorem 5, this paper chooses an additional upper bound. Specifically, for $x \in (0, 1)$ and $δ \in (0, 1)$ , the following holds:

(24) $\begin{matrix} log (1 - x) < - x \Leftrightarrow \frac{log (δ)}{log (1 - x)} < \frac{log (δ^{- 1})}{x} . \end{matrix}$

Next, substituting x in Equation (24) with $4 τ^{2} / 2^{n}$ leads to

(25) $\begin{matrix} \frac{log (δ)}{log (1 - 4 τ^{2} / 2^{n})} < \frac{log (δ^{- 1}) \cdot 2^{n}}{4 τ^{2}} . \end{matrix}$

From the upper bound of Theorem 5 given in Equation (25), the asymptotic bound is given by

(26) $\begin{matrix} \frac{log (δ^{- 1}) \cdot 2^{n}}{4 τ^{2}} = O (\frac{log (δ^{- 1}) \cdot 2^{n}}{τ^{2}}) . \end{matrix}$

In conclusion, the asymptotic upper bound of samples needed to measure at least one mask that solves Problem 1 is $O (log (δ^{- 1}) \cdot 2^{n} / τ^{2})$ . □

With the asymptotic bounds for the best- and worst-case scenarios, this paper now analyzes the query, memory, and time complexity of the CEA to measure at least one mask that solves Problem 1. Therefore, this paper discusses three quantum measures associated with the corresponding complexity in the gate model. We start our analysis with the query complexity of the CEA.

When estimating the query complexity of the CEA, it is necessary to consider the number of executions of its corresponding quantum oracle $U_{f}$ . The asymptotic number of CEA samples that contain, with a probability of $(1 - δ)$ , at least one mask that solves Problem 1 follows from Corollary 2 and Theorem 6. Consequently, the CEA needs $O (log (δ^{- 1}) / n)$ quantum oracle calls in the best case and $O (log (δ^{- 1}) \cdot 2^{n} / τ^{2})$ quantum oracle calls in the worst case.

Extending the analysis of complexities, this paper now examines the number of qubits of the CEA. In particular, the number of qubits the CEA requires depends on the number of input and output bits of f. As specified in Algorithm 2, the CEA needs $O (m + n)$ qubits.

Next, this paper discusses the time complexity of the CEA. Since the vectorial Boolean function f and its quantum oracle are unknown, $T_{f}$ and $T_{U_{f}}$ are placeholders of their circuit depth, respectively. According to Kitaev et al. [28] (Thm. 7.3), every function f is realizable as a quantum oracle $U_{f}$ with $T_{U_{f}} = O (T_{f})$ . Using the placeholder $T_{f}$ and incorporating the asymptotic query complexity of the CEA, the time complexity of the CEA is $O (log (δ^{- 1}) \cdot T_{f} / n)$ in the best case and $O (log (δ^{- 1}) \cdot 2^{n} \cdot T_{f} / τ^{2})$ in the worst case.

Table 2 summarizes the asymptotic time, query, and memory complexities of the CEA for measuring masks with a prescribed absolute bias $τ$ , illustrating that query and time complexity depend mainly on the choice of f and $τ$ . In detail, the success probability of the CEA according to Theorem 4, the prescribed absolute bias $τ$ , the time complexity $T_{f}$ , and the number of output bits of f affect its asymptotic behavior. In addition, the success probability of the CEA has only a logarithmic impact, allowing the success probabilities to be exponentially close to one. Consequently, in the worst case, the capabilities of the CEA to measure masks for solving Problem 1 in practice are limited to functions with polynomial time $(T_{f} = poly (m + n))$ , a relatively small output size, e.g., $n \leq 32$ , and at least one nontrivial mask $(α, β)$ with a constant absolute bias, e.g., $| ε_{f} (α, β) | = τ = 1 / 2$ .

Having established the complexity of the CEA for measuring a mask that addresses Problem 1, Algorithm 3 presents an approach that resolves Problem 1 using the CEA. The approach is straightforward, as it generates masks using the CEA and checks them to solve Problem 1. Hence, the aforementioned limitations of the CEA in measuring a mask that solves Problem 1 also affect Algorithm 3. Subsequently, Theorem 7 states the time and oracle complexities, as well as the classical space complexity and the quantum space complexity of Algorithm 3. By convention, we treat a classical computation step and the application of a quantum gate as equivalent. The reason for merging the oracle complexities is due to our treatment of the given classical and quantum oracles as equivalent in terms of complexity. However, we differentiate between the space and the qubit complexities to highlight the advantage the CEA provides in terms of bits and qubits used, which is exponential in comparison with, e.g., the classical solution using Brown’s FWT algorithm Algorithm 1 (see Section 6).

Algorithm 3: Pseudocode description of solving Problem 1 using the CEA

[Figure omitted. See PDF]

Theorem 7.

For $f : F_{2}^{m} \to F_{2}^{n}$ and its quantum oracle $U_{f} : C^{2^{m + n}} \to C^{2^{m + n}}$ with time complexities $O (T_{f}) = poly (n + m)$ , a threshold $τ \in (0, 1 / 2]$ , and $δ \in (0, 1)$ , Algorithm 3 solves Problem 1 with a success probability of $(1 - δ)$ , a time complexity of $O (log (δ^{- 1}) \cdot T_{f} \cdot 2^{m + n} / τ^{2})$ , an oracle complexity of $O (log (δ^{- 1}) \cdot 2^{m + n} / τ^{2})$ , a classical space complexity of $O (m + n)$ , and $O (m + n)$ qubits.

The reason behind setting $O (T_{f}) = poly (n + m)$ is that it simplifies the proof of Theorem 7 and makes the resulting asymptotic time complexity more compact.

Proof of Theorem 7.

Calculating the time complexity of Algorithm 3 is straightforward. Due to $T_{U_{f}} = O (T_{f}) = poly (n + m)$ , the time complexity of lines 1–9 is clearly dominated by the direct calculation of $W_{f} (α, β)$ in line 5 and the for loop in line 3. According to Corollary 1 and $O (T_{f}) = poly (n + m)$ , line 5 has a time complexity of $O (T_{f} \cdot 2^{m})$ . Further, in the worst case, line 5 is repeated r times. Thus, in the worst case, Algorithm 3 has a time complexity of $O (log (δ^{- 1}) \cdot T_{f} \cdot 2^{m + n} / τ^{2})$ .

Next, we investigate the oracle complexity of Algorithm 3. In detail, Algorithm 3 calls f in line 5 and $U_{f}$ in line 4. Due to Corollary 1, line 5 dominates with $O (2^{m})$ calls of f, which is repeated r times in the worst case. As r is given directly in line 2, we conclude the oracle complexity of $O (log (δ^{- 1}) \cdot 2^{m + n} / τ^{2})$ .

Now, we estimate the space complexity of Algorithm 3. We highlight that the computation of the bias in line 5 would be performed in place. Therefore, the dominating factor for the classical space complexity is the space needed for the mask pair $r e s$ , giving the space complexity as $O (m + n)$ .

Subsequently, we prove the number of qubits used by Algorithm 3. With line 4, Algorithm 3 executes the CEA, determining its required qubits. As shown in Table 2, the CEA uses $O (m + n)$ qubits, as does Algorithm 3.

Last but not least, we discuss the probability of success of Algorithm 3. Specifically, Algorithm 3 succeeds if the expression in line 5 is evaluated as true. In particular, according to Theorem 1, the inequation in line 5 is true if and only if, in line 4, the CEA measures a mask that solves Problem 1. Thus, the success probability of Algorithm 3 directly depends on the probability of the CEA to measure at least one mask that solves Problem 1. Hence, using the upper bound of Theorem 5, the number of samples r in line 2 reflects the success probability of Algorithm 3. □

5. Empirical Study of the CEA

This paper complements the theoretical work of Section 3 and Section 4 by presenting an empirical study of specific vectorial Boolean functions to verify the capabilities of the CEA in measuring a mask that solves Problem 1. Since the probability of success of the CEA depends on the distribution of the Walsh transform of the vectorial Boolean function, this paper conducted a detailed study of two functions with different Walsh transform distributions. Figure 2 displays the distribution of the Walsh transform of the examined functions, the AES S-box [29] (Section 5.1.1) and the 8-bit XOR cipher with a fixed key $k \in F_{2}^{8}$ , defined as $XOR : F_{2}^{8} \times F_{2}^{8}; x \mapsto x \oplus k$ .

5.1. Methodology

This study conducted controlled randomized experiments that executed the CEA repeatedly to measure the number of samples required to obtain a mask with an absolute bias greater than or equal to a fixed threshold $τ \in [0, 1 / 2]$ concerning the utilized vectorial Boolean function. This approach aimed to validate Theorem 4 by comparing the experimental results with the theoretical prediction.

Selection of functions: We chose the AES S-box and an 8-bit XOR cipher as the target functions due to their different Walsh transform distributions. In particular, according to Figure 2, the distribution of the Walsh transforms of the AES S-box reminds us of a normal distribution, and the Walsh transforms of the XOR cipher are concentrated on zero, with relatively few exceptions. Further, as can be deduced from Theorem 4, according to their different Walsh transform distributions, the probabilities of success of these functions for finding a nontrivial mask with the lowest possible absolute bias differ significantly. Hence, by analyzing the XOR cipher and the AES S-box, we gain insight into the behavior of the CEA for measuring a mask with a prescribed absolute bias, which is relatively likely or unlikely, respectively.
Carrying out the experiments: Given the theoretical focus of this paper, we tested the CEA in a simulation using a classical computer. This simulation served as a practical application of our theoretical work, allowing us to observe the behavior of the CEA in a controlled environment.
Parameter initialization: Each function obtained a seed, defined as the sum of the first three digits of a transcendent number and a random integer (see the experimental setup for details), ensuring the exact reproducibility of the experiment. Further, the threshold value for the bias $τ$ for nontrivial masks was determined based on the highest achievable absolute bias for each function.
Experiments and data collection: We conducted 3000 independent experiments each for the AES S-box and the XOR cipher. Each experiment repeatedly executed the CEA until a returned mask solved Problem 1 while storing each mask.
Analysis: Based on the results of the experiments, we used the Clopper–Pearson intervals [30] to provide evidence that the probability of the experiments differed only by a small constant from the probability in Theorem 4.

5.2. Experimental Setup

Algorithm 4 specifies the experiments performed for the AES S-box and the XOR cipher with the integer 89 as a fixed key, where f is a placeholder for the functions.

According to Algorithm 4, $ς = ⌊π \cdot 10^{3}⌋ + 0xCA684ACA$ denotes the seed for the AES S-box, and $ς = ⌊e \cdot 10^{3}⌋ + 0xABA640E0$ is the seed for the XOR cipher. The random seed values were generated using the free service from random.org. Further, the highest threshold value for $τ$ was $1 / 16$ in the case of the AES S-box and $1 / 2$ in the case of the XOR cipher.

The experiments were implemented in Python using the Qiskit software (Version Number: 3) stack [31] for quantum computing, and the code is available on GitHub [32]. In order to optimize the code to run efficiently on standard consumer hardware, we addressed the implementation of the quantum oracle $U_{f}$ using sparse matrices from SciPy [33]. We executed the experiments using an AMD Ryzen 7 PRO 6850U in about 5 min and 47 s.

During the simulation of the CEA, we initialized the quantum register with Qiskit and then realized the rest of the CEA in a custom simulation. To clarify, $U_{f}$ was applied by manually multiplying $U_{f}$ by the state vector. Subsequently, similarly to $U_{f}$ , we manually applied $H^{\otimes (m + n)}$ to the state vector. Ultimately, we performed the measurement by sampling the mask according to the weights in the state vector using the standard random.choices function of Python.

Algorithm 4: Generic pseudocode description of the experiments

[Figure omitted. See PDF]

5.3. Results

Figure 3 displays a boxplot that presents the results of the experiments for the AES S-box and the XOR cipher, with the lower whisker set at one and the upper whisker set at 99, representing the number of CEA measurements required to obtain a mask that solved Problem 1. For the AES S-box, we had a minimum value of one, a lower quartile (25th percentile) of 18, a median (50th percentile) of 36, an upper quartile (75th percentile) of 53, and a maximum value of 99. In addition, Figure 4 illustrates the theoretical probability of Theorem 4 and the empirically determined probability from the experiments with the AES S-box to measure a mask that solves Problem 1 with r samples, whereby there is not much visual difference. Further, for the XOR cipher, we had 2982 experiments with one single measurement and 18 experiments with two measurements, while the empirically estimated probability was close to the probability in Theorem 4. Overall, the results were in line with our theoretical work.

5.4. Analysis

To verify the significance of the estimated probabilities of the experiments, we used Clopper–Pearson confidence intervals [30] with a confidence level of $γ = 99 %$ each. In particular, we calculated confidence intervals for all the numbers r of sampled masks needed to measure a mask to solve Problem 1 for the AES S-box and the XOR cipher experiments. For the AES S-box, Figure 4 displays the confidence intervals, the relative frequencies of the experiments that solve Problem 1 with r samples, and the probabilities $p_{r}$ from Theorem 4.

All measured probabilities lay within the respective confidence intervals. For the individual confidence intervals with $r \geq 10$ for the AES S-box and $r \geq 1$ for the XOR cipher, the probability of the experiments differed practically negligibly from the theoretical results. We further highlight this fact by giving the absolute relative deviations of the boundaries of the confidence intervals from the theoretically obtained success probabilities for the 3000 AES S-box experiments in Figure 5. The absolute relative deviation is given by the term $| p_{r} - p_{r}^{'} | / p_{r}$ , where $p_{r}^{'}$ is one of the boundaries of the confidence interval. The plot shows the deviations using a logarithmic scale, illustrating the strictly monotonic decline with the increase in the count of samples measured until success r. Starting with $r = 10$ , the absolute relative deviations became less than $5 %$ , from which we considered them negligible. We observed a narrower behavior in the case of the experiments on the XOR cipher, where the absolute relative deviations were less than $1 %$ for $r = 1$ and $r = 2$ , which were the sample counts observed for solving Problem 1.

The deviations between the observed intervals did not directly indicate a potential bias or limitation in the experiments. In particular, the Clopper–Pearson interval is conservative [34], which means that high confidence ( $γ = 99 %$ ) could lead to larger intervals considering the statistical variability in the experiments. In addition, the code developed for this study was rigorously tested during its creation and was written in Python. It reflected the noiseless execution of the CEA on an idealized quantum computer whilst having been executed on a classical machine. Therefore, there was no evidence of bias or limitations in this study. The deviations between the intervals depended on the initial seed $ς$ , as it gave the random choices made by the standard pseudorandom number generator by Python, which corresponded to the quantum measurement results obtained by the CEA.

Considering the previous discussion, we may conclude that the associated confidence interval helps confirm Theorem 4 for the AES S-box and the XOR cipher, as it indicates that the theory also applies in general.

6. Discussion

This section begins by exploring the applications of the CEA in linear cryptanalysis. Then, it asymptotically compares Algorithm 3, an approach using the CEA, with Algorithm 1, which uses the FWT. Finally, this section discusses the capabilities of the CEA for linear cryptanalysis.

The CEA has two main applications in linear cryptanalysis. When attacking a cipher with linear cryptanalysis, masks with a prescribed bias are necessary. Since the primary purpose of the CEA is to measure a biased mask, it can be applied to solve Problem 1. In addition to attacking a cipher, the CEA helps design ciphers. Specifically, using Algorithm 3 can probabilistically prove that there is no mask with a particular nonzero bias. In addition, this paper emphasizes that proving the absence of masks with a particular bias using the CEA is an empirical approach that might only be acceptable in some scenarios.

Having explored the two main applications of the CEA in linear cryptanalysis, the next step here would be to compare the complexity of Algorithm 3, an algorithm that solves Problem 1 using the CEA, with Algorithm 1, which solves Problem 1 using the FWT. In contrast to Algorithm 1, as shown in Theorem 7, the time complexity of Algorithm 3 additionally depends on the threshold $τ \in (0, 1 / 2]$ and the probability of success $(1 - δ) \in (0, 1)$ . Setting these variables to unrealistic low values would give a misleading comparison and conceal the potential of the CEA in linear cryptanalysis. Therefore, we specify Scenario 1, which defines the setting of our comparison.

Scenario 1.

A function $f : F_{2}^{m} \to F_{2}^{n}$ with circuit depths $O (T_{f}) = poly (n + m)$ and $T_{U_{f}} = O (T_{f})$ , together with probability $δ = 1 / {(m + n)}^{2}$ and absolute bias $τ \in (0, 1 / 2]$ with $τ = const$ , defines the comparison scenario for Algorithms 1 and 3.

As specified in Scenario 1, the comparison scenario asymptotically fixes four variables, and the following discusses the reasonability behind these choices.

In practice, ciphers must be efficiently computable. Therefore, this paper concludes that assessing functions with $T_{f} = poly (m + n)$ using linear cryptanalysis is a reasonable assumption.
As mentioned, Kitaev et al. [28] (Thm. 7.3) prove that every function f is realizable as quantum oracle $U_{f}$ with $T_{U_{f}} = O (() T_{f})$ .
As Theorem 7 shows, the probability of failure $δ$ increases the time and query complexity of Algorithm 3 only logarithmically. Hence, this paper conservatively sets $δ = 1 / {(m + n)}^{2}$ and argues that smaller values would be unreasonable. To clarify, if $m + n > 10$ , then the success probability $(1 - δ)$ of Algorithm 3 is greater than $0.99$ .
This paper focuses on linear cryptanalysis, specifically Matsui’s Algorithms 1 and 2, whose data complexity, illustrated in Table 1, grows with smaller biases. However, the data complexity cannot exceed a specific boundary for practical reasons. To clarify, before attacking a cipher with Algorithms 1 or 2, it is necessary to collect plaintext–ciphertext pairs or at least ciphertexts for the same key, respectively. Since the available computational resources limit the size of manageable data complexities, collecting a vast quantity of data is impractical. Furthermore, recalling the relation between bias and data complexity, a limit for data complexity also limits the lower bound of the absolute bias used by Algorithms 1 or 2. Hence, this paper argues that $τ = const$ is reasonable.

After addressing the rationality of variable choices in Scenario 1, this article compares Algorithm 1 with Algorithm 3 based on Scenario 1. For this purpose, this paper applies Scenario 1 to Theorems 2 and 7, whereby Table 3 displays the result. In addition, the following paragraphs detail the comparison of the time complexity, the oracle complexity, and the requirements for space and qubits.

In the scenario specified in Scenario 1, the time complexity of Algorithm 3 has an asymptotic advantage over Algorithm 1, reducing a linear factor to a logarithmic one. However, in contrast to Algorithm 1, Algorithm 3 has the potential to improve its time complexity. In detail, in the context of testing the bias of a mask (line 5), Algorithm 3 uses a direct approach to calculate the Walsh transform, which inflicts an exponential time complexity of $O ((m + n + T_{f}) \cdot 2^{m})$ . Applying a more efficient approach to line 5 would improve the time complexity of Algorithm 3. Nonetheless, finding an efficient approach for calculating the Walsh transform is beyond the scope of this paper and is considered future work, which is more detailed in Section 7.

As stated in Section 4, we do not differentiate between classical and quantum oracle complexity. The oracle complexity for Algorithm 1 has an asymptotic advantage of a logarithmic factor over Algorithm 3. Nevertheless, similar to the time complexity, using a more efficient way of calculation, the Walsh transform in Algorithm 3 could improve its oracle complexity by potentially decreasing the number of evaluations of f.

Compared to the query complexity and neglecting the additional qubits, the space complexity of Algorithm 3 has an exponential advantage over that of Algorithm 1. In particular, Algorithm 1 has a space complexity of $O (2^{m})$ . In contrast, Algorithm 3 has a space complexity of $O (n + m)$ , demonstrating an exponential advantage. Remarkably, for Algorithm 3, this advantage comes at the cost of only using $O (m + n)$ qubits.

Beyond the advantages shown by comparing Algorithm 1 with Algorithm 3, we highlight the potential of the CEA. The quantum computing approach with the CEA offers a probabilistic method for choosing biased masks. According to Theorem 6, the CEA can reduce the mask search space from $O (2^{m + n})$ to $O (log (δ^{- 1}) \cdot 2^{n} / τ^{2})$ , which, depending on the choice of $τ \in (0, 1 / 2]$ and $δ \in (0, 1)$ , is an exponential advantage. Therefore, the CEA enables a more direct search for biased masks while filtering masks with zero bias. Neglecting the unresolved issue of efficiently checking the biases, the CEA is useful in specific scenarios that profit from a reduced search space. Specifically, scenarios with a vectorial Boolean function $f : F_{2}^{m} \to F_{2}^{n}$ with one nontrivial mask $(α, β) \in F_{2}^{m} \times F_{2}^{n}$ , a large constant absolute bias, e.g., $| ε_{f} (α, β) | = 1 / 2 - c$ where $c > 0$ is negligibly small, and a time complexity of $T_{f} = poly (m + n)$ . In the stated scenario, according to Theorem 6, the CEA can measure that mask with a probability of $1 - 1 / {(m + n)}^{2}$ , a time complexity of $O (log (m + n) \cdot T_{f} \cdot 2^{n})$ , and $O (log (m + n) \cdot 2^{n})$ queries. Remarkably, in this scenario, the number of queries is only exponential in the number of output bits of f, which makes it applicable for functions with $n \leq 32$ .

7. Conclusions

Finding masks for $f : F_{2}^{m} \to F_{2}^{n}$ with a prescribed absolute bias for linear cryptanalysis is assumed to be challenging, and this paper showed that the CEA could support this search. In addition to formalizing the success probability of CEA, we provided an asymptotic analysis that proved its capabilities to measure masks with a prescribed absolute bias. The theory was confirmed through an empirical study using a quantum computer simulation on the AES S-box and the XOR cipher with a fixed key. Furthermore, applying a practical scenario (searching for masks with a large constant absolute bias), we demonstrated that the approach using the CEA hads an asymptotic advantage, reducing a linear factor to a logarithmic one in terms of time complexity and an exponential advantage in terms of space compared to a classical approach using the FWT (see Table 3 for details). The exponential time complexity in finding a mask with a prescribed absolute bias makes the CEA suitable for functions with $(m + n \leq 32)$ . Nonetheless, neglecting the time complexity to check the bias of a mask, in specific scenarios, the CEA can reduce the search space from $O (2^{m + n})$ to $O (log (m + n) \cdot 2^{n})$ masks by executing the CEA only $O (log (m + n) \cdot 2^{n})$ times.

Although CEA probabilistically guarantees the output of a mask with a prescribed absolute bias, it does not determine it. Efficiently determining the actual bias of a mask is a crucial next step in using the CEA to support linear cryptanalysis, but it is beyond the scope of this paper. We took a step towards solving this problem by rigorously giving the relationship between the bias of a mask and its associated Walsh transform, proving that a direct computation of the bias must be of order $O ((m + n + T_{f}) \cdot 2^{m})$ , where $T_{f}$ is the time complexity of f. From the definition of the Walsh transform itself, it is not apparent how to reduce this exponential complexity; thus, it poses the main challenge to solve this problem.

Future directions might involve deeper studies of the properties of the Walsh transform, the development of efficient algorithms, and possibly quantum algorithms, or hardness proofs by reducing the problem of computing the Walsh transform of a function to a computationally hard problem. Reducing the exponent for obtaining a complexity term of, e.g., $O (2^{c m})$ with $c \in (0, 1)$ would broaden the range of applicable functions with each bit. Specifically, a value of $c = 1 / 4$ would allow the determination of Walsh transforms of ciphers with 128 input bits, although we consider this value unattainable at this time, considering the state of the art. Determining the Walsh transform of masks and thus their biases will be the focus of our future work as we continue to explore the capabilities of the CEA in the context of linear cryptanalysis.

Author Contributions

Conceptualization: C.G.; data curation: C.G. and V.P.; formal analysis: C.G.; funding acquisition: M.M., F.M. and H.E.; investigation: C.G. and V.P.; methodology: C.G.; project administration: C.G., H.E. and F.M.; software: V.P. and C.G.; supervision: C.G., H.E. and M.M.; validation: C.G., V.P., H.E., F.M., H.H. and M.M.; visualization: V.P. and C.G.; writing—original draft: C.G.; writing—review and editing: C.G., V.P., H.E., F.M., H.H. and M.M. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

The data of the empirical study are provided in a GitHub repository [32].

Acknowledgments

This article was written as part of the Qu-Gov project, which was commissioned by the German Federal Ministry of Finance. The authors want to extend their gratitude to Oliver Muth, Yvonne Ripke, and Andreas Wilke for their continuous encouragement and support. Furthermore, the authors wish to thank the reviewers from the journal for their valuable criticism and helpful suggestions, which considerably helped in improving the quality of this article.

Conflicts of Interest

Authors Holger Eble and Frank Morgner were employed by Bundesdruckerei GmbH. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript; or in the decision to publish the results.

Abbreviations

The following abbreviations are used in this manuscript:

AES	Advanced Encryption Standard
CEA	Correlation Extraction Algorithm
DES	Data Encryption Standard
FEAL	Fast Data Encipherment Algorithm
FWT	Fast Walsh transform
RAM	Random Access Machine
SPN	Substitution–permutation network
RRAM	Real Random Access Machine

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Figure 1. The quantum circuit of the CEA.

Figure 2. Distribution of the Walsh transform of the AES S-box and 8-bit XOR cipher.

Figure 3. Boxplot of 3000 experiments, where each point marks the number of samples required for an experiment.

View Image - Figure 4. Plot of the Clopper–Pearson confidence intervals for the probabilities of the 3000 AES S-box experiments to solve Problem 1 using r samples and the probabilities of Theorem 4.

Figure 4. Plot of the Clopper–Pearson confidence intervals for the probabilities of the 3000 AES S-box experiments to solve Problem 1 using r samples and the probabilities of Theorem 4.

View Image - Figure 5. Plot of the absolute relative deviations of the boundaries of the Clopper–Pearson confidence intervals from the predictions obtained using Theorem 4 during 3000 AES S-box experiments.

Figure 5. Plot of the absolute relative deviations of the boundaries of the Clopper–Pearson confidence intervals from the predictions obtained using Theorem 4 during 3000 AES S-box experiments.

Table 1

Data complexity values for specific success rates of Matsui’s Algorithm 1 [20].

Success rate	$84.1 %$	$92.1 %$	$97.7 %$	$99.8 %$
Data complexity	$1 / 4 \cdot ε_{f} {(α, β)}^{- 2}$	$1 / 2 \cdot ε_{f} {(α, β)}^{- 2}$	$ε_{f} {(α, β)}^{- 2}$	$2 \cdot ε_{f} {(α, β)}^{- 2}$

Remark: The data complexity is the number of plaintext–ciphertext pairs needed to achieve a given success rate.

Table 2

Asymptotic complexities of the CEA for measuring at least one mask that solves Problem 1.

Complexity	Best Case	Worst Case
Time	$O (\frac{log (δ^{- 1}) \cdot T_{f}}{n})$	$O (\frac{log (δ^{- 1}) \cdot T_{f} \cdot 2^{n}}{τ^{2}})$
Quantum queries	$O (\frac{log (δ^{- 1})}{n})$	$O (\frac{log (δ^{- 1}) \cdot 2^{n}}{τ^{2}})$
Qubits	$O (m + n)$

Remark: Let $(1 - δ) \in (0, 1)$ be the success probability of the CEA, $τ \in (0, 1 / 2]$ the prescribed absolute bias, and $T_{f}$ the time complexity of f.

Table 3

Worst-case comparison of Algorithm 1 using the FWT and Algorithm 3 utilizing the CEA for solving Problem 1 in the scenario specified by Scenario 1.

Complexity	Algorithm 1 (FWT)	Algorithm 3 (CEA)
Time	$O ((n \cdot T_{f} + m) \cdot 2^{m + n})$	$O (log (m + n) \cdot T_{f} \cdot 2^{m + n})$
Oracle queries	$O (2^{m + n})$	$O (log (m + n) \cdot 2^{m + n})$
Space complexity	$O (2^{m})$	$O (m + n)$
Qubits	-	$O (m + n)$

Remark: Let $f : F_{2}^{m} \to F_{2}^{n}$ be a vectorial Boolean function, and $T_{f}$ its time complexity.

References

1. Gill, S.S.; Kumar, A.; Singh, H.; Singh, M.; Kaur, K.; Usman, M.; Buyya, R. Quantum computing: A taxonomy, systematic review and future directions. Softw. Pract. Exp.; 2022; 52, pp. 66-114. [DOI: https://dx.doi.org/10.1002/spe.3039]

2. Shor, P. Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science; Santa Fe, NM, USA, 20–22 November 1994; pp. 124-134. [DOI: https://dx.doi.org/10.1109/SFCS.1994.365700]

3. Gerjuoy, E. Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers. Am. J. Phys.; 2005; 73, pp. 521-540. [DOI: https://dx.doi.org/10.1119/1.1891170]

4. Proos, J.; Zalka, C. Shor’s Discrete Logarithm Quantum Algorithm for Elliptic Curves. Quantum Inf. Comput.; 2003; 3, pp. 317-344. [DOI: https://dx.doi.org/10.26421/QIC3.4-3]

5. Larasati, H.T.; Kim, H. Quantum Cryptanalysis Landscape of Shor’s Algorithm for Elliptic Curve Discrete Logarithm Problem. Information Security Applications; Kim, H. Springer: Cham, Switzerland, 2021; pp. 91-104. [DOI: https://dx.doi.org/10.1007/978-3-030-89432-0_8]

6. Grassl, M.; Langenberg, B.; Roetteler, M.; Steinwandt, R. Applying Grover’s Algorithm to AES: Quantum Resource Estimates. Post-Quantum Cryptography; Takagi, T. Springer: Cham, Switzerland, 2016; pp. 29-43. [DOI: https://dx.doi.org/10.1007/978-3-319-29360-8_3]

7. Hasija, T.; Ramkumar, K.R.; Kaur, A.; Mittal, S.; Singh, B. A Survey on NIST Selected Third Round Candidates for Post Quantum Cryptography. Proceedings of the 2022 7th International Conference on Communication and Electronics Systems (ICCES); Coimbatore, India, 22–24 June 2022; pp. 737-743. [DOI: https://dx.doi.org/10.1109/ICCES54183.2022.9835864]

8. Burek, E.; Wroński, M.; Mańk, K.; Misztal, M. Algebraic Attacks on Block Ciphers Using Quantum Annealing. IEEE Trans. Emerg. Top. Comput.; 2022; 10, pp. 678-689. [DOI: https://dx.doi.org/10.1109/TETC.2022.3143152]

9. Chen, Y.A.; Gao, X.S. Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems. J. Syst. Sci. Complex.; 2022; 35, pp. 373-412. [DOI: https://dx.doi.org/10.1007/s11424-020-0028-6]

10. Ding, J.; Gheorghiu, V.; Gilyén, A.; Hallgren, S.; Li, J. Limitations of the Macaulay Matrix Approach for Using the HHL Algorithm to Solve Multivariate Polynomial Systems. Quantum; 2023; 7, 1069. [DOI: https://dx.doi.org/10.22331/q-2023-07-26-1069]

11. Kaplan, M.; Leurent, G.; Leverrier, A.; Naya-Plasencia, M. Quantum Differential and Linear Cryptanalysis. IACR Trans. Symmetric Cryptol.; 2016; 2016, pp. 71-94. [DOI: https://dx.doi.org/10.46586/tosc.v2016.i1.71-94]

12. Zhou, Q.; Lu, S.; Zhang, Z.; Sun, J. Quantum Differential Cryptanalysis. Quantum Inf. Process.; 2015; 14, pp. 2101-2109. [DOI: https://dx.doi.org/10.1007/s11128-015-0983-3]

13. David, N.; Naya-Plasencia, M.; Schrottenloher, A. Quantum Impossible Differential Attacks: Applications to AES and SKINNY. Des. Codes Cryptogr.; 2024; 92, pp. 723-751. [DOI: https://dx.doi.org/10.1007/s10623-023-01280-y]

14. Zou, H.; Zou, J.; Luo, Y. New Results on Quantum Boomerang Attacks. Quantum Inf. Process.; 2023; 22, 171. [DOI: https://dx.doi.org/10.1007/s11128-023-03921-6]

15. Xie, H.; Yang, L. Quantum Truncated Differential and Boomerang Attack. Symmetry; 2024; 16, 1124. [DOI: https://dx.doi.org/10.3390/sym16091124]

16. Malviya, A.K.; Tiwari, N. Linear approximation of a vectorial Boolean function using quantum computing. EPL (Europhys. Lett.); 2020; 132, 40001. [DOI: https://dx.doi.org/10.1209/0295-5075/132/40001]

17. Hosoyamada, A. Quantum Speed-Up for Multidimensional (Zero Correlation) Linear Distinguishers. Advances in Cryptology—ASIACRYPT 2023; Guo, J.; Steinfeld, R. Lecture Notes in Computer Science Springer: Singapore, 2023; pp. 311-345. [DOI: https://dx.doi.org/10.1007/978-981-99-8727-6_11]

18. Malviya, A.K.; Tiwari, N. Quantum linear cryptanalysis on a toy cipher. Pramana; 2023; 97, 63. [DOI: https://dx.doi.org/10.1007/s12043-023-02529-w]

19. Matsui, M.; Yamagishi, A. A New Method for Known Plaintext Attack of FEAL Cipher. Advances in Cryptology—EUROCRYPT’ 92; Rueppel, R.A. Springer: Berlin/Heidelberg, Germany, 1993; pp. 81-91. [DOI: https://dx.doi.org/10.1007/3-540-47555-9_7]

20. Matsui, M. Linear Cryptanalysis Method for DES Cipher. Advances in Cryptology — EUROCRYPT ’93; Helleseth, T. Springer: Berlin/Heidelberg, Germany, 1994; pp. 386-397. [DOI: https://dx.doi.org/10.1007/3-540-48285-7_33]

21. Kaliski, B.S.; Robshaw, M.J.B. Linear Cryptanalysis Using Multiple Approximations. Advances in Cryptology — CRYPTO ’94; Desmedt, Y.G. Springer: Berlin/Heidelberg, Germany, 1994; pp. 26-39. [DOI: https://dx.doi.org/10.1007/3-540-48658-5_4]

22. Hermelin, M.; Cho, J.Y.; Nyberg, K. Multidimensional Extension of Matsui’s Algorithm 2. Fast Software Encryption; Dunkelman, O. Springer: Berlin/Heidelberg, Germany, 2009; pp. 209-227. [DOI: https://dx.doi.org/10.1007/978-3-642-03317-9_13]

23. Bogdanov, A.; Rijmen, V. Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Des. Codes Cryptogr.; 2014; 70, pp. 369-383. [DOI: https://dx.doi.org/10.1007/s10623-012-9697-z]

24. Brown,. A Recursive Algorithm for Sequency-Ordered Fast Walsh Transforms. IEEE Trans. Comput.; 1977; C-26, pp. 819-822. [DOI: https://dx.doi.org/10.1109/TC.1977.1674921]

25. Cui, J.; Guo, J. Quantum cryptographic property testing of multi-output Boolean functions. Quantum Inf. Process.; 2019; 18, 182. [DOI: https://dx.doi.org/10.1007/s11128-019-2299-1]

26. Li, H. Quantum Algorithms for the Resiliency of Vectorial Boolean Functions. Int. J. Theor. Phys.; 2021; 60, pp. 1565-1573. [DOI: https://dx.doi.org/10.1007/s10773-021-04779-z]

27. Carlet, C. Vectorial Boolean Functions for Cryptography. Boolean Models and Methods in Mathematics, Computer Science, and Engineering; Hammer, P.L.; Crama, Y. Encyclopedia of Mathematics and Its Applications Cambridge University Press: Cambridge, UK, 2010; pp. 398-470. [DOI: https://dx.doi.org/10.1017/CBO9780511780448.012]

28. Kitaev, A.Y.; Shen, A.H.; Vyalyi, M.N. Classical and Quantum Computation; AMS, American Mathematical Society: Providence, RI, USA, 2002; Volume 47, Chapter 2, 64.

29. Dworkin, M.J.; Turan, M.S.; Mouha, N. Advanced Encryption Standard (AES); National Institute of Standards and Technology: Gaithersburg, MD, USA, 2023.

30. Clopper, C.J.; Pearson, E.S. The Use of Confidence or Fiducial Limits Illustrated in the Case of the Binomial. Biometrika; 1934; 26, pp. 404-413. [DOI: https://dx.doi.org/10.1093/biomet/26.4.404]

31. Javadi-Abhari, A.; Treinish, M.; Krsulich, K.; Wood, C.J.; Lishman, J.; Gacon, J.; Martiel, S.; Nation, P.D.; Bishop, L.S.; Cross, A.W. et al. Quantum Computing with Qiskit. arXiv; 2024; arXiv: 2405.08810Version Number: 3 [DOI: https://dx.doi.org/10.48550/ARXIV.2405.08810]

32. Graebnitz, C.; Margraf, M.; Pickel, V. Emperical-Study-Correlation-Extraction-Algorithm. Available online: https://github.com/JCTHRG/Emperical-Study-Correlation-Extraction-Algorithm (accessed on 13 August 2024).

33. Virtanen, P.; Gommers, R.; Oliphant, T.E.; Haberland, M.; Reddy, T.; Cournapeau, D.; Burovski, E.; Peterson, P.; Weckesser, W.; Bright, J. et al. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nat. Methods; 2020; 17, pp. 261-272. [DOI: https://dx.doi.org/10.1038/s41592-019-0686-2]

34. Chen, X.; Zhou, K.; Aravena, J.L. On the Binomial Confidence Interval and Probabilistic Robust Control. Automatica; 2004; 40, pp. 1787-1789. [DOI: https://dx.doi.org/10.1016/j.automatica.2004.04.016]

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

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

Content area

Abstract

Full text

1.1. Contribution

1.2. Related Work

1.3. Organization

2. Preliminaries

2.1. Linear Cryptanalysis

2.2. The Correlation Extraction Algorithm (CEA)

3. Formalizing the Success Probability of the CEA

4. Complexity Analysis of the CEA

5. Empirical Study of the CEA

5.2. Experimental Setup

5.4. Analysis