О новых оценках размерности подкодов кодов Рида - Маллера, квадрат Адамара которых максимален | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/28

О новых оценках размерности подкодов кодов Рида - Маллера, квадрат Адамара которых максимален

Наличие в коде некоторой структуры может привести к снижению стойкости всей системы, построенной на нем. Для «маскировки» кода под код «общего вида» часто используются подкоды. Однако стойкость подкодов, квадрат Адамара которых равен квадрату полного кода, сводится к стойкости этого кода. Таким образом, данное свойство необходимо учитывать как при синтезе схем на кодах, так и при их криптоанализе. В работе анализируется минимальное количество мономов степени r, которые при добавлении к коду RM(r - 1 ,m) образуют подкод, квадрат Адамара которого максимален, т.е. совпадает с кодом RM(2r,m). Это число снизу оценивается аналитически, а для получения верхней оценки предлагается жадный алгоритм построения такого набора мономов.

New estimates for dimension of Reed - Muller subcodes with maximum Hadamard square.pdf В последнее время большую популярность получили кодовые криптосистемы. Этот интерес прослеживается в работах, поданных на конкурс на перспективный постквантовый алгоритм, объявленный NIST [1] в 2016 г. для дальнейшей стандартизации. Кроме того, ТК 26 выбрал схемы на кодах как одно из направлений разработки будущего российского стандарта постквантовых алгоритмов. При синтезе новых кодовых схем одним из самых важных вопросов является выбор базового кода, от которого будут зависеть все характеристики. В целях создания асимметрии в возможностях легального пользователя и противника требуется скрывать структуру кода. Это можно сделать, например, используя подкоды. Однако в работе И. В. Чижова и М. А. Бородина [2] стойкость криптосистемы Мак-Элиса [3] на подкодах коразмерности 1 сведена к стойкости оригинальной криптосистемы. Сведение работает для подкодов, квадрат Адамара которых совпадает с квадратом базового кода. Такое свойство подкодов без наложения ограничений на коразмерность исследовано в работе [4]. Определение 1. Кодом Рида - Маллера RM(r, m) называется множество булевых функций f от m переменных, таких, что deg(f) ^ r. Определение 2. Произведением Адамара двух векторов называется вектор, полученный в результате покомпонентного произведения координат этих векторов: (a1,..., a„) о (&1,...,6га) = (a1&1,..., a„b„), а произведение Адамара двух кодов A и B есть линейная оболочка всех попарных произведений вида a о b, где a е A, b е B. Отметим, что квадрат Адамара кода Рида - Маллера имеет смысл только при m ^ 2r. Будем рассматривать подкоды вида (RM(r - 1, m) U {/1,..., /w(m,r)})2 = RM(2r,m), (1) где /1,... , /w(m,r) - мономы степени r, а под возведением в квадрат понимается квадрат Адамара. Задача состоит в минимизации значения w(m, r). Перейдём к графовой интерпретации задачи. Сопоставим подкод A С RM(r, m) с гиперграфом G с m вершинами, помеченными как x1,...,xm. Ребро {ж^, ...,xir} проведено тогда и только тогда, когда моном ... xir G A. В [4] показано, что для обеспечения условия (1) достаточно, чтобы гиперграф был стабильным. Определение 3. Гиперграф называется стабильным, если каждое множество, состоящее из 2r вершин, покрыто двумя непересекающимися r-рёбрами. Очевидно, что задача поиска стабильного гиперграфа с минимальным количеством r-рёбер эквивалентна поиску минимального числа w(m, r). В работе [4] это число для r ^ 2 и h < r/3 оценено как cm/cm-r ^ w(m, r) ^ cm - T(r, m, h) ^ - 2), (2) где T(r, m, h) = max {t : 3S1,... , St (Sj С {1,... , m} & & |Si| = 2r & (i = j ^ |Si П Sj| ^ h), i,j G {1,..., t})}. Эти оценки могут быть улучшены. Теорема 1. w(m,r) ^ \\Jy + 2Cm + VY, где y = Е СГ. i=max{ 1, 3r-m} Для получения верхней оценки предложен алгоритм, который по параметрам кода строит соответствующий стабильный гиперграф. Его реализацию, написанную на Python, можно посмотреть в https://github.com/VysotskayaVictory/ StableGraphGreedy/. На каждом шаге алгоритма происходит попытка добавить новое r-ребро. В случае успеха значение w(m, r) увеличивается на 1, а также формируется список r-рёбер, которые пересекаются с данным. Они добавляются в список inter. Вместе с этим поддерживается счетчик repeated повторно покрытых множеств. Алгоритм останавливается, когда все С^Т множеств размера 2r покрыты парами непересекающихся r-рёбер. Условием останова является выполнение равенства CW(m,r) - linterl - repeated = cm. Сравнение полученных оценок с оценками из (2) представлено на рис. 1. Его анализ позволяет говорить о том, что оценки существенно улучшены. Количество переменных m

Ключевые слова

постквантовая криптография, кодовая криптография, коды Рида-Маллера, подкоды Рида-Маллера, произведение Адамара, криптосистема Мак-Элиса, post-quantum cryptography, code-based cryptography, Reed-Muller subcodes, Reed-Muller codes, Hadamard product, McEliece cryptosystem

Авторы

ФИООрганизацияДополнительноE-mail
Высоцкая Виктория ВладимировнаМосковский государственный университет им. М. В. Ломоносова; НПК «Криптонит»аспирантка факультета вычислительной математики и кибернетики; специалист-исследователь лаборатории криптографииvysotskaya.victory@gmail.com
Всего: 1

Ссылки

https://csrc.nist.gov/Projects/post-quantum-cryptography/Post-Quantum-Crypto graphy-Standardization/Call-for-Proposals.
Чижов И. В., Бородин М. А. Классификация произведений Адамара подкодов коразмерности 1 кодов Рида - Маллера // Дискретная математика. 2020. №32(1). С. 115-134.
McEliece R. J. A public-key cryptosystem based on algebraic coding theory // DSN Progress Report. 1978. No. 4244. P. 114-116.
Vysotskaya V. V. Characteristics of Hadamard Square of Reed - Muller Subcodes of Special Type. https://eprint.iacr.org/2020/507.
 О новых оценках размерности подкодов кодов Рида - Маллера, квадрат Адамара которых максимален | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/28

О новых оценках размерности подкодов кодов Рида - Маллера, квадрат Адамара которых максимален | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/28