On the guaranteed number of activations in $\mathsf{XS}$-circuits

$\mathsf{XS}$-схемы описывают блочные шифры, построенные с помощью двух операций над двоичными словами фиксированной длины: поразрядное по модулю $2$ сложение ($\mathsf{X}$) и подстановка ($\mathsf{S}$). Двоичные слова интерпретируются как элементы поля характеристики $2$. В работе рассматриваются $\mathsf{XS}$-схемы, составленные из нескольких экземпляров простых тактовых (цикловых) схем, каждая из которых содержит только одну операцию $\mathsf{S}$. Составная схема называется каскадом. $\mathsf{S}$-операции каскада интерпретируются как независимые тактовые оракулы. При обработке каскадом двух различных входов некоторые тактовые оракулы получат разные запросы, эти оракулы будут считаться активированными. Чем больше активаций, тем большие гарантии защиты относительно разностного криптоанализа обеспечивает каскад. Вводится в рассмотрение гарантированное число активаций — их минимум по всем вариантам выбора базового поля, тактовых оракулов и входов каскада. Показано, что гарантированное число активаций связано с минимальным расстоянием линейного кода, ассоциированного с каскадом. Это число также связано с минимальным количеством единиц на отрезках двоичной линейной рекуррентной последовательности, характеристический многочлен которой определяется тактовой схемой. Предложен алгоритм вычисления гарантированного числа активаций и показано, как использовать алгоритм для работы с линейными активациями, возникающими в линейном криптоанализе.