Метод построения доказуемо стойкой постквантовой схемы защиты информации на основе линейных кодов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Турченко Олег Юрьевич

• Турченко Олег Юрьевич
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Турченко Олег Юрьевич

1.2.1 Код Гоппы

1.2.2 Код Рида-Соломона

1.2.3 Код Рида-Маллера

1.3 Схемы защиты информации на линейных кодах

1.3.1 Схема Мак-Элиса

1.3.2 Схема Нидеррайтера

1.3.3 Схемы типа Мак-Элиса

1.4 Распознавание кода

1.4.1 Распознавание без накопления кодовых слов

1.4.2 Распознавание с накоплением кодовых слов

1.5 Декодирование по информационным совокупностям

1.6 Выводы

2 Доказуемая стойкость схем защиты информации

2.1 Основные понятия

2.2 Свойства стойкости асимметричных схем

2.2.1 Свойство OW - CPA

2.2.2 Свойство IND - CPA

2.2.3 Свойство IND - CCA

2.2.4 Свойство IND - CCA2

2.3 Модели доказательства стойкости

2.4 IND - CPA схема Нуджимы и соавторов

2.5 IND - CCA2 схемы типа Мак-Элиса в стандартной модели

2.5.1 Схема Детлинга и соавторов

2.5.2 Схема Персичетти

2.6 Выводы

3 Новые доказуемо стойкие кодовые схемы

3.1 Метод построения IND - CCA2 стойких схем

3.2 Новые IND - CPA схемы типа Мак-Элиса в стандартной модели

3.2.1 Схема 2McE/

3.2.2 Схема w2McE'/

3.2.3 Схема w2McE;

3.2.4 Схема McEnbaaic

3.2.5 Схема McEnaMX

3.3 Новая IND - CCA2 схема McEn/w

3.4 Доказательство стойкости схем 2McE/, ^2McE'/, w2McE/

3.5 Доказательство стойкости схем McEnbasici McEnaux, McEn^n

3.6 Выводы

4 О практической реализации

4.1 Выбор параметров безопасности

4.1.1 Выбор параметров кода

4.1.2 Выбор схемы подписи

4.1.3 Выбор размера информационного сообщения

4.1.4 Сравнение с известными схемами типа Мак-Элиса для

предложенных параметров

4.2 Концепция шифрования «один ко многим»

4.2.1 Схема £-MCEnfin в шифровании «один ко многим»

4.2.2 Сравнение с RSA и NTRU в шифровании «один

ко многим»

4.3 Аппаратно-программная реализация

4.3.1 Особенности реализации функций ПЛИС

4.3.2 Сравнение реализации предложенной схемы с используемыми на практике

4.3.3 Оценка параметров реализации схем подписи и хэширования

4.4 Эксперименты

4.4.1 Проверка неотличимости публичного ключа схемы Мак-Элиса от случайной матрицы

4.4.2 Проверка выполнимости алгоритма Verify

4.5 Выводы

Заключение

Основные обозначения

Литература

Введение диссертации (часть автореферата) на тему «Метод построения доказуемо стойкой постквантовой схемы защиты информации на основе линейных кодов»

Введение

Актуальность темы исследования. Активные исследования в области построения и анализа схем защиты информации, устойчивых в постквантовую эпоху, ведутся по нескольким направлениям [1]. Среди них можно выделить направления, связанные с использованием решеток, хэш-функций, полиномов нескольких переменных и помехоустойчивых кодов. Применение помехоустойчивых кодов характеризуется, с одной стороны, простотой программно-аппаратной реализации алгоритмов шифрования и расшифрования, а с другой стороны, высокой скоростью этих операций. Первой кодовой схемой защиты информации является система Р. Мак-Элиса [2], построенная на основе кода Гоппы. Для систем типа Мак-Элиса, независимо от используемого кода, известны атаки на основе декодирования по информационным совокупностям [3-6]. Поэтому для обеспечения высокого уровня стойкости необходимо использовать коды Гоппы большой длины и размерности, что приводит к большому размеру публичного ключа. Замена кода Гоппы на некоторые известные коды, как показали исследования, снижает стойкость системы. В частности, для обобщенных кодов Рида-Соломона (ОРС-коды), двоичных кодов Рида-Маллера (РМ-коды), БЧХ кодов, алгебро-геометрических кодов, а также прямой суммы этих кодов известны эффективные алгоритмы нахождения подходящих секретных ключей по публичным ключам (структурные атаки) [7-9]. Исследователями предложен ряд модификаций протокола с целью повышения стойкости схемы Мак-Элиса на кодах, для которых известны структурные атаки.

К известным модификациям протокола можно отнести модификации М. Балди и соавторов [10], модификации В.М. Сидельникова [11] и ее обобщения [12], [13]. В ряде случаев для этих модификаций найдены эффективные структурные атаки [14], [15]. В то же время для системы типа Мак-Элиса на кодах Гоппы на настоящий момент такие атаки не известны.

Помимо стойкости схем защиты информации с публичным ключом к структурным атакам необходимо обеспечивать стойкость к атакам на шифртекст. Обычно стойкость к таким атакам рассматривается в одной из двух моделей: стандартной модели или модели со случайным оракулом [16]. Суть стандартной модели заключается в том, что стойкость доказываемой схемы сводится к вычислительной сложности решения некоторой задачи. Модель со случайным оракулом отличается от стандартной модели тем, что все используемые хэш функции в схеме заменяются случайными оракулами, то есть такими функциями, которые обладают всеми свойствами хэш функций, но при этом на выходе выдают истинно случайные значения при различных аргументах. Поскольку основные кандидаты конкурса NIST [17-21] на постквантовые схемы шифрования и инкапсуляции ключа являются стойкими к атакам на шифртекст только в модели со случайным оракулом, то также актуально построение и исследование схем, стойких в стандартной модели. Известен ряд модификаций схемы Мак-Элиса, стойких в стандартной модели. В частности, к таким схемам относится модификация рандомизированного Мак-Элиса [22], основанная на применении вероятностного шифрования. Эта схема обеспечивает стойкость к атакам по подобранным открытым текстам (IND - CPA). Однако использование только вероятностного шифрования не обеспечивает стойкость к самому сильному классу атак - адаптивным атакам по подобранным шифртек-стам (IND -CCA2). В рамках стандартной модели в [23,24] предложены конструкции схем, с одной стороны, устойчивых к структурным атакам, а с другой стороны, устойчивых к адаптивным атакам по подобранным

шифртекстам. Данные схемы основаны на использовании коррелированных образов однонаправленных функций (correlated products) [25]. Однако эти схемы характеризуются малой скоростью передачи информации (отношение длины информационного сообщения к длине шифртекста). Таким образом, актуальна задача построения схем в рамках стандартной модели, одновременно обладающих стойкостью к адаптивным атакам по подобранному шифртексту и высокой скоростью передачи информации.

Объектом исследования являются кодовые схемы защиты информации с публичным ключом; предметом исследования - методы построения доказуемо стойких схем защиты информации.

Цель работы. Цель работы - разработка и исследование схемы защиты информации на основе схемы Мак-Элиса, одновременно обладающей доказуемой стойкостью к атакам на сообщение в стандартной модели и информационной скоростью, приемлемой для практического применения.

Задачи диссертационной работы. Основные задачи диссертационной работы:

