# Lemma 5 in Matsui's Paper about Linear Cryptanalysis

I have a problem about the formula in Matsui's paper about linear cryptanalysis.

Let $$N$$ be the number of given random plaintexts, p be the probability that equation $$P[i_1,i_2,\cdots,i_a]\oplus C[j_1,j_2,\cdots,j_b]\oplus F_n(C_L,K_n)[l_1,l_2,\cdots,l_d]=K[k_1,k_2,\cdots,k_c]$$ holds, and assume $$|p-1/2|$$ is sufficiently small. Let $$q^{(i)}$$ be the probability that the following equation holds for a subkey candidate $$K_n^{(i)}$$ and a random variable $$X$$: $$F_n(X,K_n)[l_1,l_2,\cdots,l_d]=F_n(X,K_n^{(i)})[l_1,l_2,\cdots,l_d]$$. Then if $$q^{(i)}$$'s are independent, the success rate of Algorithm 2 is $$\int_{x=-2\sqrt{N}|p-1/2|}^{\infty}(\prod\limits_{K_n^{(i)}\ne K_n}\int_{-x-4\sqrt{N}(p-1/2)q^{(i)}}^{x+4\sqrt{N}(p-1/2)(1-q^{(i)})}\frac{1}{\sqrt{2\pi}}e^{-y^2/2}dy)\frac{1}{\sqrt{2\pi}}e^{-x^2/2}dx$$.

I don't know why $$y$$ ranges from $$-x-4\sqrt{N}(p-1/2)q^{(i)}$$ to $$x+4\sqrt{N}(p-1/2)(1-q^{(i)})$$. I am trying to understand whether $$4\sqrt{N}(p-1/2)q^{(i)}$$ is more likely a retrodictive guess based on experimental results or based on a specific mathematical model.

Ali Aydın Selçuk wrote a comprehensive article in the Journal of Cryptology on success probability in differential and linear cryptanalysis.

The limits have to do with using the Gaussian approximation, then replacing it with a Folded normal distribution (since we tack absolute deviations not signed deviations), and then asymptotic analysis backed by experimental verification.

See the arguments culminating in Theorem 2. I believe the limits are the same, up to notational changes. If not, this is a rigorous analysis while Matsui's was somewhat handwavy, though a great advance in cryptanalysis.

The paper concludes

In this paper, we gave a formal probabilistic model of success in linear and differential cryptanalysis. We also provided efficient formulations that can be used to estimate the success probability of a given attack or to find its plaintext requirement to achieve a certain success level. Experimental results show that the formulas developed for LC are quite precise, especially when a success probability of 90% or higher is of interest

• Thank you for your suggestion. I am curious about why Matsui uses $-x-4\sqrt{N}(p-1/2)q^{(i)}$ to $x+4\sqrt{N}(p-1/2)(1-q^{(i)})$ as the range. It seems to me that the expression is not very intuitive mathematically. I am trying to understand whether $4\sqrt{N}(p-1/2)q^{(i)}$ is more likely a rough assumption or based on a specific mathematical model. Commented Jun 5 at 0:41

I want to present my proof, hoping that it is correct.

There are two assumptions which are heuristic in nature:

• [Assumption 1] $$|\frac{T_i}{N}-\frac{1}{2}|$$ of a linear expression evaluated with wrong subkey candidates has a distribution independent of the key value.
• [Assumption 2] $$|\frac{T_0}{N}-\frac{1}{2}|$$​ of a linear expression evaluated with the right subkey candidates has a distribution independent of the distribution defined in Assumption 1 and independent of the key value.

Based on the law of large numbers, we could get that the distributions of $$\frac{T_0}{N}$$ and $$\frac{T_i}{N}$$ are well approximated by a normal law. Specifically, $$X_0=\frac{T_0}{N}-\frac{1}{2}\sim\mathcal{N}(p-\frac{1}{2},\frac{1}{4N})$$ for right key candidates. Because $$q^{(i)}$$ is the probability that $$F_n(X,K_n)[l_1,l_2,\cdots,l_d]=F_n(X,K_n^{(i)})[l_1,l_2,\cdots,l_d]$$ holds, the probability that $$P[i_1,i_2,\cdots,i_a]\oplus C[j_1,j_2,\cdots,j_b]\oplus F_n(C_L,K_n^{(i)})[l_1,l_2,\cdots,l_d]=K[k_1,k_2,\cdots,k_c]$$ holds is $$pq^{(i)}+(1-p)(1-q^{(i)})$$. Then $$X_i=\frac{T_i}{N}-\frac{1}{2}\sim\mathcal{N}(pq^{(i)}+(1-p)(1-q^{(i)})-\frac{1}{2},\frac{1}{4N})$$ for wrong key candidates.

We assume for simplicity that $$p>\frac{1}{2}$$ (when $$p<\frac{1}{2}$$, it could be obtained by substituting $$-X_0$$ for $$X_0$$).

$$P_S=\int_0^{\infty}\left(\prod\limits_{K_n^{(i)}\ne K_n}\int_{-x}^xf_{(i)}(y)dy\right)f_0(x)dx\\=\int_{-2\sqrt{N}|p-1/2|}^{\infty}\left(\prod\limits_{K_n^{(i)}\ne K_n}\int_{-\frac{x}{2\sqrt{N}}-|p-\frac{1}{2}|}^{\frac{x}{2\sqrt{N}}+|p-\frac{1}{2}|}f_{(i)}(y)dy\right)\phi(x)dx\\=\int_{x=-2\sqrt{N}|p-1/2|}^{\infty}(\prod\limits_{K_n^{(i)}\ne K_n}\int_{-x-4\sqrt{N}(p-1/2)q^{(i)}}^{x+4\sqrt{N}(p-1/2)(1-q^{(i)})}\frac{1}{\sqrt{2\pi}}e^{-y^2/2}dy)\frac{1}{\sqrt{2\pi}}e^{-x^2/2}dx$$