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

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

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

Имеется ${\displaystyle m}$ примеров формы ${\displaystyle \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}}$, где ${\displaystyle \mathbf {a} _{i}\in {\mathcal {R}}_{n,q}^{d/n}}$ и ${\displaystyle \mathbf {s} \leftarrow D_{s}}$ фиксирован, требуется найти ${\displaystyle \mathbf {s} }$^[1].

Сложность данной версии заключается в различении равномерного распределения по ${\displaystyle {\mathcal {R}}_{n,q}^{d/n}\times {\mathcal {R}}_{n,p}}$ и распределения ${\displaystyle (\mathbf {a} _{i},b_{i})}$, где ${\displaystyle \mathbf {a} _{i}{\xleftarrow[{}]{\$}}{\mathcal {R}}_{n,q}^{d/n}}$, ${\displaystyle \mathbf {s} \leftarrow D_{s}}$ фиксирован и ${\displaystyle 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].

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

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

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

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

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

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

Algorithm 1: r5_cpa_pke_keygen()
1. ${\displaystyle \sigma {\xleftarrow[{}]{\$}}\{0,1\}^{k}}$
2. ${\displaystyle {\boldsymbol {A}}=f_{d,n}^{(\tau )}(\sigma )}$
3. ${\displaystyle sk{\xleftarrow[{}]{\$}}\{0,1\}^{k}}$
4. ${\displaystyle {\boldsymbol {S}}=f_{S}(sk)}$
5. ${\displaystyle {\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. ${\displaystyle pk=(\sigma ,{\boldsymbol {B}})}$
7. return ${\displaystyle (pk,sk)}$

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

Algorithm 2: r5_cpa_pke_encrypt${\displaystyle (pk,m)}$
1. ${\displaystyle {\boldsymbol {A}}=f_{d,n}^{(\tau )}(\sigma )}$
2. ${\displaystyle {\boldsymbol {R}}=f_{R}(\rho )}$
3. ${\displaystyle {\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. ${\displaystyle {\tilde {\boldsymbol {U}}}={\boldsymbol {U}}^{T}}$
5. ${\displaystyle {\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. ${\displaystyle ct=({\tilde {\boldsymbol {U}}},{\boldsymbol {v}})}$
7. return ${\displaystyle ct}$

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

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

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

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

Algorithm 2: r5_cpa_pke_decrypt${\displaystyle (sk,ct)}$
1. ${\displaystyle {\boldsymbol {v}}_{p}={\frac {p}{t}}{\boldsymbol {v}}}$
2. ${\displaystyle {\boldsymbol {S}}=f_{S}(sk)}$
3. ${\displaystyle {\boldsymbol {U}}={\tilde {\boldsymbol {U}}}^{T}}$
4. ${\displaystyle {\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. ${\displaystyle {\hat {m}}={\text{xef}}\_{\text{correct}}_{k,f}({\boldsymbol {y}})}$
6. return ${\displaystyle {\hat {m}}}$

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

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

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

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

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

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

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