En el criptoanálisis , el lema de acumulación es un principio utilizado en el criptoanálisis lineal para construir aproximaciones lineales a la acción de los cifrados en 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á relacionada con el producto de los sesgos de entrada: [2]
o
dónde es el sesgo (hacia cero [3] ) yel desequilibrio : [4] [5]
- .
Por el contrario, si el lema no se cumple, las variables de entrada no son independientes. [6]
Interpretación
El lema implica que XOR-ing variables binarias independientes siempre reduce el sesgo (o al menos no lo aumenta); además, la salida es insesgada si y solo si hay al menos una variable de entrada insesgada.
Tenga en cuenta que para dos variables la cantidad es una medida de correlación de y , igual a ; puede interpretarse como la correlación de con .
Formulación de valor esperado
El lema de acumulación se puede expresar de forma más natural cuando las variables aleatorias toman valores en . Si introducimos variables (mapeo de 0 a 1 y de 1 a -1) luego, mediante inspección, la operación XOR se transforma en un producto:
y dado que los valores esperados son los desequilibrios,, el lema ahora dice:
que es una propiedad conocida del valor esperado para variables independientes .
Para las variables dependientes, la formulación anterior obtiene un término de covarianza (positivo o negativo) , 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 lo contrario del lema de acumulación: si no se cumple, las variables no son independientes (no correlacionadas) .
Derivación booleana
El lema de acumulación permite al criptoanalista determinar la probabilidad de que la igualdad:
se mantiene, 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 , es seguro que A sucederá, y si es igual a cero, A no puede suceder. En primer lugar, consideramos el lema de acumulación para dos variables binarias, donde y .
Ahora, consideramos:
Debido a las propiedades de la operación xor , esto es equivalente a
X 1 = X 2 = 0 y X 1 = X 2 = 1 son eventos mutuamente excluyentes , por lo que podemos decir
Ahora, debemos hacer el supuesto central del lema de acumulación: las variables binarias con las que estamos tratando son independientes ; es decir, el estado de uno no tiene ningún efecto sobre el estado de los demás. Por lo tanto, podemos expandir la función de probabilidad de la siguiente manera:
Ahora expresamos las probabilidades p 1 y p 2 como ½ + ε 1 y ½ + ε 2 , donde las ε son los sesgos de probabilidad, la cantidad en que la probabilidad se desvía de ½.
Por lo tanto, el sesgo de probabilidad ε 1,2 para la suma XOR anterior es 2ε 1 ε 2 .
Esta fórmula se puede extender a más X de la siguiente manera:
Tenga en cuenta que si alguno de los ε es cero; es decir, una de las variables binarias es insesgada, toda la función de probabilidad será insesgada, igual a ½.
Una definición relacionada ligeramente diferente del sesgo es de hecho menos dos veces el valor anterior. La ventaja es que ahora con
tenemos
agregar variables aleatorias equivale a multiplicar sus sesgos (segunda definición).
Práctica
En la práctica, las X son aproximaciones a las cajas S (componentes de sustitución) de los cifrados en bloque. Normalmente, los valores de X son entradas a la caja S y los valores de Y son las salidas correspondientes. Con solo mirar las cajas S, el criptoanalista puede saber 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 acumulación. Esta consideración debe tenerse en cuenta al aplicar el lema; no es una fórmula de criptoanálisis automático.
Ver también
- Varianza de una suma de variables reales independientes
Referencias
- ^ Matsui, Mitsuru (1994). Helleseth, Tor (ed.). "Método de criptoanálisis lineal para cifrado DES" . Avances en Criptología - EUROCRYPT '93 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 765 : 386–397. doi : 10.1007 / 3-540-48285-7_33 . ISBN 978-3-540-48285-7.
- ^ Li, Q .; Boztas, S. (2012). "Criptoanálisis lineal extendido y Lema de acumulación extendido" . www.semanticscholar.org . S2CID 5508314 . Consultado el 29 de abril de 2021 .
- ^ El sesgo (y el desequilibrio) también se puede tomar como un valor absoluto; si se usa el sesgo con signo invertido (sesgo hacia uno), el lema necesita un factor de signo adicional (-1) ^ (n + 1) en el lado derecho.
- ^ Harpes, Carlo; Kramer, Gerhard G .; Massey, James L. (1995). Guillou, Louis C .; Quisquater, Jean-Jacques (eds.). "Una generalización del criptoanálisis lineal y la aplicabilidad del lema de acumulación de Matsui" . Avances en Criptología - EUROCRYPT '95 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 921 : 24–38. doi : 10.1007 / 3-540-49264-X_3 . ISBN 978-3-540-49264-1.
- ^ Kukorelly, Zsolt (1999). Walker, Michael (ed.). "El lema de acumulación y variables aleatorias dependientes" . Criptografía y codificación . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 1746 : 186-190. doi : 10.1007 / 3-540-46665-7_22 . ISBN 978-3-540-46665-9.
- ^ Nyberg, Kaisa (26 de febrero de 2008). "Criptoanálisis lineal (Conferencia de Criptología)" (PDF) . Universidad Tecnológica de Helsinki, Laboratorio de Informática Teórica .