Round5

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

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

Виды задачи GLWR

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

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

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

Система Round5 на задаче RLWR

Обозначения

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

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

Основой Round5 является схема шифрования r5_cpa_pke, надежная в смысле IND-CPA. r5_cpa_pke похож на схему шифрования Эль-Гамаля.

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

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

Algorithm 1: r5_cpa_pke_keygen()
1. $a{\xleftarrow[{}]{\$}}{\mathcal {R}}_{n,q}$
2. $s{\xleftarrow[{}]{\$}}{\mathcal {H}}_{n}(h)$
3. $b=\left\langle \left\lfloor {\frac {p}{q}}(\langle as\rangle _{{\mathit {\Phi }}_{n+1}(x)}+h_{1})\right\rfloor \right\rangle _{p}$
4. return $(pk=(a,b),sk=s)$

Для создания ключа равновероятно выбираются открытый многочлен $a(x)$ из множества многочленов степени не выше $n$ с коэффициентами из $\mathbb {Z} _{q}$ и многочлен $s(x)$, являющийся закрытым ключом, также равновероятно из множества ${\mathcal {H}}_{n}(h)$. Затем вычисляется многочлен $b(x)$, являющийся закрытым ключом, следующим образом: первым этапом вычисляется произведение $a(x)$ и $s(x)$ по модулю ${\mathit {\Phi }}_{n+1}(x)$, после к этому выражению прибавляется число $h_{1}={\frac {q}{2p}}$, затем полученная сумма умножается на ${\frac {p}{q}}$, в завершающем этапе коэффициенты полученного многочлена округляют к меньшим целым числам и уже округленные коэффициенты вычисляются по модулю $p$.

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

Algorithm 2: r5_cpa_pke_encrypt$(pk,m)$
1. $r{\xleftarrow[{}]{\$}}{\mathcal {H}}_{n}(h)$
2. $u=\left\langle \left\lfloor {\frac {p}{q}}(\langle ar\rangle _{{\mathit {\Phi }}_{n+1}(x)}+h_{1})\right\rfloor \right\rangle _{p}$
3. $\upsilon =\left\langle \left\lfloor {\frac {t}{p}}({\text{Sample}}_{\mu }\langle br\rangle _{\xi (x)}+h_{1})\right\rfloor +{\frac {t}{2}}{\text{xef}}\_{\text{compute}}_{k,f}(m)\right\rangle _{t}$
4. return $ct=(u,\upsilon )$

Для создания шифра необходимо выбрать случайно многочлен $r(x)$, являющийся секретным, из множества ${\mathcal {H}}_{n}(h)$. Используя его и $a(x)$, вычисляется первая компонента шифротекста $u(x)$ таким же образом как $b(x)$. Поскольку не все коэффициенты $\upsilon (x)$ необходимы для шифрования $k$-битового сообщения $m(x)$, для вычисления второй компоненты шифротекста $\upsilon (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})$$

Использование ${\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. $v_{p}={\frac {p}{t}}v$
2. $y=\left\langle \left\lfloor {\frac {2}{p}}(v_{p}-{\text{Sample}}_{\mu }\langle su\rangle _{\xi (x)}+h_{2})\right\rfloor \right\rangle _{2}$
3. ${\hat {m}}={\text{xef}}\_{\text{correct}}_{k,f}(y)$
4. return ${\hat {m}}$

Где $h_{2}={\frac {p}{2t}}+{\frac {p}{4}}-{\frac {q}{2p}}$. Таким образом получаем исходное сообщение ${\hat {m}}$.

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

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

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

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

Ссылки

• example.com