On additive differential probabilities of a composition of bitwise XORs | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/5

Исследуются разностные характеристики adp⊗k по модулю 2n композиции k - 1 побитовых XOR. Для векторов α1,...,αk+1 ℤ2n они определяются как вероятность преобразования функцией x1 ⊗ ... ⊗ xk входных разностей α1,... ,αk в выходную разность αk+1, где x1,...,xk ℤ2n и k ≥ 2. Данные характеристики используются при разностном криптоанализе симметричных алгоритмов, в том числе ARX-конструкций, использующих только три операции: сложение по модулю 2n, побитовый XOR и циклический сдвиг битов. Показано, что многие свойства, известные для adp⊗2 , обобщаются на adp⊗k . Доказаны симметрии аргументов adp⊗k . Получены рекуррентные формулы, позволяющие уменьшить на 1 размерность аргументов n. Найдены все несовместные разности и все разности, при которых adp⊗k равна 1. Для чётного k доказано, что max adp⊗k (α1,..., αk → αk+1) = adp⊗k (0,..., 0, αk+1 → αk+1). Построены матрицы, которые можно использовать для вычисления adp⊗k за линейное по n время. Показано, что случаи чётного и нечётного к существенно различаются.