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.


2 Answers 2


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

  • $\begingroup$ 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. $\endgroup$ 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.