Round5

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].

Обозначения

Пусть $a$ — целое положительное число, тогда за $\mathbb {Z} _{a}$ обозначим набор чисел $\{0,1,\cdots ,a-1\}$ . Для набора $A$ через $a{\xleftarrow[{}]{\$}}A$ обозначим случайный и равновероятный выбор $a$ из $A$ .
Пусть $n+1$ — простое число. ${\mathit {\Phi }}_{n+1}(x)$ — циклотомический полином равный $x^{n}+x^{n-1}+\cdots +x+1$ . Многочлен $N_{n+1}(x)$ равен $x^{n+1}-1=$ ${\mathit {\Phi }}_{n+1}(x)$ $(x-1)$ .
Кольцо многочленов $\mathbb {Z} [x]/{\mathit {\Phi }}_{n+1}(x)$ обозначим ${\mathcal {R}}_{n}$ . ${\mathcal {R}}_{n,a}$ — это набор многочленов таких, что их степень меньше $n$ и их коэффициенты лежат в $\mathbb {Z} _{a}$ , а ${\mathcal {R}}_{n,a}^{b}$ — это множество таких векторов размерности $b$ ( $b$ — положительное целое число), что каждая компонента любого вектора принадлежит ${\mathcal {R}}_{n,a}$ .
${\mathcal {R}}_{n}$ называется троичным, если все его коэффициенты равны $0,1$ или $-1$ .
Для любого элемента $\upsilon \in {\mathcal {R}}_{n}$ вес Хемминга определяется как число ненулевых коэффициентов. ${\mathcal {H}}_{n}(h)$ определяется как множество троичных полиномов степени меньше $n$ с весом Хемминга $h$ . В Round5 такие многочлены к тому же ещё являются сбалансированными и разреженными, то есть имеют ровно $h/2$ коэффициентов равных $+1$ и столько же равных $-1$ (сбалансированные), и при этом $h$ принимает фиксированное значение (разреженные).
$\{0,1\}^{k}$ — это множество всех таких наборов длины $k$ , состоящие из нулей и единиц.
Для рационального числа $x$ обозначим: $\lfloor x\rfloor$ — округление вниз до целого, а $\lfloor x\rceil$ — округление до ближайшего целого. Взятие остатка от деления обозначим как $\langle x\rangle _{a}$ , то есть $\langle x\rangle _{a}=x{\bmod {a}}$ ^[1]^[2].

Задача GLWR

Пусть $d,n,p,q$ — положительные целые числа, такие что $q\geq p\geq 2$ и $n$ равняется $1$ или $d$ . $D_{s}$ является распределением вероятности по ${\mathcal {R}}_{n,q}^{d/n}$ . Выбор элемента $\mathbf {s}$ из ${\mathcal {R}}_{n,q}^{d/n}$ в соответствии с распределением $D_{s}$ обозначим как $\mathbf {s} \leftarrow D_{s}$ ^[1].

Версия поиска

Имеется $m$ примеров формы $\left\langle \left\lfloor {\frac {p}{q}}\langle \mathbf {a} _{i}^{T}\mathbf {s} \rangle _{{\mathit {\Phi }}_{n+1}(x)}\right\rfloor \right\rangle _{p}$ , где $\mathbf {a} _{i}\in {\mathcal {R}}_{n,q}^{d/n}$ и $\mathbf {s} \leftarrow D_{s}$ фиксирован, требуется найти $\mathbf {s}$ ^[1].

Версия решения

Сложность данной версии заключается в различении равномерного распределения по ${\mathcal {R}}_{n,q}^{d/n}\times {\mathcal {R}}_{n,p}$ и распределения $(\mathbf {a} _{i},b_{i})$ , где $\mathbf {a} _{i}{\xleftarrow[{}]{\$}}{\mathcal {R}}_{n,q}^{d/n}$ , $\mathbf {s} \leftarrow D_{s}$ фиксирован и $b_{i}=\left\langle \left\lfloor {\frac {p}{q}}\langle \mathbf {a} _{i}^{T}\mathbf {s} \rangle _{{\mathit {\Phi }}_{n+1}(x)}\right\rfloor \right\rangle _{p}$ ^[1].

Виды задачи GLWR

Ключевой особенностью Round5 является то, что её можно реализовать на основе таких задач как обучение с округлением (Learning with Rounding (LWR)), так и кольцевое обучение с округлением (Ring Learning with Rounding (RLWR)) единым способом, что приводит к уменьшению затрат на анализ и обслуживание кода^[1].

Каждая из этих задач получается из задачи GLWR. Чтобы поставить задачу LWR, в GLWR нужно $n$ принять равной $1$ , а RLWR — $n$ принять равной $d$ ^[1].

