Lema de acumulación

En criptoanálisis , el lema de apilamiento es un principio utilizado en criptoanálisis lineal para construir aproximaciones lineales a la acción de los cifrados de bloque . Fue introducido por Mitsuru Matsui (1993) como una herramienta analítica para el criptoanálisis lineal. ^[1] El lema establece que el sesgo (desviación del valor esperado de 1/2) de una función booleana lineal (cláusula XOR) de variables aleatorias binarias independientes está relacionado con el producto de los sesgos de entrada: ^[2]

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

o

${\displaystyle I(X_{1}\omás X_{2}\omás \cdots \omás X_{n})=\prod _{i=1}^{n}I(X_{i})}$

¿Dónde está el sesgo (hacia cero ^[3] ) y el desequilibrio : ^{[4] [5]}${\displaystyle \epsilon \in [-{\tfrac {1}{2}},{\tfrac {1}{2}}]}$${\displaystyle I\in [-1,1]}$

${\displaystyle \epsilon(X)=P(X=0)-{\frac {1}{2}}}$

${\displaystyle I(X)=P(X=0)-P(X=1)=2\epsilon (X)}$.

Por el contrario, si el lema no se cumple, entonces las variables de entrada no son independientes. ^[6]

El lema implica que la operación XOR de variables binarias independientes siempre reduce el sesgo (o al menos no lo aumenta); además, la salida es imparcial si y solo si hay al menos una variable de entrada imparcial.

Nótese que para dos variables la cantidad es una medida de correlación de y , igual a ; puede interpretarse como la correlación de con . ${\displaystyle I(X\omás Y)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle P(X=Y)-P(X\neq Y)}$${\displaystyle I(X)}$${\displaystyle X}$${\displaystyle 0}$

El lema de apilamiento se puede expresar de forma más natural cuando las variables aleatorias toman valores en . Si introducimos variables (asignando 0 a 1 y 1 a -1), entonces, por inspección, la operación XOR se transforma en un producto: ${\displaystyle \{-1,1\}}$${\displaystyle \chi _{i}=1-2X_{i}=(-1)^{X_{i}}}$

${\displaystyle \chi _{1}\chi _{2}\cdots \chi _{n}=1-2(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=(-1)^{X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}}}$

y como los valores esperados son los desequilibrios, , el lema ahora establece: ${\displaystyle E(\chi _{i})=I(X_{i})}$

${\displaystyle E\left(\prod _{i=1}^{n}\chi _{i}\right)=\prod _{i=1}^{n}E(\chi _{i})}$

que es una propiedad conocida del valor esperado de las variables independientes .

Para las variables dependientes, la formulación anterior obtiene un término de covarianza (positiva o negativa) , por lo que el lema no se cumple. De hecho, dado que dos variables de Bernoulli son independientes si y solo si no están correlacionadas (es decir, tienen covarianza cero; ver falta de correlación ), tenemos el recíproco del lema de acumulación: si no se cumple, las variables no son independientes (no están correlacionadas).

El lema de acumulación permite al criptoanalista determinar la probabilidad de que la igualdad:

${\displaystyle X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0}$

se cumple, donde las X son variables binarias ( es decir, bits: 0 o 1).

Sea P (A) "la probabilidad de que A sea verdadera". Si es igual a uno , A es seguro que ocurrirá, y si es igual a cero, A no puede ocurrir. En primer lugar, consideramos el lema de apilamiento para dos variables binarias, donde y . ${\displaystyle P(X_{1}=0)=p_{1}}$${\displaystyle P(X_{2}=0)=p_{2}}$

Ahora, consideremos:

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

Debido a las propiedades de la operación xor , esto es equivalente a

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

X ₁ = X ₂ = 0 y X ₁ = X ₂ = 1 son eventos mutuamente excluyentes , por lo que podemos decir

${\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)}$

Ahora, debemos hacer la suposición central del lema de la acumulación: las variables binarias con las que estamos tratando son independientes ; es decir, el estado de una no tiene efecto sobre el estado de ninguna de las otras. Por lo tanto, podemos desarrollar la función de probabilidad de la siguiente manera:

Ahora expresamos las probabilidades p ₁ y p ₂ como ⁠1/2⁠ + ε ₁ y ⁠1/2⁠ + ε ₂ , donde los ε son los sesgos de probabilidad: la cantidad en la que la probabilidad se desvía de ⁠1/2⁠ .

Por lo tanto, el sesgo de probabilidad ε _1,2 para la suma XOR anterior es 2ε ₁ ε ₂ .

Esta fórmula se puede extender a más X de la siguiente manera:

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

Tenga en cuenta que si alguno de los ε es cero, es decir, una de las variables binarias es imparcial, toda la función de probabilidad será imparcial, igual a ⁠1/2⁠ .

Una definición ligeramente diferente del sesgo es, de hecho, menos dos veces el valor anterior. La ventaja es que ahora con ${\displaystyle \epsilon _{i}=P(X_{i}=1)-P(X_{i}=0),}$

${\displaystyle \varepsilon _{total}=P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=1)-P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)}$

tenemos

${\displaystyle \varepsilon _{total}=(-1)^{n+1}\prod _{i=1}^{n}\varepsilon _{i},}$

Añadir variables aleatorias equivale a multiplicar sus sesgos (segunda definición).

En la práctica, las X son aproximaciones a las cajas S (componentes de sustitución) de los cifrados de bloque. Normalmente, los valores X son entradas a la caja S y los valores Y son las salidas correspondientes. Con solo mirar las cajas S, el criptoanalista puede determinar cuáles son los sesgos de probabilidad. El truco consiste en encontrar combinaciones de valores de entrada y salida que tengan probabilidades de cero o uno. Cuanto más cercana sea la aproximación a cero o uno, más útil será la aproximación en el criptoanálisis lineal.

Sin embargo, en la práctica, las variables binarias no son independientes, como se supone en la derivación del lema de apilamiento. Esta consideración debe tenerse en cuenta al aplicar el lema; no se trata de una fórmula automática de criptoanálisis.

• Varianza de una suma de variables reales independientes