Lemme d'empilement

Une équation linéaire dans le cadre de la cryptanalyse linéaire se présente sous la forme d'un ou-exclusif de variables binaires :

${\displaystyle X_{1}\oplus X_{2}\oplus ...\oplus X_{N}=0}$

Soit ${\displaystyle N~}$ variables aléatoires, indépendantes et binaires (le résultat de l'événement est soit 0, soit 1), ${\displaystyle X_{1},X_{2},...,X_{N}~}$, la probabilité que cette équation soit correcte est :

${\displaystyle P(X_{1}\oplus X_{2}\oplus ...\oplus X_{N}=0)=1/2+2^{N-1}\prod _{i=1}^{N}\epsilon _{i}}$

avec ${\displaystyle \epsilon _{i}~}$, le biais linéaire de la variable aléatoire ${\displaystyle X_{i}~}$. Ce biais peut être positif ou négatif et quantifie l'écart par rapport à une distribution uniforme où l'espérance d'une variable aléatoire binaire est 1/2. Plus le biais est important, plus un algorithme de chiffrement est susceptible d'être attaqué via la cryptanalyse linéaire.

Soit ${\displaystyle P(A)~}$, la probabilité que l'événement A arrive. Avec une probabilité de 1, l'événement se produira. Inversement, une probabilité de 0 indique l'impossibilité de cet événement. Dans le cadre du lemme d'empilement, nous avons donc affaire à des variables aléatoires, binaires et considérées comme indépendantes.

Considérons d'abord le lemme pour deux variables aléatoires :

${\displaystyle P(X_{1}=i)=\left\lbrace {\begin{matrix}p_{1}&{\hbox{pour }}i=0\\1-p_{1}&{\hbox{pour }}i=1\end{matrix}}\right.}$

${\displaystyle P(X_{2}=j)=\left\lbrace {\begin{matrix}p_{2}&{\hbox{pour }}j=0\\1-p_{2}&{\hbox{pour }}j=1\end{matrix}}\right.}$

Considérons maintenant la probabilité d'une équation linéaire avec ces deux variables :

${\displaystyle P(X_{1}\oplus X_{2}=0)}$

Grâce aux propriétés de XOR, ceci est équivalent à :

${\displaystyle P(X_{1}=X_{2})~}$

X₁ = X₂ = 0 et X₁ = X₂ = 1 sont des événements mutuellement exclus et de ce fait :

${\displaystyle P(X_{1}=X_{2})=P(X_{1}=X_{2}=0)+P(X_{1}=X_{2}=1)=P(X_{1}=0,X_{2}=0)+P(X_{1}=1,X_{2}=1)~}$

Nous partons dès lors du principe que les variables sont indépendantes. C’est-à-dire que l'état d'une variable ne va pas influencer l'état d'une autre. On peut ainsi étendre la probabilité au résultat suivant :

${\displaystyle P(X_{1}\oplus X_{2}=0)}$	${\displaystyle =P(X_{1}=0)P(X_{2}=0)+P(X_{1}=1)P(X_{2}=1)\ }$
	${\displaystyle =p_{1}p_{2}+(1-p_{1})(1-p_{2})\ }$
	${\displaystyle =p_{1}p_{2}+(1-p_{1}-p_{2}+p_{1}p_{2})\ }$
	${\displaystyle =2p_{1}p_{2}-p_{1}-p_{2}+1\ }$

Nous exprimons maintenant les probabilités p₁ et p₂ comme ½ + ε₁ et ½ + ε₂, où les ε sont des biais de probabilités — la quantité de déviation de la probabilité par rapport à ½.

${\displaystyle P(X_{1}\oplus X_{2}=0)}$	${\displaystyle =2(1/2+\epsilon _{1})(1/2+\epsilon _{2})-(1/2+\epsilon _{1})-(1/2+\epsilon _{2})+1\ }$
	${\displaystyle =1/2+\epsilon _{1}+\epsilon _{2}+2\epsilon _{1}\epsilon _{2}-1/2-\epsilon _{1}-1/2-\epsilon _{2}+1\ }$
	${\displaystyle =1/2+2\epsilon _{1}\epsilon _{2}\ }$

Ainsi, le biais ε_1,2 pour la somme de XOR ci-dessus est de 2ε₁ε₂.

Cette formule peut s'étendre pour un nombre infini de variables comme suit :

${\displaystyle P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)=1/2+2^{n-1}\prod _{i=1}^{n}\epsilon _{i}}$

Si un ε est à zéro, c’est-à-dire qu'une des variables est non-biaisée, alors l'ensemble de la fonction ne sera pas biaisée et égale à ½.