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 требуются в средах, где производительность не так важна по сравнению с безопасностью.

Напротив, по сравнению с 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}$, т. е. $\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}$ называется троичным, если все его коэффициенты равны $0,1$ или $-1$. Для любого элемента $\upsilon \in {\mathcal {R}}_{n}$ вес Хемминга определяется как число ненулевых коэффициентов. ${\mathcal {H}}_{n}(h)$ определяется как множество троичных полиномов степени меньше $n$ с весом Хемминга $h$. В Round5 такие многочлены к тому же еще являются сбалансированными и разреженными, то есть имеют ровно ${\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)$, являющийся закрытым ключом, следующим образом:

1. Вычисляется произведение $a(x)$ и $s(x)$ по модулю ${\mathit {\Phi }}_{n+1}(x)$
2. К этому выражению прибавляется число $h_{1}={\frac {q}{2p}}$
3. Полученная сумма умножается на ${\frac {p}{q}}$
4. Коэффициенты полученного многочлена округляют к меньшим целым числам и уже округленные коэффициенты вычисляются по модулю $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$ являются степенями двойки, упрощается реализация функции округления, поскольку её можно реализовать, отбрасывая младшие биты. Аналогично, модульные вычисления могут быть реализованы путем отбрасывания старших битов.

Возможные атаки на Round5

• Dual Attack

Ссылки

• example.com