• Построить схему защиты информации, основываясь на схеме Мак-Элиса и ее модификациях для защиты от адаптивных атака по подобранным шифртекстам в стандартной модели.

• Теоретически обосновать стойкость построенной схемы к адаптивным атакам по подобранным шифртекстам в стандартной модели.

• Провести анализ параметров построенной схемы и сравнить с известными.

• Разработать аппаратного-программную реализацию и провести анализ ее технических характеристик.

Методы исследования. Построение схемы защиты информации на основе схемы Мак-Элиса проводится при помощи методов теории кодиро-

вания, методов вероятностного шифрования и использования конструкции коррелированных образов однонаправленных функций. При доказательстве стойкости построенной схемы используются методы теории вероятностей, линейной алгебры и теории доказуемой стойкости.

Научная новизна. В диссертации получены следующие новые научные результаты.

1. Разработан статистический критерий и алгоритм проверки принадлежности выборки заданному коду, подтверждающий предположение, что не существует эффективного алгоритма, который мог бы отличить два случайных зашумленных кодовых слова от случайных векторов.

2. Разработаны новые схемы шифрования на основе схемы Мак-Элиса и доказана их IND - CPA стойкость в рамках стандартной модели.

3. Разработан метод построения новой схемы, обладающей IND - CCA2 стойкостью в рамках стандартной модели, более высокой информационной скоростью и наименьшим размером публичного ключа по срав-

IND -CCA2

дартной модели.

4. Подобраны подходящие для реализации параметры IND - CCA2 схемы, предложен вариант аппаратно-программной реализации разработанной схемы и выполнен анализ технических характеристик.

Теоретическая значимость. Научной ценностью является метод построения новой доказуемо стойкой схемы асимметричного шифрования типа Мак-Элиса на основе кода Гоппы с информационной скоростью, приемлемой для практического применения. Разработанный метод может быть использован для построения новых схем этого типа на других кодах.

Практическая ценность. С практической точки зрения, ценность разработанной схемы заключается в том, что она может быть применена

в прикладных протоколах информационного взаимодействия, где предъявляются высокие требования к защите информации. Так как шифрование и расшифрование основаны на алгоритмах линейной алгебры, то данные алгоритмы легко реализуются аппаратно и могут эффективно использоваться в различных устройствах защиты информации.

Область исследования. Содержание диссертации соответствует паспорту специальности 2.3.6 — «Методы и системы защиты информации, информационная безопасность» (технические науки): исследования в области безопасности криптографических алгоритмов, криптографических примитивов, криптографических протоколов. Защита инфраструктуры обеспечения применения криптографических методов (п. 19).

Степень достоверности результатов. Достоверность результатов, полученных в ходе диссертационной работы, обосновывается математическими доказательствами, вычислительными экспериментами и наличием опубликованных результатов.

Апробация. Результаты диссертационных исследований представлены на следующих всероссийский и международных конференциях:

1. 15 Всероссийская конференция «Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография"» 81ВЕСКУРТ'16 (очное участие, г. Новосибирск, 2016 год).

2. 18-ая Всероссийская национальная молодежная научно-практическая конференция «Фундаментальные исследования, методы и алгоритмы прикладной математики в технике, медицине и экономике» (г. Новочеркасск, 2019 год).

3. Международная научная конференция «Актуальные проблемы прикладной математики, информатики и механики» (г. Воронеж, 2020 год).

4. XXVII Научная конференция «Современные информационные технологии: тенденции и перспективы развития» (г. Ростов-на-Дону, 2020 год).

5. 19 Всероссийская конференция «Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография"» SIBECRYPT'20 (г. Новосибирск 2020 год).

6. Международный IX симпозиум «Современные тенденции в криптографии» CTCrypt 2020 (очное участие, г. Москва, 2020 год).

7. 20 Всероссийская конференция «Сибирская научная школа-семинар с международным участием "Компьютерная безопасность и криптография"» SIBECRYPT'21 (очное участие, г. Новосибирск 2021 год).

Публикации. Основные результаты по теме диссертации опубликованы в 8 научных печатных изданиях [26], [27], [28], [29], [30], [31], [32], [33], из которых: 2 - в международных научных изданиях, индексируемых Scopus [27], [28], 1 - в рецензируемых журналах из списка ВАК [32], 5 - в материалах конференций и других научных печатных изданиях [26], [29], [30], [31], [33].

Личный вклад автора. Все результаты по теме диссертационного исследования получены лично автором. В работах, опубликованных в соавторстве [26], [27], [28], [29], [30], [32], [33], научным руководителем Косола-повым Ю.В. были поставлены задачи, предоставлены идеи по возможным подходам решения данных задач и помощь в виде обсуждений формы и содержания доказательств.

Структура и объем работы. Диссертационная работа изложена на 124 страницах, включает 4 главы, 3 рисунка, 28 таблиц и список литературы из 123 наименований.

В первой главе рассматриваются особенности и свойства современ-

ных схем шифрования с публичным ключом. Одним из перспективных направлений постквантовой защиты информации являются кодовые схемы. В главе рассматриваются основные понятия теории кодирования и наиболее часто используемые коды в области защиты информации. Описываются известные схемы шифрования с публичным ключом, основанные на кодах. В последних двух разделах первой главы рассматриваются основные методы распознавания кода и уязвимости кодовых схем.

Во второй главе приводятся основные понятия из области доказуемой стойкости схем защиты информации с публичным ключом. А именно: свойства однонаправленности и неразличимости схем защиты информации с публичным ключом, а также модели доказательства стойкости. Далее описываются наиболее известные доказуемо стойкие схемы защиты информации с публичным ключом в стандартной модели, основанные на кодах.

Третья глава посвящена построению ряда новых доказуемо стойких схем защиты информации с публичным ключом в стандартной модели, основанных на кодах. В начале главы описывается новый метод построения ШБ — ССА2 стойких схем защиты информации, обобщающий метод ¿'-повторенного шифрования. Для каждой из предложенных схем приводится строгое теоретическое обоснование свойств стойкости к атакам на шифртекст.

В четвертой главе производится выбор параметров доказуемо стойких асимметричных схем в стандартной модели для применения на практике. Выполняется сравнение разработанной схемы с известными доказуемо стойкими асимметричными схемами в стандартной модели для предложенных параметров. После анализа параметров описывается концепция шифрования, в которой использование разработанной схемы является наиболее целесообразным. В рамках данной концепции выполняется сравнение с некоторыми асимметричными схемами, имеющими широкое применение на практике в настоящий момент. После этого рассматривается возмож-

ныи вариант аппаратно-программной реализации разработанной схемы. Выполняется оценка ресурсов и характеристик предлагаемой аппаратно-программной реализации и сравнение с характеристиками известных реализаций других асимметричных схем. В последнем разделе производятся эксперименты для подтверждения теоретических результатов.

Глшзв

Современные схемы защиты информации с публичным ключом

1.1 Обзор схем защиты информации с публичным ключом