Алгоритмы на основе LWR требуются в средах, где производительность не так важна по сравнению с безопасностью^[1].

Напротив, по сравнению с LWR, в алгоритмах на основе RLWR вычисления более просты и эффективны. К тому же эти алгоритмы менее требовательны к полосе пропускания, поэтому они лучше подходят для тех сред, где накладываются более строгие требования к каналам передачи информации, например, там, где могут возникнуть трудности с фрагментацией сообщений или MTU слишком мал^[1].

Основа Round5

Схема шифрования

Основой Round5 является схема шифрования r5_cpa_pke, надёжная в смысле IND-CPA. r5_cpa_pke похожа на схему шифрования Эль-Гамаля с шумом. Здесь приведены алгоритмы для задачи GLWR. Для того, чтобы получить алгоритмы для задач LWR или RLWR, нужно выбрать $n$ равной $1$ или $d$ соответственно^[2]^[1].

Параметры схемы шифрования r5_cpa_pke: $n,d,h,p,q,t,b,{\bar {n}},{\bar {m}},\mu ,f,\tau$ — целые положительные числа, $k$ — параметр безопасности (длина сообщения в битах), $m(x)$ — многочлен, коэффициенты которого являются сообщением и равны $0$ или $1$ ( $m(x)=m_{0}+m_{1}x+\cdots +m_{k-1}x^{k-1}$ ). ${\bar {n}},{\bar {m}}$ — число столбцов в секретных матрицах. Модули $p,q,t,b$ являются степенями двойки, так что $b$ делит $t$ , $t$ делит $p$ и $p$ делит $q$ . Требуется, чтобы $\mu \leq n\cdot {\bar {n}}\cdot {\bar {m}}$ и $\mu \geq k\cdot \log _{2}(b)$ . $h$ — вес Хемминга многочленов, являющихся секретными. $\xi (x)$ — многочлен ${\mathit {\Phi }}_{n+1}(x)$ или $N_{n+1}(x)$ . ${\boldsymbol {J}}$ — это матрица, вся заполненная $1$ ^[1]^[2].

Алгоритм создания ключа

Algorithm 1: r5_cpa_pke_keygen()
1. $\sigma {\xleftarrow[{}]{\$}}\{0,1\}^{k}$
2. ${\boldsymbol {A}}=f_{d,n}^{(\tau )}(\sigma )$
3. $sk{\xleftarrow[{}]{\$}}\{0,1\}^{k}$
4. ${\boldsymbol {S}}=f_{S}(sk)$
5. ${\boldsymbol {B}}=\left\langle \left\lfloor {\frac {p}{q}}(\langle {\boldsymbol {A}}{\boldsymbol {S}}\rangle _{{\mathit {\Phi }}_{n+1}(x)}+h_{1}{\boldsymbol {J}})\right\rfloor \right\rangle _{p}$
6. $pk=(\sigma ,{\boldsymbol {B}})$
7. return $(pk,sk)$

$\sigma$ равновероятно выбирается из множества $\{0,1\}^{k}$ .
На основе $\sigma$ вычисляется открытая квадратная матрица ${\boldsymbol {A}}$ размера $d/n\times d/n$ , элементы которой принадлежат множеству ${\mathcal {R}}_{n,q}$ (в случае RLWR ( $n=d$ ) это один многочлен, если LWR ( $n=1$ ) — матрица из элементов, лежащих в $\mathbb {Z} _{q}$ ). Для этого применяется функция $f_{d,n}^{(\tau )}(\sigma )$ , использующая детерминированный генератор случайных битов^[6] и перестановки, определяемые параметром $\tau$ .
Как и $\sigma$ , секретный ключ $sk$ выбирается случайно из $\{0,1\}^{k}$ .
На основе $sk$ вычисляется секретная матрица ${\boldsymbol {S}}$ размера $d/n\times {\bar {n}}$ , элементы которой принадлежат множеству ${\mathcal {H}}_{n}(h)$ (в случае RLWR ( $n=d$ ) это вектор, состоящий из троичных многочленов, если LWR ( $n=1$ ) — матрица, состоящая из $0,1$ и $-1$ ). Для этого используется функция $f_{S}(sk)$ , использующая также детерминированный генератор случайных битов.
Вычисляется матрица ${\boldsymbol {B}}$ размера $d/n\times {\bar {n}}$ , состоящая из элементов ${\mathcal {R}}_{n,p}$ , следующим образом:
1. Элементы матрицы, равной произведению ${\boldsymbol {A}}$ на ${\boldsymbol {S}}$ , вычисляются по модулю ${\mathit {\Phi }}_{n+1}(x)$ . Затем к каждому элементу прибавляется постоянная округления $h_{1}={\frac {q}{2p}}$ .
2. Каждый элемент умножается на дробь ${\frac {p}{q}}$ .
3. Коэффициенты всех многочленов полученной матрицы округляются в меньшую сторону до ближайшего целого и берутся по модулю $p$ .
Открытый ключ представляет собой набор из $\sigma$ и ${\boldsymbol {B}}$ ^[1]^[2].

