Уточнённые асимптотические оценки для числа (n, m, k)- устойчивых двоичных отображений

значение PAPR, являются векторы значений бент-функций. В связи с этим возникает задача поиска кодов, состоящих из векторов значений бент-функций. Одним из способов построения таких кодов является построение линейного кода для некоторой бент-функции f, такого, что сдвиг на любую функцию из кода оставляет функцию f в классе бент-функций. Код длины 2п называется кодом постоянной амплитуды, если все элементы кода являются векторами значений бент-функций. Линейный код длины 2п называется кодом, сохраняющим свойство бент (SPB-кодом) для функции f, если сдвиг на любой элемент кода оставляет функцию f в классе бент-функций [1]. Если C — SPB-код, то его аффинный сдвиг f ф C является кодом постоянной амплитуды. Это свойство позволяет конструировать коды постоянной амплитуды из линейных кодов.

В работе исследуются свойства бент-функций, лежащих в классе Мэйорана — Мак-Фарланда [2]. Получена нижняя оценка максимальной размерности SPB-кода для произвольной бент-функции.

Теорема 1. Пусть f — бент-функция из класса Мэйорана — МакФарланда от 2n переменных. Тогда для функции f существует SPB-код размерности 2n+1 — 1.

В [3] В. В. Ященко ввёл понятие индекса линейности для произвольной булевой функции. Любую булеву функцию можно представить в виде f (x, y) = x1^1(y) + ... + + xt^t(y) + Ф(у), x E F2, y E Fn-t. Среди всех таких представлений есть представление с максимальным t, которое является аффинным инвариантом и называется индексом линейности булевой функции.

Теорема 2. Пусть f — бент-функция, индекс линейности которой равен k. Тогда для функции f существует SPB-код размерности 2fc+1 — 1.

ЛИТЕРАТУРА

1. Павлов А. В. Бент-функции и линейные коды в CDMA // Прикладная дискретная математика. Приложение. 2010. №3. С. 95-97.

2. McFarland R. L. A family of difference sets in non-cyclic groups //J. Combin. Theory. Ser. A.

1973. V. 15. No. 1. P. 1-10.

3. Ященко В. В. О критерии распространения для булевых функций и о бент-функциях //

Пробл. передачи информ. 1997. Т. 33. Вып. 1. С. 75-86.

УДК 519.212.2, 519.214 DOI 10.17223/2226308X/10/20

УТОЧНЁННЫЕ АСИМПТОТИЧЕСКИЕ ОЦЕНКИ ДЛЯ ЧИСЛА (n, m, к)-УСТОЙЧИВЫХ ДВОИЧНЫХ ОТОБРАЖЕНИЙ

К. Н. Панков

Уточнена локальная предельная теорема для распределения части вектора спектральных коэффициентов линейных комбинаций координатных функций случайного двоичного отображения. С помощью этой теоремы получена асимптотическая формула для |R (m, n, k)| — числа (n, m, к)-устойчивых двоичных отображе-

n

ний в случае n ^ œ, m E {1,2,3,4} и k ^ --- для произвольного

5 + 2 log2 n

0 <с< 1, k = 0( А) :

vln n/

