Round5 — это постквантовая система шифрования с открытым ключом, основанная на общей задаче обучения с округлением (General Learning with Rounding (GLWR))[1]. Данная система является альтернативой для алгоритмов RSA и эллиптических кривых и предназначена для защиты от атак квантовыми компьютерами[2]. Round5 состоит из алгоритмов, предназначенных для реализаций механизма инкапсуляции ключей (key encapsulation mechanism (KEM)) и схемы шифрования с открытым ключом (public-key encryption (PKE)). Данные алгоритмы попадают под категорию криптография на решётках.
Round5 представляет собой слияние двух систем: Round2[3], основанная также на задаче GLWR, и HILA5[4], имеющая код исправления ошибок[1].
Введение
Если крупные квантовые компьютеры когда-либо будут построены, то они смогут взломать многие криптосистемы с открытым ключом, используемые в настоящее время. Это серьёзно подорвало бы конфиденциальность и целостность цифровых коммуникаций в Интернете. Целью пост-квантовой криптографии является разработка криптографических систем, которые защищены как от квантовых, так и от классических компьютеров и могут взаимодействовать с существующими протоколами связи и сетями[5].
Обозначения
- Пусть
— целое положительное число, тогда за
обозначим набор чисел
. Для набора
через
обозначим случайный и равновероятный выбор
из
. - Пусть
— простое число.
— циклотомический полином равный
. Многочлен
равен ![{\displaystyle x^{n+1}-1=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55b4dd2d3001b9ad0633fac6a2c5376b6efdff68)
![{\displaystyle {\mathit {\Phi }}_{n+1}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2723eee33eb58936c8730b5623fee0b13510f500)
. - Кольцо многочленов
обозначим
.
— это набор многочленов таких, что их степень меньше
и их коэффициенты лежат в
, а
— это множество таких векторов размерности
(
— положительное целое число), что каждая компонента любого вектора принадлежит
.
называется троичным, если все его коэффициенты равны
или
. - Для любого элемента
вес Хемминга определяется как число ненулевых коэффициентов.
определяется как множество троичных полиномов степени меньше
с весом Хемминга
. В Round5 такие многочлены к тому же ещё являются сбалансированными и разреженными, то есть имеют ровно
коэффициентов равных
и столько же равных
(сбалансированные), и при этом
принимает фиксированное значение (разреженные).
— это множество всех таких наборов длины
, состоящие из нулей и единиц. - Для рационального числа
обозначим:
— округление вниз до целого, а
— округление до ближайшего целого. Взятие остатка от деления обозначим как
, то есть
[1][2].
Задача GLWR
Пусть
— положительные целые числа, такие что
и
равняется
или
.
является распределением вероятности по
. Выбор элемента
из
в соответствии с распределением
обозначим как
[1].
Версия поиска
Имеется
примеров формы
, где
и
фиксирован, требуется найти
[1].
Версия решения
Сложность данной версии заключается в различении равномерного распределения по
и распределения
, где
,
фиксирован и
[1].
Виды задачи GLWR
Ключевой особенностью Round5 является то, что её можно реализовать на основе таких задач как обучение с округлением (Learning with Rounding (LWR)), так и кольцевое обучение с округлением (Ring Learning with Rounding (RLWR)) единым способом, что приводит к уменьшению затрат на анализ и обслуживание кода[1].
Каждая из этих задач получается из задачи GLWR. Чтобы поставить задачу LWR, в GLWR нужно
принять равной
, а RLWR —
принять равной
[1].
Алгоритмы на основе LWR требуются в средах, где производительность не так важна по сравнению с безопасностью[1].
Напротив, по сравнению с LWR, в алгоритмах на основе RLWR вычисления более просты и эффективны. К тому же эти алгоритмы менее требовательны к полосе пропускания, поэтому они лучше подходят для тех сред, где накладываются более строгие требования к каналам передачи информации, например, там, где могут возникнуть трудности с фрагментацией сообщений или MTU слишком мал[1].
Основа Round5
Схема шифрования
Основой Round5 является схема шифрования r5_cpa_pke, надёжная в смысле IND-CPA. r5_cpa_pke похожа на схему шифрования Эль-Гамаля с шумом. Здесь приведены алгоритмы для задачи GLWR. Для того, чтобы получить алгоритмы для задач LWR или RLWR, нужно выбрать
равной
или
соответственно[2][1].
Параметры схемы шифрования r5_cpa_pke:
— целые положительные числа,
— параметр безопасности (длина сообщения в битах),
— многочлен, коэффициенты которого являются сообщением и равны
или
(
).
— число столбцов в секретных матрицах. Модули
являются степенями двойки, так что
делит
,
делит
и
делит
. Требуется, чтобы
и
.
— вес Хемминга многочленов, являющихся секретными.
— многочлен
или
.
— это матрица, вся заполненная
[1][2].
Алгоритм создания ключа
Algorithm 1: r5_cpa_pke_keygen() |
1. |
2. |
3. |
4. |
5. |
6. |
7. return |
равновероятно выбирается из множества
. - На основе
вычисляется открытая квадратная матрица
размера
, элементы которой принадлежат множеству
(в случае RLWR (
) это один многочлен, если LWR (
) — матрица из элементов, лежащих в
). Для этого применяется функция
, использующая детерминированный генератор случайных битов[6] и перестановки, определяемые параметром
. - Как и
, секретный ключ
выбирается случайно из
. - На основе
вычисляется секретная матрица
размера
, элементы которой принадлежат множеству
(в случае RLWR (
) это вектор, состоящий из троичных многочленов, если LWR (
) — матрица, состоящая из
и
). Для этого используется функция
, использующая также детерминированный генератор случайных битов. - Вычисляется матрица
размера
, состоящая из элементов
, следующим образом: - Элементы матрицы, равной произведению
на
, вычисляются по модулю
. Затем к каждому элементу прибавляется постоянная округления
. - Каждый элемент умножается на дробь
. - Коэффициенты всех многочленов полученной матрицы округляются в меньшую сторону до ближайшего целого и берутся по модулю
.
- Открытый ключ представляет собой набор из
и
[1][2].
Алгоритм шифрования
Algorithm 2: r5_cpa_pke_encrypt |
1. |
2. |
3. |
4. |
5. |
6. |
7. return |
- Так же, как и при вычислении ключей, находится матрица
. - Вводится элемент множества
—
. На его основе при помощи функции
вычисляется секретная матрица
размера
, элементы которой принадлежат множеству
(в случае RLWR (
) это вектор, состоящий из троичных многочленов, если LWR (
) — матрица, состоящая из
и
). - Используя матрицы
,
и постоянную округления
(
), вычисляется матрица
аналогично как в алгоритме создания ключей. - Транспонированная
есть первая компонента шифротекста. - Вторая компонента шифротекста — вектор
, элементы которого лежат в
. Поскольку не все компоненты
необходимы для шифрования
-битового сообщения
, используется функция
. - Если
, то
— это многочлен и
принимает его на вход, а на выходе выдаёт набор всех коэффициентов, соответствующих членам со степенью меньших
:
. - Если
, то
— это матрица
, состоящая из целых чисел и
выдаёт первые
чисел этой матрицы:
, где
. - Получаем, что
содержит только
компонент.
- Таким образом, получаем шифротекст
[1][2].
Использование
делает шифрование и дешифрование более эффективными, поскольку в зашифрованном тексте необходимо вычислять только коэффициенты
вместо всех
[1][2].
Так же для уменьшение вероятности ошибок применяются функции кодирования
при шифровании и декодирования
при дешифровании . Функция
преобразует многочлен
в набор двоичных коэффициентов размера
. Затем этот набор складывается с набором ошибок
, где каждый
равен
или
, причём количество единиц в наборе ошибок не должно быть больше чем
для однозначного декодирования[1][2].
[1][2].
Алгоритм дешифрования
Algorithm 2: r5_cpa_pke_decrypt |
1. |
2. |
3. |
4. |
5. |
6. return |
- Вычисляется вектор
. - На основе закрытого ключа находится секретная матрица
такая же, как в алгоритме создания ключей. - Транспонированием
находится матрица
, вычисленная в алгоритме шифрования. - Происходит дешифрование сообщения.
,
. - Исправляются ошибки. Таким образом получаем исходное сообщение
[1][2].
Достоинства Round5
Округление позволяет избежать дополнительного создания случайных величин — шума. Генерация шума может быть уязвимостью для атак по побочным каналам. Таким образом, отсутствие необходимости создания шума является дополнительным преимуществом[1].
Так как секретные ключи в Round5 являются разреженными, троичными и сбалансированными, снижается вероятность ошибок при расшифровки и ускоряются вычисления. Последнему факту также помогает то, что ненулевые коэффициенты многочленов равны либо +1, либо −1, что подразумевает, что умножения могут быть выполнены с использованием только сложений и вычитаний[2].
Благодаря тому, что модули
являются степенями двойки, упрощается реализация функции округления, поскольку её можно реализовать, отбрасывая младшие биты. Аналогично, модульные вычисления могут быть реализованы путём отбрасывания старших битов[1].
Возможное применение
Спектр применения системы Round5 широк. Она может быть использована как в сфере интернет вещей, так и для систем с высоким уровнем секретности. Это достигается тем, что для неё можно легко и точно выбрать параметры, например
,
,
и
[2].
Примечания
- ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Hayo Baan, Sauvik Bhattacharya, Scott Fluhrer, Oscar Garcia-Morchon, ThijsLaarhoven, Rachel Player, Ronald Rietman, Markku-Juhani O. Saarinen, LudoTolhuizen, Jos ́e Luis Torre-Arce, and Zhenfei Zhang. Round5:KEM and PKE based on (Ring) Learning with Rounding (англ.) // round5.org : article. — 2019. — 28 March. — P. 153. Архивировано 5 декабря 2019 года.
- ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Hayo Baan, Sauvik Bhattacharya, Scott Fluhrer, Oscar Garcia-Morchon, Thijs Laarhoven, Ronald Rietman, Markku-Juhani O. Saarinen, Ludo Tolhuizen, and Zhenfei Zhang. [https://eprint.iacr.org/2019/090.pdf Round5: Compact and Fast Post-Quantum Public-Key Encryption] (англ.) // https://round5.org/ : article. — 2019. — P. 20. Архивировано 7 декабря 2019 года.
- ↑ Hayo Baan, Sauvik Bhattacharya, Oscar Garcia-Morchon, Ronald Rietman, Ludo Tolhuizen. Round2: KEM and PKE based on GLWR. — 2017. — № 1183. Архивировано 6 декабря 2019 года.
- ↑ Markku-Juhani O. Saarinen, 2017.
- ↑ Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta. Report on Post-Quantum Cryptography. — National Institute of Standards and Technology, 2016-04. Архивировано 16 октября 2023 года.
- ↑ Elaine B. Barker, John M. Kelsey. Recommendation for Random Number Generation Using Deterministic Random Bit Generators. — National Institute of Standards and Technology, 2015-06. — doi:10.6028/nist.sp.800-90ar1.
Литература
- Markku-Juhani O. Saarinen. HILA5: On Reliability, Reconciliation, and Error Correction for Ring-LWE Encryption (англ.). — Springer, Cham, 2017. — 23 December. — doi:10.1007/978-3-319-72565-9_10.
- Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta. Report on Post-Quantum Cryptography (англ.). — U.S. Department of Commerce, 2016. — April. — doi:10.6028/NIST.IR .8105.
Ссылки
- Официальный сайт (англ.)
- Механизм инкапсуляции ключей (англ.)