Round5

Round5 — это постквантовая система шифрования с открытым ключом, основанная на общей задаче обучения с округлением (General Learning with Rounding (GLWR)). Данная система является альтернативой для алгоритмов RSA и эллиптических кривых и предназначена для защиты от атак квантовыми компьютерами. Round5 состоит из алгоритмов, предназначенных для реализаций механизма инкапсуляции ключей (key encapsulation mechanism (KEM)) и схемы шифрования с открытым ключом (public-key encryption (PKE)). Данные алгоритмы попадают под категорию криптография на решётках.

Round5 представляет собой слияние двух систем: Round2, основанная также на задаче GLWR, и HILA5, имеющая код исправления ошибок.

Введение

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

Обозначения

• Пусть $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}}$.

Задача 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}$.

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

Имеется $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}$.

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

Сложность данной версии заключается в различении равномерного распределения по ${\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}$.

Виды задачи GLWR

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

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

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

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

Основа Round5

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

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

Параметры схемы шифрования 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$.

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

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)$

1. $\sigma$ равновероятно выбирается из множества $\{0,1\}^{k}$.
2. На основе $\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 )$, использующая детерминированный генератор случайных битов и перестановки, определяемые параметром $\tau$.
3. Как и $\sigma$, секретный ключ $sk$ выбирается случайно из $\{0,1\}^{k}$.
4. На основе $sk$ вычисляется секретная матрица ${\boldsymbol {S}}$ размера $d/n\times {\bar {n}}$, элементы которой принадлежат множеству ${\mathcal {H}}_{n}(h)$ (в случае RLWR ($n=d$) это вектор, состоящий из троичных многочленов, если LWR ($n=1$) — матрица, состоящая из $0,1$ и $-1$). Для этого используется функция $f_{S}(sk)$, использующая также детерминированный генератор случайных битов.
5. Вычисляется матрица ${\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$.
6. Открытый ключ представляет собой набор из $\sigma$ и ${\boldsymbol {B}}$.

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

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$

1. Так же, как и при вычислении ключей, находится матрица ${\boldsymbol {A}}$.
2. Вводится элемент множества $\{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$).
3. Используя матрицы ${\boldsymbol {A}}$, ${\boldsymbol {R}}$ и постоянную округления $h_{2}={\frac {q}{2z}}$ ($z=\max(p,{\tfrac {tq}{p}})$), вычисляется матрица ${\boldsymbol {U}}$ аналогично как в алгоритме создания ключей.
4. Транспонированная ${\boldsymbol {U}}$ есть первая компонента шифротекста.
5. Вторая компонента шифротекста — вектор ${\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$ компонент.
6. Таким образом, получаем шифротекст $ct=({\tilde {\boldsymbol {U}}},{\boldsymbol {v}})$.

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

Так же для уменьшение вероятности ошибок применяются функции кодирования ${\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$ для однозначного декодирования.

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

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

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}}$

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

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

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

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

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

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

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

Литература

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

Ссылки

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