^ I * (т, п,к) I - т2п - (2т - ^ + log2 £ (^ ) +

+ (2  3т-2 - 1) 1пё {т = 1} Е (пУ

«=о V 8/

Найдены верхние и нижние асимптотические оценки для |* (т,п, к)| в случае п ^ то, к (5 + 2 log2 п) + 5т ^ п (1 — е) для произвольного 0 < е < 1:

-£1 (т - 1) Е < 8=0 \ 88 /

< log2 | * (т, п, к) | - т2п + (2т - 1) (^ (к) + log2 Е О ) <

к /п\ ^ /п

<е2 (т - 2) (2т - 1) £ ) + £ ( 8=0 \ V 8=0 \ 8

для произвольных е1, е2 (0 < е1, е2 < 1).

Ключевые слова: случайное двоичное отображение, локальная предельная теорема, спектральные коэффициенты, устойчивые вектор-функции, эластичные вектор-функции.

Как известно, многие свойства двоичных отображений и определяемые ими классы вектор-функций исторически выделялись под влиянием задач разработки и анализа криптографических систем. К таким классам относятся и широко известные в математике и её приложениях (п, т, к)-устойчивые или, как их можно назвать в соответствии с [1], к-эластичные отображения. Такие вектор-функции используются, например, в поточных шифрсистемах в качестве комбинирующих функций, обладающих способностью противостоять корреляционному методу криптоанализа, так как их выход статистически не зависит от некоторых комбинаций входов.

Обозначим через Уп множество двоичных векторов размерности п. В [2] доказано, что многие важные свойства двоичного отображения / (а) = (/1 (а) , /2 (а) ,...,/т (а)) : Уп ^ Ут, к которым относится и (п, т, к)-устойчивость, сводятся к обладанию этими свойствами всеми ненулевыми линейными комбинациями координатных функций / (а), называемыми в [3] компонентными функциями или компонентами. Свойства компонент могут быть, в частности, выражены в терминах их спектральных коэффициентов Фурье — Уолша — Адамара [4], или, иначе говоря, коэффициентов статистической структуры в соответствии с [5, с. 71]:

Р/ (/) = А/ (/) = 2 Е (-1)(^(/),/)(х)ф(^(/= 2п-1 - ||(фт (3), /) (х) 0 (фп (I) ,х)||,

2 жеУп

где / = (/1,...,/т); |/1| —вес булевой функции /1; 3 = |} С {1,...,т};

фт (3) —двоичный вектор длины т, у которого на ... , 1 координатах стоят единицы, а на остальных нули. В терминологии [6] фт (3) называется индикаторным вектором множества 3.

Определение 1. Отображение / из множества Вт всех т-мерных двоичных функций от п переменных называется (п, т, к)-устойчивым, если для любых 1,3, 0 = 3 С {1,... , т}, I С {1,... , п}, |11 ^ к, выполняется А/ (/) = 0.

Пусть функция f выбирается случайно и равновероятно из множества В^7". Рассмотрим для этой функции вектор коэффициентов статистической структуры

Д к а) =

к

длины N = N (п, т, к) = (2т — 1) Е ( ). Для упрощения записи введём обозначения

з=0 \ V

ехр2 х = 2х,

Т = Т (п, т, к) = ^ (£) (2т — 1) + N (п, т, к) log^ .

Теорема 1. Пусть при всех достаточно больших п для произвольного 0 < е < 1 выполняется к

¿С/

для любых 0 = 3 € {1,... , т} и / € {1,... , п} справедливо:

Р (Дк = а) =05 (а) ехр (—2—5) + + ехр2 (—Т (п,т,к))(ехр(—21-п Е Е (а/)^ х

V V 0=/е{1,...,т} /С{1,...,п},|//

х (1 + 01 (а) 2(1о& 3-9)т-п/2 + 02 (а) 2-8т-п + 03 (а) 2(1о& 3-17)т-3п/2) + +04 (а) пк22т+к-га/2 ехр (—2п-2т-2к-3п-2к^ х

""\ 0=/С{1,...,т} /С{1,...,п},|/¿С/

где

К** (т, N) ={ 1 = (г/, 0 = 3 С {1,... , т}, / С {1,...,п}, |/1 ^ к) € ^2™-1 )М : V/ Ув €{1,...,т}У5 € Е (—1)(й'^т (/)) г/ =

«е/

|01 (а)| ^ 32; |02 (а)| ^ 8; |03 (а)| ^ 267; |04 (а)| ^ 3,2; |05 (а)| ^ 1; Z2m-l - кольцо вычетов по модулю 2т-1.

Пусть Я(т, п, к) —множество всех (п, т, к)-устойчивых двоичных отображений. Следствие 1. В условиях теоремы 1 при п 1 то

|Д (т,п,к)| - |К** (т, N)|  ехр2 (т2га — Т (п,т,к)).

Следствие 2. Пусть при всех достаточно больших п для произвольного 0 < е < 1

п (1 — е) / п \

выполняется к ^ ---, к = О ( --) и т € {1, 2, 3,4}. Тогда при п 1 то

5 + 2log2 п Мпп/

|Я (т,п,к)| - ехр2 (т2га — Т (п,т,к) + N (п, 1,к) (2  3т-2 — 1) 1пё {т = 1}) ,

где 1пё {А} —индикатор события А.

Следствие 3. В условиях теоремы 1 существует n0, такое, что для любых £i, £2 > 0, n > n0 верны неравенства

(1 - £1) exp2 (m2n - T (n,m,k) + (m - 1) N (n, 1,k)) < |R (m,n,k)| <

< (1 + £2) exp2 (m2n - T (n, m, k) + (m - 2) N (n, m, k) + N (n, 1, k)).

Данные оценки уточняют или улучшают результаты работ [1, 4] в связи с [8].

ЛИТЕРАТУРА

1. Панков К. Н. Асимптотические оценки для чисел двоичных отображений с заданными криптографическими свойствами // Математические вопросы криптографии. 2014. №4. С. 73-97.

2. Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012.

3. Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Encyclopedia of Mathematics and its Applications. V. 134. N.Y.: Cambridge University Press, 2010. P. 398-472.

4. Денисов О. В. Локальная предельная теорема для распределения части спектра случайной двоичной функции // Дискретная математика. 2000. №1. С. 82-95.

5. Словарь криптографических терминов. М.: МЦНМО, 2006.

6. Сачков В. Н. Курс комбинаторного анализа. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2013.

7. Панков К. Н. Оценки скорости сходимости в предельных теоремах для совместных распределений части характеристик случайных двоичных отображений // Прикладная дискретная математика. 2012. №4. С. 14-30.

8. Canfield E. R., Gao Z., Greenhill C., et al. Asymptotic enumeration of correlation-immune Boolean functions // Cryptography and Communications. 2010. No. 1. P. 111-126.

УДК 519.7 DOI 10.17223/2226308X/10/21

КОМПОНЕНТНАЯ АЛГЕБРАИЧЕСКАЯ ИММУННОСТЬ S-БЛОКОВ, ИСПОЛЬЗУЮЩИХСЯ В НЕКОТОРЫХ БЛОЧНЫХ ШИФРАХ

Д. П. Покрасенко

Установлено точное значение компонентной алгебраической иммунности S-бло-ков, которые используются в работе известных блочных шифров. Получено, что такие шифры, как DES, CAST-256, KASAMI, PRESENT не обладают максимальной иммунностью и потенциально являются менее стойкими к алгебраическому криптоанализу.

Ключевые слова: векторная булева функция, компонентная алгебраическая иммунность, S-блоки, DES, AES, PRESENT, KUZNYECHIK.

Известно, что любой шифр можно представить в виде системы булевых уравнений, которые описывают его работу. Данная система строится на основе известного алгоритма шифрования и позволяет связать между собой биты открытого текста, ключа и шифротекста. Решение систем булевых уравнений в общем случае является NP-трудной задачей. Существуют различные алгоритмы решения таких систем, но большинство из них решают только линейные системы либо нелинейные при достаточно низком значении степени уравнений, трудоёмкость нахождения решения в таком случае слишком велика. Подробнее с методами решения систем булевых уравнений можно ознакомиться в [1].