Лемма о нагромождении
-
Лемма о накоплении в криптоанализе
- Используется для построения линейных приближений к блочным шифрам.
- Предложена Мицуру Мацуи в 1993 году.
- Утверждает связь между смещением линейной булевой функции и произведением входных смещений.
- Если лемма не выполняется, переменные не являются независимыми.
-
Интерпретация и формулировка
- Исключение независимых переменных уменьшает смещение.
- Несмещенные выходные данные возможны при наличии хотя бы одной несмещенной входной переменной.
- Я(X⊕Y) является корреляционной мерой X и Y.
- Я(X) интерпретируется как соотношение X с 0.
-
Формулировка для двоичных переменных
- Вводит переменные χi = 1 — 2Xi для упрощения операции XOR.
- Ожидаемые значения равны дисбалансам, то есть Я(Xi).
- Для зависимых переменных появляется ковариационный член.
-
Логический вывод и практическое применение
- Лемма позволяет определить вероятность равенства для бинарных переменных.
- На практике Xs являются приближениями к S-блокам блочных шифров.
- Чем ближе приближение к 0 или 1, тем оно полезнее в линейном криптоанализе.
- На практике бинарные переменные не всегда независимы, что следует учитывать при применении леммы.