Алгоритм шифрования

Algorithm 2: r5_cpa_pke_encrypt $(pk,m)$
1. ${\boldsymbol {A}}=f_{d,n}^{(\tau )}(\sigma )$
2. ${\boldsymbol {R}}=f_{R}(\rho )$
3. ${\boldsymbol {U}}=\left\langle \left\lfloor {\frac {p}{q}}(\langle {\boldsymbol {A}}^{T}{\boldsymbol {R}}\rangle _{{\mathit {\Phi }}_{n+1}(x)}+h_{2}{\boldsymbol {J}})\right\rfloor \right\rangle _{p}$
4. ${\tilde {\boldsymbol {U}}}={\boldsymbol {U}}^{T}$
5. ${\boldsymbol {\upsilon }}=\left\langle \left\lfloor {\frac {t}{p}}({\text{Sample}}_{\mu }\langle {\boldsymbol {B}}^{T}{\boldsymbol {R}}\rangle _{\xi (x)}+h_{2}{\boldsymbol {J}})\right\rfloor +{\frac {t}{b}}{\text{xef}}\_{\text{compute}}_{k,f}(m)\right\rangle _{t}$
6. $ct=({\tilde {\boldsymbol {U}}},{\boldsymbol {v}})$
7. return $ct$

Так же, как и при вычислении ключей, находится матрица ${\boldsymbol {A}}$ .
Вводится элемент множества $\{0,1\}^{k}$ — $\rho$ . На его основе при помощи функции $f_{R}(\rho )$ вычисляется секретная матрица ${\boldsymbol {R}}$ размера $d/n\times {\bar {m}}$ , элементы которой принадлежат множеству ${\mathcal {H}}_{n}(h)$ (в случае RLWR ( $n=d$ ) это вектор, состоящий из троичных многочленов, если LWR ( $n=1$ ) — матрица, состоящая из $0,1$ и $-1$ ).
Используя матрицы ${\boldsymbol {A}}$ , ${\boldsymbol {R}}$ и постоянную округления $h_{2}={\frac {q}{2z}}$ ( $z=\max(p,{\tfrac {tq}{p}})$ ), вычисляется матрица ${\boldsymbol {U}}$ аналогично как в алгоритме создания ключей.
Транспонированная ${\boldsymbol {U}}$ есть первая компонента шифротекста.
Вторая компонента шифротекста — вектор ${\boldsymbol {v}}$ , элементы которого лежат в $\mathbb {Z} _{t}$ . Поскольку не все компоненты ${\boldsymbol {v}}$ необходимы для шифрования $k$ -битового сообщения $m$ , используется функция ${\text{Sample}}_{\mu }$ .
1. Если $n=d$ , то $\langle {\boldsymbol {B}}^{T}{\boldsymbol {R}}\rangle _{\xi (x)}$ — это многочлен и ${\text{Sample}}_{\mu }$ принимает его на вход, а на выходе выдаёт набор всех коэффициентов, соответствующих членам со степенью меньших $\mu$ : $c_{0}+c_{1}x+\cdots +c_{\mu -1}x^{\mu -1}+c_{\mu }x^{\mu }+\cdots +c_{n}x^{n}\rightarrow (c_{0},c_{1},\cdots ,c_{\mu -1})$ .
2. Если $n=1$ , то $\langle {\boldsymbol {B}}^{T}{\boldsymbol {R}}\rangle _{\xi (x)}$ — это матрица $M$ , состоящая из целых чисел и ${\text{Sample}}_{\mu }$ выдаёт первые $\mu$ чисел этой матрицы: $\overbrace {\underbrace {M_{0,0},M_{0,1},\cdots ,M_{0,{\bar {n}}-1}} _{\text{нулевая строка}},\cdots ,\underbrace {M_{i-1,0},M_{i-1,1},\cdots ,M_{i-1,j-1}} _{i-1{\text{-ая строка}}}} ^{\mu \,{\text{коэффициентов}}}$ , где $\mu =i{\bar {n}}+j$ .
3. Получаем, что ${\boldsymbol {v}}$ содержит только $\mu$ компонент.
Таким образом, получаем шифротекст $ct=({\tilde {\boldsymbol {U}}},{\boldsymbol {v}})$ ^[1]^[2].