В настоящее время необходимость защиты конфиденциальности передаваемых данных возникает во многих областях повседневной жизни. При этом распространены ситуации, в которых пользователи обладают возможностью передавать данные только по открытым каналам. В таком случае пользователи не могут передать секретный ключ для использования стандартного симметричного шифрования. Для решения данной проблемы применяют схемы шифрования с публичным ключом (асимметричные схемы). Схема шифрования с публичным ключом представляет собой систему с парой ключей: публичный и закрытый ключи. Основная идея таких схем заключается в том, что любой пользователь может зашифровать сообщение с помощью публичного ключа, а расшифровать может лишь владелец секретного. Также схемы шифрования с публичным ключом часто используют для формирования цифровых подписей. Однако схемы шифрования с публичным ключом уступают по характеристикам симметричным схемам шифрования. В частности, у схем с публичном ключом скорость шифрова-

ния ниже, а ключевая система требует большего объема памяти. Так, например, согласно рекомендациям NIST [34] рекомендуемый размер ключа симметричных схем равен 256 битам, а для RSA (одной из наиболее популярных асимметричных схем) - 2048 битам. Поэтому стандартные протоколы передачи информации, такие как TLS/SSL, IPsec комбинируют схемы шифрования. А именно в начале передачи данных пользователи обмениваются или вырабатывают ключи симметричного шифрования с помощью схемы с открытым ключом. Затем, когда оба пользователя имеют симметричные ключи, они используют симметричную схему для шифрования передаваемых данных.

Тем не менее область применения схем шифрования с публичным ключом не ограничена только передачей ключа. Так, например, в широковещательном шифровании [35-37] и шифровании «один ко многим» [38, 39] схемы шифрования с публичным ключом могут использоваться для передачи больших циркулярных сообщений. На данный момент можно выделить четыре основных вида схем шифрования с публичным ключом: теоретико-числовые, кодовые, основанные на решетках и на изогениях. К наиболее известным теоретико-числовым схемам можно отнести схемы RSA [40], ElGamal [41], ЕСС [42]. Стойкость теоретико-числовых схем основывается на вычислительной сложности задач дискретного логарифмирования и дискретной факторизации. Основным преимуществом схем данного типа является относительно небольшой размер публичного ключа. Недостатком теоретико-числовых схем является уязвимость к атакам на квантовых компьютерах с помощью алгоритма Шора. К наиболее известных кодовым схемам можно отнести схемы Мак-Элиса [2] и Нидеррайтера [43]. Стойкость кодовых схем основывается на сложности декодирования случайного кода. В [44] доказано, что данная задача является NP - сложной. Более того, на данный момент нет известных алгоритмов решения данной задачи даже при использовании квантового компьютера. К преимуществам кодовых

схем можно отнести более высокую скорость шифрования и расшифрования и простоту аппаратной реализации. К недостаткам кодовых схем можно отнести большие размеры публичных ключей. Среди схем на решетках выделяются NTRU [45], KYBER [18] и SABER [46]. Стойкость схем на решетках основана на сложности решения задач поиска кратчайшего вектора и обучения с ошибками, решение которых является сложным даже при использовании квантовых компьютеров. В [47] доказано, что задача поиска кратчайшего вектора является NP - сложной. К преимуществам схем па решетках можно отнести высокую скорость шифрования и расшифрования и небольшие размеры ключей. Среди недостатков схем на решетках можно выделить следующие: схемы на решетках требуют большого числа ресурсов при аппаратной реализации; несмотря на трудность решения за-

NP

случае, более того на данный момент существуют теоретические уязвимости, которые не покрываются доказательствами стойкости [48]. Наиболее известной на данный момент схемой на изогениях являются SIDH [49] и SIKE [20]. Стойкость таких криптосистем основана на сложности нахождения изогении между двумя суперсингулярными эллиптическими кривыми. Преимуществом схем на изогениях являются небольшие размеры ключей и шифртекстов. Недостатком является низкая скорость шиффрования и расшифрования. В настоящее время наиболее используемыми на практике являются теоретико-числовые схемы. Тем не менее развитие квантовых вычислений является серьезной угрозой для такого рода схем и современной криптографии в целом. Согласно последнему отчету [50] в качестве постквантовых схем асимметричного шифрования и обмена ключей будут рассматриваться следующие схемы: одна на решетках (KYBER), три на кодах (МсЕНесеКЕМ [17], BIKE [19], HQC [21]) и одна на изогениях (SIKE). С учетом данного факта, а также особенностей разных типов схем далее будут рассмотрены кодовые схемы шифрования с публичным ключом.

1.2 Основы теории линейных кодов

Пусть щ t - натуральные числа, 2t < щ [п] = {1,...,п}, ¡3 С [п], 2М - множество всех подмножеств [n], Fg - поле Галуа мощности д, где q степень простого числа. Носителем вектора m будем называть множество supp(m) = {г : mi = 0}, а весом Хэмминга этого вектора -число wt(m) = |supp(m)|. Расстоянием между век торами х и y будем обозначать d(x, y) = wt(x — y), а побитовым произведением векторов х = (х1, х2,..., хп) и y = (у1, у2,..., уп) будем называть операцию вида х 0 y = (х1у1, х2у2,..., хп Уп)- Пуст ь С является линейным подпространством F™ размерности к, a d - минимальный вес вектора из С. Тогда, будем говорить, что С - липейный [п, к, dj-код, где п - длина кода, к - размерность кода, a d - кодовое расстояние кода С. Порождающей матрицей G [п, к, dj-кода С является (к х п)-матрица, строки которой образуют базис линейного пространства С над полем Fg. Матри ца Н размер а (п — к) х п называется проверочной матрицей [п, к, dj-кода С, если GHт = 0. Базис кода С будем обозначать как Вс- Рассмотрим зашумлеппое кодовое слово y = ce = Gx + e, где х - информационное сообщение, ae - вектор ошибки. Тогда произведение вида Нy = Нc + Нe = Нe называется синдромом y

информации на основе схемы Мак-Элиса.

1.2.1 Код Гоппы

Пусть g(z) = д0+д1z+...+gtzt G Fqm[z] и пусть L = {a\, a2, ...,an} С F^m такие, что g(a,i) = 0 для всех ai G L. Тогда код Гоппы с параметрами д(z) и L определяется следующим образом:

) c = (ci,C2,...,Cn) G Fqn : V] Сг = 0 mod g(z) \

Z — Qj

I i=i % )

Отметим, что параметры g(z) и L полностью описывают [п, к, dj-код. Именно: п = \L\, к = п — mt, d = 2t + 1. Проверочная матрица кода Гоппы имеет

д(а2)-1 ... д(ап)—1 ^ 1 ... а2д(ап)-1

\aigt—1(ai)—1 а^д^)-1 ... at~1g(an)—1 В качестве алгоритма декодирования можно рассмотреть алгоритм Пат-терсона [51] для бинарного кода Гоппы, принимающего на вход зашум-ленный кодовый вектор y = (у1,...,уп) и возвращающий вектор ошибок e = (d,..., еп):

п

1. Вычислить синдром в виде S(z) = ^ jz^-

i=1

2. Найти Р(z) = \J(S(z)—1 + z) mod g(z).

3. Если предыдущий шаг не удался (если S(z) = 0 mod g(z)), то возвращаем e = 0, иначе переходим на следующий шаг.

4. Вычислить u(z) и v(z) из уравнения u(z) = v(z)Р(z) mod g(z).

5. Вычислить локатор ошибок a(z) = u(z)2 + zv(z)2.

6. Вычислить корни локатора ошибок: В = {i\a(a.i) = 0}.

