Лемма о нагромождении

В криптоанализе лемма о нагромождении — это принцип, используемый в линейном криптоанализе для построения линейных приближений к действию блочных шифров . Он был представлен Мицуру Мацуи (1993) как аналитический инструмент для линейного криптоанализа. Лемма утверждает, что смещение (отклонение ожидаемого значения от 1/2) линейной булевой функции (предложение XOR) независимых двоичных случайных величин связано с произведением входных смещений:

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

или

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

где $\epsilon \in [-{\tfrac {1}{2}},{\tfrac {1}{2}}]$ - смещение (к нулю ) и $I\in [-1,1]$ дисбаланс ​ :

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

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

Обратно, если лемма не выполняется, то входные переменные не являются независимыми.

Интерпретация

Лемма подразумевает, что операция XOR независимых двоичных переменных всегда уменьшает смещение (или, по крайней мере, не увеличивает его); более того, выходной сигнал является несмещенным тогда и только тогда, когда существует хотя бы одна несмещенная входная переменная.

Заметим, что для двух переменных величина $I(X\oplus Y)$ является корреляционной мерой $X$ и $Y$, равно $P(X=Y)-P(X\neq Y)$; $I(X)$ можно интерпретировать как соотношение $X$ с $0$.

ожидаемой

Лемму о нагромождении можно выразить более естественно, если случайные величины принимают значения в $\{-1,1\}$. Если мы введем переменные $\chi _{i}=1-2X_{i}=(-1)^{X_{i}}$ (сопоставление 0 с 1 и 1 с -1), затем при проверке операция XOR преобразуется в произведение:

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

и поскольку ожидаемые значения представляют собой дисбалансы, $E(\chi _{i})=I(X_{i})$, лемма теперь гласит:

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

что является известным свойством ожидаемого значения независимых переменных .

Для зависимых переменных в приведенной выше формулировке появляется (положительный или отрицательный) ковариационный член, поэтому лемма не выполняется. Фактически, поскольку две переменные Бернулли независимы тогда и только тогда, когда они некоррелированы (т. е. имеют нулевую ковариацию; см. некоррелированность ), мы имеем обратную лемму о нагромождении: если она не выполняется, переменные не являются независимыми (некоррелированными). .

Булев вывод

Лемма о нагромождении позволяет криптоаналитику определить вероятность того, что равенство:

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

выполняется, где X — . двоичные переменные (то есть биты: либо 0, либо 1)

Пусть P (A) обозначает «вероятность того, что A истинно». Если оно равно единице , то А обязательно произойдет, а если оно равно нулю, то А не может произойти. Прежде всего, рассмотрим лемму о нагромождении для двух бинарных переменных, где $P(X_{1}=0)=p_{1}$ и $P(X_{2}=0)=p_{2}$.

Теперь мы считаем:

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

Благодаря свойствам операции xor это эквивалентно

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

X ₁ = X ₂ = 0 и X ₁ = X ₂ = 1 являются взаимоисключающими событиями , поэтому мы можем сказать

$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)$

Теперь мы должны сделать главное предположение леммы о нагромождении: двоичные переменные, с которыми мы имеем дело, независимы ; то есть состояние одного не влияет на состояние любого другого. Таким образом, мы можем расширить функцию вероятности следующим образом:

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

Теперь выразим вероятности p ₁ и p ₂ как 1/2 ​ + ε ₁ и 1/2 ε + , ₂ где ε — это вероятность отклонения — величина отклонения вероятности от 1 / 2 .

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

Таким образом, вероятностное смещение ε _1,2 для суммы XOR выше равно 2ε ₁ ε ₂ .

Эту формулу можно распространить на большее количество следующим X образом:

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

Обратите внимание: если какое-либо из ε равно нулю; то есть одна из бинарных переменных несмещена, вся функция вероятности будет несмещенной — равной 1 / 2 .

Связанное с этим несколько иное определение предвзятости: $\epsilon _{i}=P(X_{i}=1)-P(X_{i}=0),$фактически минус в два раза больше предыдущего значения. Преимущество в том, что теперь с

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

у нас есть

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

добавление случайных величин равносильно умножению их смещений (второе определение).

Практика

На практике X являются приближениями к S-блокам (компонентам замены) блочных шифров. Обычно значения X являются входными данными для S-блока, а значения Y — соответствующими выходными данными. Просто взглянув на S-блоки, криптоаналитик может определить, каковы вероятностные отклонения. Хитрость заключается в том, чтобы найти комбинации входных и выходных значений, вероятность которых равна нулю или единице. Чем ближе аппроксимация к нулю или единице, тем полезнее аппроксимация в линейном криптоанализе.

Однако на практике бинарные переменные не являются независимыми, как предполагается при выводе леммы о нагромождении. Это соображение следует иметь в виду при применении леммы; это не формула автоматического криптоанализа.

См. также

• Дисперсия суммы независимых действительных переменных