Round5

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

Round5, основанный на задаче Ring Learning with Rounding (RLWR)

Обозначения

Пусть $a$ — целое положительное число, тогда за $\mathbb {Z} _{a}$ обозначим набор чисел $\{0,1,\cdots ,a-1\}$. Для набора $A$ через $a{\xleftarrow[{}]{\$}}A$ обозначим случайный и равновероятный выбор $a$ из $A$. Для рационального числа $x$ обозначим: $\lfloor x\rfloor$— округление вниз до целого, а $\lfloor x\rceil$ — округление до ближайшего целого. $<x>_{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 является шифр 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{xefcompute}}_{k,f}(m)\right\rangle _{t}$
4. return $(pk=(a,b),sk=s)$

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

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

κ,f(xef computeκ,f(m) + e) = m.

Ссылки

• example.com