{1, если i ф В, 0, если г ф В. Теперь рассмотрим следующий код.

1.2.2 Код Рида-Соломона

Определим код Рида-Соломона аналогично [52]. Пусть а - примитивный элемент поля Fq. Пусть В = {1,а, а2,..., a4-2}, Rq(к) - множество всех

вид:

Н =

9(а1) 1 а1д(а1)—1

многочленов степени не более к — 1 с коэффициента ми из Щ. Рассмотрим отображение еУв,к : Rq(к) ^ Щ-1 сопоставляющее каждому многочлену из Яд(к) вектор еувкк(/(х)) = (/(1),/(а),...,/(а4-2)). Тогда образ отображения еУвк будем называть [п, к, -кодом Рида-Соломона, где п = д — 1, ё, = д — к. Можно отметить, что код Рида-Соломона является МДР кодом, т.е. для пего выполняется равенство ё, = п — к + 1. Порождающая матрица кода Рида-Соломона имеет вид:

/11 1 ... 1 \

С =

а 2

а

а

а

а

ч—2

2(4—2)

\1 а

к—1 а(к—1)2

а

а(к—1)(Ч—2) у

Среди наиболее применяемых на практике декодеров кода Рида-Соломона можно выделить декодер Берлекэмпа-Велча [53], исправляющий не более ¿ошибок, где Ь = \п—г \ ■ На вход алгоритм получает зашум ленный кодовый вектор у = (у1,..., уп) и возвращает /(х), соответствующий исходному кодовому слову:

1. Найти ненулевое решение (щ, ...,Щ+к—1 системы уравнений:

Ь+к—1

Уг е [0, п — 1] : ^

пу а'3 —

3=0

У г ^ 3=0

а, а'3 = 0.

г+к-1

Е пг-

3=0

2. Вычислить /(х) =

Е ^з^

3=0

то вернуть ошибку, иначе вернуть /(х).

.

Теперь рассмотрим еще один код.

1.2.3 Код Рида-Маллера

Существует множество подходов для определения кодов Рида-Маллера. В настоящей работе будем определять данное семейство кодов аналогично [52]. Коды Рида-Маллера являются бинарными кодами с целыми параметрами т и г, где т > 0,г > 0,г < т. Параметры [п,^,^]-кода Рида-

Маллера выражаются следующим образом: п = 2т,к = ^ Сгт= 2т-г.

г=1

Определим код Рида-Маллера через порождающую матрицу. Именно, порождающая матрица представляет собой блочную матрицу-столбец с блоками специального вида: Число столбцов в каждом блоке равно п = 2т. Теперь опишем данные блоки.

1. Блок С(0)

представляет собой вектор-столбец из единиц.

2. Блок С(1) представляет собой матрицу т х п, столбцы которой представляют собой упорядоченную слева направо последовательность целых чисел в бинарном виде от 0 до 2п. Младшие разряды данной последовательности расположены в нижней строке блока С(1\

3. Блок

С® представляет собой матрицу С'т х 2т. Строками матрицы С® являются всевозможные побитовые произведения г строк матрицы С«. Запись произведений в строки матрицы производится в лексикографическом порядке.

Опишем способ декодирования, приведенный в [52]. Рассмотрим случай,

когда нам необходимо декодировать зашумленный кодовый вектор у =

(у1,..., уп). Сначала получим последний бит информационного вектора Хк-

Для этого строятся проверочные суммы:

/

= У1 + ... + У2Г < &2 = У2Г+1 + ... + У2Г+1

(У^тп-г = У2т-1+1 + ... + У2т

Полученные проверочные обладают следующим свойством: а1 = а2 = ... = а2ш-г = Хк при отсутствии ошибок. Таким образом, если ошибок не более, чем 2т—т—1 — 1 то Хк однозначно восстанавливается мажоритарным голосованием по аг. Для восстановления произвольного бита Х3 проводятся следующие операции. Пусть ^'-ая строка порождающей матрицы имеет вид: а(3х) 0а(32) 0... 0а(з1\ где а(г - строки блока С(1\ Теперь переставим строки в блоке таким образом, чтобы строки а(з1\ а(з2\ ..., а(31^ оказались последними с сохранением их порядка, а столбцы переставим так, чтобы новая матрица С« совпала со старой. После указанных преобразований ^'-ая строка будет обладать свойствами к-ой строки. Поэтому можно применить указанные действия для восстановления ху, поменяв индексы у вектора у в соответствии с перестановкой столбцов. Таким образом, если ошибок не более, чем 2т—г—1 — 1, то вектор х однозначно восстанавливается.

1.3 Схемы защиты информации на линейных кодах

В настоящем разделе рассматривается ряд схем защиты информации на основе кодов. Далее при описании операций шифрования и расшифрования мы будем использовать следущие обозначения. Пусть 2 - схема защиты информации, вк - секретный ключ, рк - публичный ключ. Тогда шифрование сообщения т с помощью публичного ключа рк будем обозначать как {т}^- Расшифрование шифрограммы с с помощью секретного ключа вк будем записывать как {с}^. Обозначим Еггп¿ф подмножество Fn такое, что любой вектор е = (&1, ...,еп)(€ Еггп^ф) имеет вес Хэмминга £ и ег = 0 для любо го г € р. Когда ¡3 = 0 будем пис ать Еггп^-

1.3.1 Схема Мак-Элиса

Рассмотрим схему Мак-Элиса (МсЕ), предложенную в [2]. Пусть С (С Fn) - линейный [п, к, ^]-код. Пусть С является порождающей матрицой кода С, а число ошибок, исправляемых кодом, равной = |_^г-\. Секретным ключом вк является тройка матриц (51, С, Р), где £ - случайная невырожденная (к х &)-матрица над полем а Р - перестановочная (п х п)-матрица. Публичным ключом рк является пара (С = ЗСР,Ь). Шифрование сообщения т € Fk выполняется согласно правилу:

{т}МсЕ = тС + е = с, е €К Еггп^. с

декодер, возвращающий информационный вектор Беса : Fn ^ Fk код а С и секретный ключ вк:

{с}МсЕ = Беса (сР-1)Б-1. (1.1)

Важно отметить, что в оригинальной схеме Мак-Элиса в качестве кода С использовался код Гоппы.

1.3.2 Схема Нидеррайтера

Рассмотрим схему Нидеррайтера (N1^ на коде С (С предложенную в [43]. Пусть Н является проверочной матрицой кода С, а число ошибок, исправляемых кодом, равной = ■ ] • Секретным ключом й к является пара матриц ( Б, Н), где 3 - случайная певырожденная (п — к х п — &)-матрица над полем Щч. Публичным ключом рк является пара ( Н = БН, £). Перед шифрованием информационное сообщение кодируется в вектор длины п с весом не более Полученное сообщение т шифруется согласно правилу:

{т}™ = Нтт = с.

Для расшифрования шифртекста с необходимо использовать эффективный декодер, возвращающий вектор ошибки Бее^ : ¥пч ^ Щк кода С и секретный ключ в к:

{с}™ = Беес (3—1с). С

Рида-Соломона. Данная схема была взломана Сидельниковым и IПестиковым [54] при использовании предложенного кода Рида-Соломона. Также можно отметить, что взлом схемы Нидеррайтера полиномиально сводится к взлому Мак-Элиса и наоборот.

1.3.3 Схемы типа Мак-Элиса

Рассмотрим ряд схем, основывающихся на схеме Мак-Элиса. Стоит отметить, что для оригинальной схемы Мак-Элиса до сих пор не найдено атакующих алгоритмов, способных за полиномиальное время восстановить секретный ключ или получить какую-либо существенную информацию об этом ключе. Основной целью большинства описанных далее схем является уменьшение размера публичного ключа, так как публичный ключ схемы Мак-Элиса при использовании кода Гоппы имеет достаточно большие раз-

Список литературы диссертационного исследования кандидат наук Турченко Олег Юрьевич, 2022 год

Литература

[1] Post-Quantum Cryptography [Электронный ресурс]. — URL: https://csrc.nist.gov/Projects/Post-Quantum-Cryptography (дата обращения 01.07.2022).

[2] McEliece, R. J. A Public-Key Cryptosystem Based On Algebraic Coding Theory / R. J. McEliece // DSN Progress Report. - 1978.

[3] Prange, E. The use of information sets in decoding cyclic codes / E. Prange // IRE Trans. - 1962. - Vol. 8. - P. 5-9.

[4] May, A. Decoding Random Linear Codes in O(2°-054n) / A. May, A. Meurer, E. Thomae // Advances in Cryptology - ASIACRYPT 2011 / ed. by D. H. Lee, X. Wang. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2011. - P. 107-124.

[5] Becker, A. Decoding Random Binary Linear Codes in 2n/20: How 1+1=0 Improves Information Set Decoding / A. Becker, A. Joux, A. May, A. Meurer // Advances in Cryptology - EUROCRYPT 2012 / ed. by D. Pointcheval, T. Johansson. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - P. 520-536.

[6] Hamdaoui, Y. A Non Asymptotic Analysis of Information Set Decoding / Y. Hamdaoui, N. Sendrier // IACR Cryptol. ePrint Arch. — 2013. — Vol. 2013. - P. 162.

[7] Sidel'nikov, V. On an Encoding System Constructed on the Basis of Generalized Reed - Solomon Codes / V. Sidel'nikov, S. Shestakov // Discrete Math. Appl. - 1978. - Vol. 4. - P. 439-444.

[8] Borodin, M. Effective attack on the McEliece cryptosystem based on Reed Muller codes / M. Borodin, I. Chizhov // Diskr. Mat. — 2014.

_ Vol. 26. - P. 10-20.

[9] Деундяк, В. Анализ стойкости некоторых кодовых криптосистем, основанный на разложении кодов в прямую сумму / В. Деундяк, Ю. Косолапой // Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование. - 2019. - Т. 12. - С. 89-101.

[10] Baldi, М. A New Analysis of the McEliece Cryptosystem Based on QC-LDPC Codes / M. Baldi, M. Bodrato, F. Chiaraluce // Security and Cryptography for Networks / ed. by R. Ostrovsky, R. De Prisco, I. Visconti. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2008. — P. 246-262.

[11] Sidel'nikov, V. M. Open coding based on Reed-Muller binary codes / V. M. Sidel'nikov // Diskret. Mat. - Vol. 6. - P. 3-20.

[12] Kabatiansky, G. A new code-based cryptosystem via pseudorepetition of codes / G. Kabatiansky, C. Tavernier // Proceedings of Sixteenth International Workshop on Algebraic and Combination Coding Theory. _ 2018. - P. 189-191.

[13] Egorova, E. A new code-based public-key cryptosystem resistant to quantum computer attacks / E. Egorova, G. Kabatiansky, E. Krouk, C. Tavernier // Journal of Physics: Conference Series. — 2019. — Vol. 1163. - P. 012061.

[14] Otmani, A. Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes / A. Otmani, J.-P. Tillich, L. Dallot // Mathematics in Computer Science. — 2008.^04. — Vol. 3.

[15] Deundyak, V. On the strength of asymmetric code cryptosystems based on the merging of generating matrices of linear codes / V. Deundyak, Y. Kosolapov // 2019 XVI International Symposium "Problems of Redundancy in Information and Control Systems"(REDUNDANCY). — 2019. - P. 143-148.

[16] Bellare, M. Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols / M. Bellare, P. Rogaway // Proceedings of the 1st ACM Conference on Computer and Communications Security. — CCS '93. _ URL: New York, NY, USA : Association for Computing Machinery, 1993. - P. 62-73.

[17] McElieceKEM [Электронный ресурс]. — URL: https://classic.mceliece.org/ (дата обращения 01.07.2022).

[18] CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based КЕМ / J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck et al. // 2018 IEEE European Symposium on Security and Privacy (EuroS P). — 2018. - P. 353-367.

[19] BIKE [Электронный ресурс]. — URL: https://bikesuite.org/ (дата обращения 01.07.2022).

[20] SIKE [Электронный ресурс]. — URL: https://sike.org/ (дата обращения 01.07.2022).

[21] HQC [Электронный ресурс]. — URL: https://pqc-hqc.org/ (дата обращения 01.07.2022).

[22] Nojima, R. Semantic security for the McEliece cryptosystem without random oracles / R. Nojima, H. Imai, K. Kobara, K. Morozov // Des. Codes Cryptogr. - 2008. - Vol. 49. - P. 289-305.

[23] Dottling, N. A CCA2 secure variant of the McEliece cryptosystem / N. Dottling, R. Dowsley, J. Miiller-Quade, A. C. A. Nascimento // IEEE Trans. Inform. Theory. - 2012. - Vol. 58. - P. 6672-6680.

[24] Persichetti, E. On a CCA-secure variant of McEliece in the standard model / E. Persichetti // Provable Security. - 2018. - Vol. 11192.

- P. 165-181.

[25] Rosen, A. Chosen-ciphertext security via correlated products / A. Rosen, G. Segev // Theory of cryptography. — Springer, Berlin, 2009. — Vol. 5444 of Lecture Notes in Comput. Sci. - P. 419-436.

[26] Косолапов, Ю. В. Поиск информационного сообщения в зашумлённых кодовых блоках при многократной передаче данных / Ю. В. Косолапов, О. Ю. Турченко // Прикладная дискретная математика. Приложение. - 2016. - №9. - С. 55-57. - DOI 10.17223/2226308Х/9/22.

[27] Kosolapov, Y. V. Application of one method of linear code recognition to the wire-Tap channel / Y. V. Kosolapov, O. Y. Turchenko // Prikladnaya Diskretnaya Matematika. - 2017. - No 35. - P. 76-88. - DOI 10.17223/20710410/35/7.

[28] Kosolapov, Y. V. On the construction of a semantically secure modification of the McEliece cryptosystem / Y. V. Kosolapov, O. Y. Turchenko // Prikladnaya Diskretnaya Matematika. — 2019. — Vol. 45. — P. 33-43.

- DOI 10.17223/20710410/45/4.

[29] Косолапов, Ю. В. Проверяемая конструкция конкатенации шифртек-стов криптосистемы типа Мак-Элиса / Ю. В. Косолапов, О. Ю. Тур-

ченко // Актуальные проблемы прикладной математики, информатики и механики : сборник трудов Международной научной конференции, Воронеж, 11-13 ноября 2019 года / ФГБОУ ВО "Воронежский государственный университет". — Воронеж : Научно-исследовательские публикации, 2020. — С. 256-259.

[30] Kosolapov, Y. V. Efficient s-repetition method for constructing an ind-cca2 secure McEliece modification in the standard model / Y. V. Kosolapov, O. Y. Turchenko // Applied Discrete Mathematics. Application. — 2020. _ No 13. - P. 80-84. - DOI 10.17223 2226308X 13 24.

[31] Турченко, О. Ю. Построение протокола передачи данных для семантически стойкой модификации криптосистемы типа Мак-Элиса / О. Ю. Турченко // Современные информационные технологии: тенденции и перспективы развития : материалы XXVII научной конференции, Ростов-на-Дону -Таганрог, 24-26 сентября 2020 года / под ред. Г. В. Муратова, С. С. Михалкович, В. С. Пилиди, А. Н. Соловьев, В. Ю. Тополов. — Ростов-на-Дону -Таганрог : Южный федеральный университет, 2020. — С. 270-272.

[32] Kosolapov, Yu. V. IND-CCA2 secure McEliece-type modification in the standard model / Yu. V. Kosolapov, O. Yu. Turchenko // Математические вопросы криптографии. — 2021. — Vol. 12. — No 2. — P. 111-128. - DOI 10.4213/mvk359.

[33] Kosolapov, Y. V. Choosing parameters for one IND-CCA2 secure McEliece modification in the standard model / Y. V. Kosolapov, O. Y. Turchenko // Applied Discrete Mathematics. Application. — 2021. — No 14. — P. 110114. - DOI 10.17223 2226308X 14 24.

[34] NIST Special Publication 800-57 Part 3 Revision 1: Recommendation for Key Management: Application-Specific

Key Management Guidance [Электронный ресурс]. — URL: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57Pt3rl.pdf (дата обращения 01.07.2022).

[35] Fiat, A. Broadcast Encryption / A. Fiat, M. Naor // Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology. — CRYPTO '93. — Berlin, Heidelberg : Springer-Verlag, 1994. - P. 480-491.

[36] Ak, M. Efficient broadcast encryption with user profiles / M. Ak, K. Kaya, K. Onarlioglu, A. Selcuk // Information Sciences. — 2010. — Vol. 180.

- P. 1060-1072.

[37] Zhang, M. Efficient and adaptively secure broadcast encryption systems / M. Zhang, B. Yang, Z. Chen, T. Takagi // Security and Communication Networks. - 2013. ^08. - Vol. 6.

[38] Bellare, M. Public-Key Encryption in a Multi-user Setting: Security Proofs and Improvements / M. Bellare, A. Boldyreva, S. Micali // Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 1418, 2000, Proceeding. — Vol. 1807 of Lecture Notes in Computer Science.

- Springer, 2000. - P. 259-274.

[39] Baudron, O. Extended Notions of Security for Multicast Public Key Cryptosystems / O. Baudron, D. Pointcheval, J. Stern // Automata, Languages and Programming / ed. by U. Montanari, J. D. P. Rolim, E. Welzl. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2000. — P. 499-511.

[40] Rivest, R. L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems / R. L. Rivest, A. Shamir, L. Adleman // Commun. ACM. _ 1978. _ Vol. 21. - P. 120-126.

[41] ElGamal, Т. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms / T. ElGamal // Advances in Cryptology / ed. by G. R. Blakley, D. Chaum. — Berlin, Heidelberg : Springer Berlin Heidelberg, 1985. - P. 10-18.

[42] Koblitz, N. Elliptic curve cryptosystems / N. Koblitz // Mathematics of Computation. - 1987. - Vol. 48. - P. 203-209.

[43] Niederreiter, H. Knapsack Type Cryptosystems and Algebraic Coding Theory / H. Niederreiter // Problems of Control and Information Theory.

_ 1986. _ v0i. 15.

[44] Berlekamp, E. R. On the inherent intractability of certain coding problems / E. R. Berlekamp, R. J. McEliece, H. C. A. van Tilborg // IEEE Trans. Inform. Theory. - 1978. - Vol. IT-24. - P. 384-386.

[45] NTRU [Электронный ресурс]. — URL: littps: ntru.org f ntru-20190330.pdf (дата обращения 01.07.2022).

[46] SABER [Электронный ресурс]. — URL: https://esat.kuleuven.be/cosic/pqcrypto/saber (дата обращения 01.07.2022).

[47] Ajtai, М. The Shortest Vector Problem in L2 is NP-Hard for Randomized Reductions (Extended Abstract) / M. Ajtai // Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. — STOC '98. — New York, NY, USA : Association for Computing Machinery, 1998. - P. 10-19.

[48] Risks of lattice KEMs [Электронный ресурс]. — URL: https://ntruprime.cr.yp.to/warnings.html (дата обращения 01.07.2022).

[49] Rostovtsev, A. Public-Key Cryptosystem Based on Isogenics / A. Rostovtsev, A. Stolbunov // IACR Eprint archive. — 2006.

[50] Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process [Электронный ресурс]. — URL: https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf (дата обращения 06.07.2022).

[51] Patterson, N. J. The algebraic decoding of Goppa codes / N. J. Patterson // IEEE Trans. Inf. Theory. - 1975. - Vol. 21.

- P. 203-207.

[52] Деундяк, В. Методы помехоустойчивой защиты данных / В. Деундяк.

- Ростов-на-Дону : Изд-во Южного федерального ун-та, 2015.

[53] Error correction for algebraic block codes., 1986. — U.S. Patent 4,633,470, issued Dec. 30.

[54] Сидельников, В. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона / В. Сидельников, С. Шестаков // Дискрет. матем. — 1992. — Т. 4. — С. 55-63.

[55] Сидельников, В. Открытое шифрование на основе двоичных кодов Рида-Маллера / В. Сидельников // Дискрет, матем. — 1994. — Т. 6. _ с. 3-20.

[56] Minder, L. Cryptanalysis of the Sidelnikov cryptosystem / L. Minder, A. Shokrollahi // Advances in cryptology^EUROCRYPT 2007. -Springer, Berlin, 2007. — Vol. 4515 of Lecture Notes in Comput. Sci.

- P. 347-360.

[57] Berger, T. P. How to mask the structure of codes for a cryptographic use / T. P. Berger, P. Loidreau // Des. Codes Cryptogr. — 2005. — Vol. 35.

- P. 63-79.

[58] Wieschebrink, C. Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes / C. Wieschebrink / / Post-quantum

cryptography. — Springer, Berlin, 2010. — Vol. 6061 of Lecture Notes in Comput. Sci. — P. 61-72.

[59] Габидулин, Э. Теория кодов с максимальным ранговым расстоянием / Э. Габидулин // Пробл. передачи информ. — 1985. — Т. 21. — С. 3 16.

[60] Gabidulin, Е. М. Ideals over a noncommutative ring and their application in cryptology / E. M. Gabidulin, A. V. Paramonov, О. V. Tretjakov // Advances in cryptology^EUROCRYPT '91 (Brighton, 1991). — Springer, Berlin, 1991. - Vol. 547 of Lecture Notes in Comput. Sci. - P. 482-489.

[61] Overbeck, R. Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes / R. Overbeck // Journal of Cryptology. — 2008. — Vol. 21. - P. 280-301.

[62] Деундяк, В. Декодирование тензорного произведения MLD-кодов и приложения к кодовым криптосистемам / В. Деундяк, Ю. Косолапов, Е. Лелюк // Модел. и анализ информ. систем. — 2017. — Т. 24. — С. 239-252.

[63] Couvreur, A. Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes / A. Couvreur, I. Marquez-Corbella, R. Pellikaan // IEEE Transactions on Information Theory. — 2017. — Vol. 63. - P. 5404-5418.

[64] Couvreur, A. Cryptanalysis of Public-Key Cryptosystems That Use Subcodes of Algebraic Geometry Codes / A. Couvreur, I. Marquez-Corbella, R. Pellikaan // Coding Theory and Applications / ed. by R. Pinto, P. Rocha Malonek, P. Vettori. — Springer International Publishing, 2015. - P. 133-140.

[65] Couvreur, A. Polynomial Time Attack on Wild McEliece Over Quadratic Extensions / A. Couvreur, A. Otmani, J.-P. Tillich // IEEE Transactions on Information Theory. - 2017. - Vol. 63. - P. 404-427.

[66] Couvreur, A. Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes / A. Couvreur, P. Gaborit, V. Gauthier-Umana, A. Otmani, J. Tillich // Designs, Codes, and Cryptography. —

2014. - Vol. 73. - P. 641-666.

[67] Cascudo, I. Squares of Random Linear Codes / I. Cascudo, R. Cramer, D. Mirandola, G. Zémor // IEEE Transactions on Information Theory. —

2015. - Vol. 61. - P. 1159-1173.

[68] Yardi, A. D. Detecting linear block codes in noise using the GLRT / A. D. Yardi, S. Vijayakumaran // 2013 IEEE International Conference on Communications (ICC). - 2013. - P. 4895-4899.

[69] Chabot, С. Recognition of a code in a noisy environment / C. Chabot // 2007 IEEE International Symposium on Information Theory. — 2007. — P. 2211-2215.

[70] Wyner, A. D. The wire-tap channel / A. D. Wyner // The Bell System Technical Journal. - 1975. - Vol. 54. - P. 1355-1387.

[71] Ширяев, А. Вероятность / А. Ширяев. — МЦНМО, 2017. — В 2-х кн.

[72] Т., В. Failure of the McEliece public-key cryptosystem under message-resend and relatedmessage attack / В. T. // 17th Annual Intern. Cryptology Conf., Santa Barbara, California, USA, LNCS. — 1997. — Vol. 1294. - P. 213-220.

[73] Canto Torres, R. Analysis of information set decoding for a sub-linear error weight / R. Canto Torres, N. Sendrier // Post-quantum cryptography. —

Springer, [Cham], 2016. — Vol. 9606 of Lecture Notes in Comput. Sci. — P. 144 161.

[74] Bernstein, D. Grover vs. McEliece / D. Bernstein // Post-Quantum Cryptography (3rd International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010) / edited byN. Sendrier. — Lecture Notes in Computer Science. — Germany : Springer, 2010. — P. 73-80.

[75] Grover, L. K. A Fast Quantum Mechanical Algorithm for Database Search / L. K. Grover // Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. — STOC '96. — New York, NY, USA : Association for Computing Machinery, 1996. — P. 212-219.

[76] Kachigar, G. Quantum Information Set Decoding Algorithms / G. Kachigar, J.-P. Tillich // Post-Quantum Cryptography / ed. by T. Lange, T. Takagi. — Cham : Springer International Publishing, 2017. - P. 69-89.

[77] Report on Post-Quantum Cryptography [Электронный ресурс]. — URL: https://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf (дата обращения 01.07.2022).

[78] Bellare, M. Relations Among Notions of Security for Public-Key Encryption Schemes. / M. Bellare, A. Desai, D. Pointcheval, P. Rogaway // Advances in Cryptology - CRYPTO '98. CRYPTO, L.XCS. - 1998. - Vol. 1462. - P. 26-45.

[79] Kobara, K. On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC / K. Kobara, H. Imai // IEEE Trans. Inform. Theory. - 2003. - Vol. 49. - P. 3160-3168.

[80] Bleichenbacher, D. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 / D. Bleichenbacher //

Advances in Cryptology — CRYPTO '98 / ed. by H. Krawczyk. — Berlin, Heidelberg : Springer Berlin Heidelberg, 1998. — P. 1-12.

[81] Green, M. A Unified Approach to Idealized Model Separations via Indistinguishability Obfuscation / M. Green, J. Katz, A. Malozemoff, H.-S. Zhou. - Vol. 9841. - 2016.^08. - P. 587-603.

[82] Canetti, R. The Random Oracle Methodology, Revisited / R. Canetti, O. Goldreich, S. Halevi // J. ACM. - 2004. - Vol. 51. - P. 557-594.

[83] Lamport, L. Constructing Digital Signatures from a One Way Function : L. Lamport. — This paper was published by IEEE in the Proceedings of HICSS-43 in January, 2010. 1979. - October.

[84] Kobara, K. Semantically secure McEliece public-key (Typtosysteins conversions for McEliece PKC / K. Kobara, H. Imai // Public key cryptography (Cheju Island, 2001). — Springer, Berlin, 2001. — Vol. 1992 of Lecture Notes in Comput. Sci. — P. 19-35.

[85] Preetha Mathew, K. An Efficient IND-CCA2 Secure Variant of the Niederreiter Encryption Scheme in the Standard Model / K. Preetha Mathew, S. Vasant, S. Venkatesan, C. Pandu Rangan // Information Security and Privacy / ed. by W. Susilo, Y. Mu, J. Seberry. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. — P. 166-179.

[86] Cramer, R. Secure Multiparty Computation and Secret Sharing / R. Cramer, I. B. Damgard, J. B. Nielsen. — Cambridge University Press, 2015.

[87] Brent, R. Random Krylov Spaces over Finite Fields / R. Brent, S. Gao, A. Lauder // SIAM Journal on Discrete Mathematics. — 2002. — Vol. 16. _ No 2. - P. 276-287.

[88] Lenstra, А. К. Selecting Cryptographic Key Sizes / A. K. Lenstra, E. R. Verheul // Public Key Cryptography / ed. by H. Imai, Y. Zheng.

— Berlin, Heidelberg : Springer Berlin Heidelberg, 2000. — P. 446-465.

[89] Bernstein, D.J. McBits: Fast Constant-Time Code-Based Cryptography / D. J. Bernstein, T. Chou, P. Schwabe // Cryptographic Hardware and Embedded Systems - CHES 2013 / ed. by G. Bertoni, J.-S. Coron. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2013. — P. 250-272.

[90] SPHINCS+ [Электронный ресурс]. — URL: https://sphincs.org/ (дата обращения 01.07.2022).

[91] Stern, J. A new identification scheme based on syndrome decoding / J. Stern // Advances in Cryptology — CRYPTO' 93 / ed. by D. R. Stinson.

— Berlin, Heidelberg : Springer Berlin Heidelberg, 1994. — P. 13-21.

[92] Gaborit, P. Lightweight code-based identification and signature / P. Gaborit, M. Girault. - 2007. 07. - P. 191 - 195.

[93] Vysotskaya, V. The security of the code-based signature scheme based on the Stern identification protocol / V. Vysotskaya, I. Chizhov // Cryptology ePrint Archive, Report 2021/1075. - 2021.

[94] Falcon-512 [Электронный ресурс]. — URL: https://falcon-sign.info/ (дата обращения 01.07.2022).

[95] Dilithium [Электронный ресурс]. — URL: https://pq-crystals.org/dilithium/resources.shtml (дата обращения 01.07.2022).

[96] Rainbow [Электронный ресурс]. — URL: https://www.pqcrainbow.org/ (дата обращения 01.07.2022).

[97] Hoffstein, J. Choosing parameters for NTRUEncrypt / J. Hoffstein, J. Pipher, J. Schanck, J. Silverman, W. Whyte, Z. Zhang. — 2017. — 02. - P. 3-18.

[98] Bernstein, D. J. The SPHINCS+ Signature Framework / D. J. Bernstein, A. Hülsing, S. Kolbl, R. Niederhagen, J. Rijneveld, P. Schwabe // Cryptology ePrint Archive, Report 2019/1086. - 2019.

[99] Bernstein, D. J. Attacking and Defending the McEliece Cryptosystem / D. J. Bernstein, T. Lange, C. Peters // Post-Quantum Cryptography / ed. by J. Buchmann, J. Ding. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2008. - P. 31-46.

[100] Kurosawa, K. Multi-recipient Public-Key Encryption with Shortened Ciphertext / K. Kurosawa // Public Key Cryptography / ed. by D. Naccache, P. Paillier. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2002. - P. 48-63.

[101] Bellare, M. Randomness Re-use in Multi-recipient Encryption Schemeas / M. Bellare, A. Boldyreva, J. Staddon // Public Key Cryptography — PKC 2003 / ed. by Y. G. Desmedt. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2002. - P. 85-99.

[102] Rafaeli, S. A Survey of Key Management for Secure Group Communication / S. Rafaeli, D. Hutchison // ACM Comput. Surv. — 2003. - Vol. 35. - P. 309-329.

[103] Sun, Y. Analysis and Protection of Dynamic Membership Information for Group Key Distribution Schemes / Y. Sun, K. J. R. Liu // Information Forensics and Security, IEEE Transactions on. — 2007.^07. — Vol. 2. - P. 213 - 226.

[104] Shi, R.-h. A novel one-to-many and many-to-one asymmetric encryption model and its algorithms / R.-h. Shi, H. Zhong, J. Cui, S. Zhang // Security and Communication Networks. — 2015.^07. — Vol. 8.

[105] Kumar, S. JEDI: Many-to-Many End-to-End Encryption and Key Delegation for IoT / S. Kumar, Y. Hu, M. P. Andersen, R. A. Popa, D. E. Culler // USENIX Security Symposium. - 2019.

[106] Moriarty, K. PKCS #1: RSA Cryptography Specifications Version 2.2 / K. Moriarty, B. Kaliski, J. Jonsson, A. Rusch // Request for Comments. _ 2016. - P. 1-78.

[107] IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices // IEEE Std 1363.1-2008. - 2009. _ p. 1-81.

[108] Bellare, M. Optimal asymmetric encryption / M. Bellare, P. Rogaway // Advances in Cryptology - EUROCRYPT'94 / ed. by A. De Santis. -Berlin, Heidelberg : Springer Berlin Heidelberg, 1995. — P. 92-111.

[109] Massolino, P. M. C. Optimized and Scalable Co-Processor for McEliece with Binary Goppa Codes / P. M. C. Massolino, P. S. L. M. Barreto, W. V. Ruggiero // ACM Trans. Embed. Comput. Syst. — 2015. — Vol. 14. - 32 P.

[110] Blum, T. High-radix Montgomery modular exponentiation on reconfigurable hardware / T. Blum, C. Paar // IEEE Transactions on Computers. - 2001. - Vol. 50. - P. 759-764.

[111] Tang, S. Modular exponentiation using parallel multipliers / S. Tang, K. Tsui, P. Leong // Proceedings. 2003 IEEE International Conference on Field-Programmable Technology (FPT) (IEEE Cat. No.03EX798). -2003. - P. 52-59.

[112] Jiang, N. Quotient Pipelined Very High Radix Scalable Montgomery Multipliers / N. Jiang, D. Harris // 2006 Fortieth Asilomar Conference on Signals, Systems and Computers. — 2006. — P. 1673-1677.

[113] Miyamoto, A. Systematic Design of RSA Processors Based on High-Radix Montgomery Multipliers / A. Miyamoto, N. Homma, T. Aoki, A. Satoh // Very Large Scale Integration (VLSI) Systems, IEEE Transactions on. — 2011. _ Vol. 19. - P. 1136-1146.

[114] Wu, T. Fast, Compact and Symmetric Modular Exponentiation Architecture by Common-Multiplicand Montgomery Modular Multiplications / T. Wu, S. Li, L. Liu // Integr. VLSI J. - 2013. _ Vol. 46. - P. 323-332.

[115] Wu, T. Fast RSA decryption through high-radix scalable Montgomery modular multipliers / T. Wu, S. Li, L. Liu // Science China Information Sciences. - 2015.^06. - Vol. 58.

[116] Bailey, D. V. NTRU in Constrained Devices / D. V. Bailey, D. Coffin, A. Elbirt, J. H. Silverman, A. D. Woodbury // Cryptographic Hardware and Embedded Systems — CHES 2001 / ed. by Q. K. Kog, D. Naccache, C. Paar. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2001. — P. 262-272.

[117] Kamal, A. A. An FPGA implementation of the NTRUEncrypt cryptosystem / A. A. Kamal, A. M. Youssef // 2009 International Conference on Microelectronics - ICM. - 2009. - P. 209-212.

[118] Liu, B. Efficient architecture and implementation for NTRUEncrypt system / B. Liu, H. Wu // 2015 IEEE 58th International Midwest Symposium on Circuits and Systems (MWSCAS). — 2015. — P. 14.

[119] Fritzmann, T. Efficient Hardware/Software Co-design for NTRU / T. Fritzmann, T. Schamberger, C. Frisch, K. Braun, G. Maringer, J. Sepülveda // VLSI-SoC: Design and Engineering of Electronics Systems Based on New Computing Paradigms / ed. by N. Bombieri, G. Pravadelli, M. Fujita, T. Austin, R. Reis. — Cham : Springer International Publishing, 2019. - P. 257-280.

[120] Farahmand, F. A High-Speed Constant-Time Hardware Implementation of NTRUEncrypt SVES / F. Farahmand, M. U. Sharif, K. Briggs, K. Gaj // 2018 International Conference on Field-Programmable Technology (FPT). - 2018. - P. 190-197.

[121] Amiet, D. FPGA-based SPHINCS+ Implementations: Mind the Glitch / D. Amiet, L. Leuenberger, A. Curiger, P. Zbinden // 2020 23rd Euromicro Conference on Digital System Design (DSD). - 2020. - P. 229-237.

[122] Sundal, M. Efficient FPGA Implementation of the SHA-3 Hash Function / M. Sundal, R. Chaves // 2017 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). - 2017. - P. 86-91.

[123] SP 800-22 Rev. la. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications : L. E. Bassham, A. L. Rukhin, J. Soto, J. R. Nechvatal, M. E. Smid, E. B. Barker et al. — Gaithersburg, MD, USA : National Institute of Standards and Technology, 2010.