Использование ${\text{Sample}}_{\mu }$ делает шифрование и дешифрование более эффективными, поскольку в зашифрованном тексте необходимо вычислять только коэффициенты $\mu$ вместо всех $n$ ^[1]^[2].

Так же для уменьшение вероятности ошибок применяются функции кодирования ${\text{xef}}\_{\text{compute}}_{k,f}(m(x))$ при шифровании и декодирования ${\text{xef}}\_{\text{correct}}_{k,f}$ при дешифровании . Функция ${\text{xef}}\_{\text{compute}}_{k,f}(m(x))$ преобразует многочлен $m(x)$ в набор двоичных коэффициентов размера $\mu$ . Затем этот набор складывается с набором ошибок $e=(e_{0},\cdots ,e_{\mu -1})$ , где каждый $e_{i}$ равен $0$ или $1$ , причём количество единиц в наборе ошибок не должно быть больше чем $f$ для однозначного декодирования^[1]^[2].

${\text{xef}}\_{\text{correct}}_{k,f}({\text{xef}}\_{\text{compute}}_{k,f}(m(x))+e)=m$ ^[1]^[2].

Алгоритм дешифрования

Algorithm 2: r5_cpa_pke_decrypt $(sk,ct)$
1. ${\boldsymbol {v}}_{p}={\frac {p}{t}}{\boldsymbol {v}}$
2. ${\boldsymbol {S}}=f_{S}(sk)$
3. ${\boldsymbol {U}}={\tilde {\boldsymbol {U}}}^{T}$
4. ${\boldsymbol {y}}=\left\langle \left\lfloor {\frac {b}{p}}({\boldsymbol {v}}_{p}-{\text{Sample}}_{\mu }\langle {\boldsymbol {S}}^{T}({\boldsymbol {U}}+h_{4}{\boldsymbol {J}})\rangle _{\xi (x)}+h_{3}{\boldsymbol {J}})\right\rfloor \right\rangle _{b}$
5. ${\hat {m}}={\text{xef}}\_{\text{correct}}_{k,f}({\boldsymbol {y}})$
6. return ${\hat {m}}$

Вычисляется вектор ${\boldsymbol {v}}_{p}$ .
На основе закрытого ключа находится секретная матрица ${\boldsymbol {S}}$ такая же, как в алгоритме создания ключей.
Транспонированием ${\boldsymbol {\tilde {U}}}$ находится матрица ${\boldsymbol {U}}$ , вычисленная в алгоритме шифрования.
Происходит дешифрование сообщения. $h_{3}={\frac {p}{2t}}+{\frac {p}{4}}-{\frac {q}{2p}}$ , $h_{4}={\frac {q}{2p}}-{\frac {q}{2z}}$ .
Исправляются ошибки. Таким образом получаем исходное сообщение ${\hat {m}}$ ^[1]^[2].

Достоинства Round5

Округление позволяет избежать дополнительного создания случайных величин — шума. Генерация шума может быть уязвимостью для атак по побочным каналам. Таким образом, отсутствие необходимости создания шума является дополнительным преимуществом^[1].

Так как секретные ключи в Round5 являются разреженными, троичными и сбалансированными, снижается вероятность ошибок при расшифровки и ускоряются вычисления. Последнему факту также помогает то, что ненулевые коэффициенты многочленов равны либо +1, либо −1, что подразумевает, что умножения могут быть выполнены с использованием только сложений и вычитаний^[2].

Благодаря тому, что модули $p,q,t,b$ являются степенями двойки, упрощается реализация функции округления, поскольку её можно реализовать, отбрасывая младшие биты. Аналогично, модульные вычисления могут быть реализованы путём отбрасывания старших битов^[1].

Возможное применение

Спектр применения системы Round5 широк. Она может быть использована как в сфере интернет вещей, так и для систем с высоким уровнем секретности. Это достигается тем, что для неё можно легко и точно выбрать параметры, например $n$ , $\tau$ , $f$ и $\xi (x)$ ^[2].

Примечания

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ ¹⁶ ¹⁷ ¹⁸ ¹⁹ ²⁰ 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 года.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² 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.

Ссылки

Официальный сайт (англ.)
Механизм инкапсуляции ключей (англ.)

[:0-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ ¹⁶ ¹⁷ ¹⁸ ¹⁹ ²⁰ 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] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² 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 года.

[3] Hayo Baan, Sauvik Bhattacharya, Oscar Garcia-Morchon, Ronald Rietman, Ludo Tolhuizen. Round2: KEM and PKE based on GLWR. — 2017. — № 1183. Архивировано 6 декабря 2019 года.

[_f23912643a01b8aa-4] Markku-Juhani O. Saarinen, 2017.

[5] 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 года.

[6] 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.

[1]

[2]

[3]

[4]

[5]

[6]