Дифференциальные уравнения сложения

В криптографии дифференциальные уравнения сложения (DEA) являются одними из самых основных уравнений, связанных с дифференциальным криптоанализом , которые смешивают сложения по двум различным группам (например, сложение по модулю 2 32 ^и сложение по GF(2)), и где входные и выходные разности выражаются как XOR.

Дифференциальные уравнения сложения (ДУС) имеют следующий вид:

${\displaystyle (x+y)\oplus ((x\oplus a)+(y\oplus b))=c}$

где и - неизвестные переменные разряда , а и - известные переменные . Символы и обозначают сложение по модулю и побитовое исключающее ИЛИ соответственно. Уравнение выше обозначается как .${\displaystyle x}$${\displaystyle у}$${\displaystyle n}$${\displaystyle а}$${\displaystyle б}$${\displaystyle с}$${\displaystyle +}$${\displaystyle \oplus}$ ${\displaystyle 2^{n}}$${\displaystyle (а,б,в)}$

Пусть набор

${\displaystyle S=\{(a_{i},b_{i},c_{i})|i<k\}}$

для целого числа обозначим систему DEA , где — многочлен от . Доказано, что выполнимость произвольного набора DEA находится в классе сложности P , когда поиск методом грубой силы требует экспоненциального времени . ${\displaystyle я}$${\displaystyle к(н)}$ ${\displaystyle к(н)}$${\displaystyle n}$

В 2013 году некоторые свойства особой формы DEA были сообщены Чэнцином Ли и др., где и предполагается известным. По сути, особый DEA можно представить как . На основе найденных свойств был предложен и проанализирован алгоритм вывода . ^[1]${\displaystyle а=0}$${\displaystyle у}$${\displaystyle (x\dotplus \alpha )\oplus (x\dotplus \beta )=c}$${\displaystyle x}$

Решение для произвольного набора DEA (либо в пакетной, либо в адаптивной модели запроса) было получено от Souradyuti Paul и Bart Preneel . Методы решения были использованы для атаки на потоковый шифр Helix .

• Сорадьюти Пол и Барт Пренел , Решение систем дифференциальных уравнений сложения, ACISP 2005. Полная версия ( PDF )
• Сорадьюти Пол и Барт Пренил , Почти оптимальные алгоритмы решения дифференциальных уравнений сложения с помощью пакетных запросов, Indocrypt 2005. Полная версия ( PDF )
• Хельгер Липмаа, Йохан Валлен, Филипп Дюма: Об аддитивной дифференциальной вероятности исключающего ИЛИ. FSE 2004: 317-331.