Подпись на основе обучения с ошибками в кольце

Подпись при обучении с ошибками в кольце (англ. Ring learning with errors signature) — один из классов криптосистем с открытым ключом, основанный на задаче обучения с ошибками в кольце^[1], который заменяет используемые алгоритмы подписи RSA и ECDSA. В течение последнего десятилетия проводились активные исследования по созданию криптографических алгоритмов, которые остаются безопасными, даже если у злоумышленника есть ресурсы квантового компьютера^[2][3]. Подпись при обучении с ошибками в кольце относится к числу пост-квантовых^[2][3] подписей с наименьшим открытым ключом и размерами подписи. Использование общей проблемы обучения с ошибками в криптографии было введено Одедом Регевым в 2005 году и послужило источником нескольких криптографических разработок^[4]. Основоположники криптографии при обучении с ошибками в кольце (англ. Ring learning with errors, RLWE), считают, что особенностью этих алгоритмов, основанных на обучении с ошибками, является доказуемое сокращение известных сложных задач^[1][5]. Данная подпись имеет доказуемое сокращение до задачи нахождения кратчайшего вектора в области криптографии на решётках^[6]. Это означает, что если можно обнаружить атаку на криптосистему RLWE, то целый класс предполагаемых сложных вычислительных проблем будет иметь решение^[7]. Первая подпись на основе RLWE была разработана Вадимом Любашевским^[8] и уточнена в 2011 году^[9]. Данная статья освещает фундаментальные математические основы RLWE и основана на схеме под названием GLYPH^[10].

Цифровая подпись является средством защиты информации и средством проверки подлинности источника информации. Криптография с открытым ключом предоставляет богатый набор различных криптографических алгоритмов для создания цифровых подписей. Тем не менее, подписи с открытым ключом, используемые в настоящее время, станут совершенно небезопасными после появления квантовых компьютеров^[2][11][12].Потому как даже относительно небольшой квантовый компьютер, способный обрабатывать только лишь десять тысяч битов информации, сможет легко взломать все широко используемые алгоритмы шифрования с открытым ключом, используемые для защиты конфиденциальности и цифровой подписи в Интернете^[2][13]. RSA, как один из наиболее широко используемых алгоритмов с открытым ключом для создания цифровых подписей, также становится уязвимым благодаря квантовым компьютерам, так как его безопасность основана на классической сложности задач факторизации^[14] . А квантовый компьютер, обладающий примерно 6n кубитами памяти и способный выполнять алгоритм Шора, легко может произвести факторизацию произведения двух n-разрядных простых чисел, а также взломать цифровые подписи на основе задач дискретного логарифма и дискретного логарифма эллиптической кривой^[15] за обозримое время^[16]. Предпосылки к появлению таких компьютеров имеются уже сейчас. Так, например, 20 сентября 2019 Financial Times сообщила: «Google утверждает, что достигла квантового превосходства на массиве из 54 кубитов, из которых 53 были функциональными и использовались для выполнения вычислений за 200 секунд, на что обычному суперкомпьютеру потребовалось бы около 10 000 лет»^[17]. Таким образом, относительно небольшой квантовый компьютер, используя алгоритмом Шора, может быстро взломать все цифровые подписи, используемые для обеспечения конфиденциальности и целостности информации в Интернете сегодня^[16].

Криптографические примитивы, основанные на сложных задачах теории решёток, играют ключевую роль в области постквантовых криптографических исследований. Во 2 раунде внесения представлений о постквантовой криптографии, названных NIST^[18], 12 из 26 основаны на решётках и большинство из них основаны на проблеме обучения с ошибками (англ. Learning With Errors, LWE) и её вариантах. Было предложено огромное количество криптографических примитивов на основе LWE, таких как шифрование с открытым ключом, протоколы обмена ключами, цифровые подписи, семейства псевдослучайных функций и другие^[19]. Криптографические протоколы, основой которых служит задача LWE, являются такими же безопасными, как и протоколы, основывающиеся на задачах теории решёток, которые на сегодняшний день полагаются чрезвычайно сложными. Тем не менее, криптографические примитивы, основанные на задаче LWE страдают от больших размеров ключей, следовательно, они обычно являются неэффективными^[19].Этот недостаток стимулировал людей к развитию более эффективных вариантов LWE, таких как обучение с ошибками в кольце(англ. Ring Learning with errors, RLWE)^[1]. Было показано, что задача RLWE также вычислительно трудна, как и наисложнейшие задачи теории решёток над специальными классами идеальных решёток^[1], и криптографические приложения RLWE обычно имеют большую эффективность по сравнению с обычными LWE, особенно в циклотомическом полиномиальном кольце, приведённым по модулю многочлена, степень которого является спепенью 2^[19].

Подпись RLWE работает в кольце многочленов по модулю многочлена ${\displaystyle \Phi (x)}$ степени ${\displaystyle n}$ с коэффициентами в конечном поле ${\displaystyle Z_{q}}$ для нечётного простого числа ${\displaystyle q}$. Множество многочленов над конечным полем с операциями сложения и умножения образует бесконечное полиномиальное кольцо ${\displaystyle F_{q}[x]}$^[9]. Умножение и сложение полиномов будет работать как обычно с результатом, приведённым по модулю ${\displaystyle \Phi (x)}$(то есть кольцо ${\displaystyle F_{q}[x]/\Phi (x)}$). Типичный многочлен выражается как:

${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}$

Поле ${\displaystyle Z_{q}}$ имеет свои элементы в наборе ${\displaystyle \{-(q-1)/2,...-1,0,1,...(q-1)/2\}}$. Если ${\displaystyle n}$ — это степень двух, то многочлен ${\displaystyle \Phi (x)}$ будет круговым многочленом ${\displaystyle x^{n}+1}$. Возможны другие варианты выбора ${\displaystyle n}$, но соответствующие круговые многочлены являются более эффективными^[9].

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

Положим: ${\displaystyle a_{i}(x)}$ — множество случайных, но известных полиномов из ${\displaystyle Z_{q}[x]/\Phi (x)}$ с различными коэффициентами для всех ${\displaystyle F_{q}}$, ${\displaystyle e_{i}(x)}$ — множество малых случайных и неизвестных полиномов относительно границы ${\displaystyle b}$ в кольце ${\displaystyle Z_{q}[x]/\Phi (x)}$, ${\displaystyle s(x)}$ — малый неизвестный полином относительно границы ${\displaystyle b}$ в кольце ${\displaystyle Z_{q}[x]/\Phi (x)}$, ${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$.

Поиск: найти полином ${\displaystyle s(x)}$ по списку полиномиальных пар ${\displaystyle (a_{i}(x),b_{i}(x))}$

Решение: данный список полиномиальных пар ${\displaystyle (a_{i}(x),b_{i}(x))}$ определяет были ли полиномы ${\displaystyle b_{i}(x)}$ построены как ${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$ или были сгенерированы случайным образом из ${\displaystyle Z_{q}[x]/\Phi (x)}$ с коэффициентами из всех ${\displaystyle F_{q}}$.

Сложность данной задачи заключается в выборе фактор-полинома ${\displaystyle \Phi (x)}$ степени ${\displaystyle n}$, над полем ${\displaystyle F_{q}}$ и границей ${\displaystyle b}$. Во многих алгоритмах, основывающихся на RLWE, закрытый ключ будет парой «малых» полиномов ${\displaystyle s(x)}$ и ${\displaystyle e(x)}$. Тогда соответствующий ему открытый ключ будет парой полиномов ${\displaystyle a(x)}$, выбранный случайно из ${\displaystyle Z_{q}[x]/\Phi (x)}$, и полинома ${\displaystyle t(x)=(a(x)\cdot s(x))+e(x)}$. Данные ${\displaystyle a(x)}$ и ${\displaystyle t(x)}$ полиномы должны быть вычислительно неразрешимы для задачи восстановления полинома ${\displaystyle s(x)}$^[1][6].

Циклотомическим классом над полем ${\displaystyle \mathbb {F} _{q},\;q=p^{s}}$, порождённым некоторым элементом ${\displaystyle \alpha \in \mathbb {F} _{Q},\;Q=p^{S}}$ называется множество всех различных элементов ${\displaystyle \mathbb {F} _{Q}}$, являющихся ${\displaystyle q}$-ми степенями ${\displaystyle \alpha }$^[20].

Если ${\displaystyle \alpha }$ — примитивный элемент^[21] (такой элемент, что ${\displaystyle \alpha ^{Q-1}=1}$ и ${\displaystyle \alpha ^{k}\neq 1}$ при ${\displaystyle 0<k<Q-1}$) поля ${\displaystyle \mathbb {F} _{Q},\;Q=q^{m}}$, то циклотомический класс ${\displaystyle C=\{\alpha ,\;\alpha ^{q},\;\alpha ^{q^{2}},\;\ldots ,\;\alpha ^{q^{m-1}}\}}$ над полем ${\displaystyle \mathbb {F} _{q}}$ будет иметь ровно ${\displaystyle m}$ элементов. Любой элемент из циклотомического класса может порождать этот и только этот класс, а, следовательно, и принадлежать только ему.

Пример 1. Пусть ${\displaystyle q=2}$, ${\displaystyle Q=2^{3}=8}$ и ${\displaystyle \alpha }$ — примитивный элемент поля ${\displaystyle \mathbb {F} _{8}}$, то есть ${\displaystyle \alpha ^{7}=1}$ и ${\displaystyle \alpha ^{i}\neq 1}$ при ${\displaystyle i<7}$. Учитывая также, что ${\displaystyle \alpha ^{8}=\alpha }$, можно получить разложение всех ненулевых элементов поля ${\displaystyle \mathbb {F} _{8}}$ на три циклотомических класса над полем ${\displaystyle \mathbb {F} _{2}}$:

${\displaystyle {\begin{matrix}\{1\},\\\{\alpha ,\;\alpha ^{2},\;\alpha ^{4}\},\\\{\alpha ^{3},\;\alpha ^{6},\;\alpha ^{5}\}.\end{matrix}}}$

Пример 2. Аналогично можно построить классы на поле ${\displaystyle \mathbb {F} _{16}}$ над полем ${\displaystyle \mathbb {F} _{4}}$, то есть ${\displaystyle q=4,\;Q=q^{2}=16}$. Пусть ${\displaystyle \alpha }$ — примитивный элемент поля ${\displaystyle \mathbb {F} _{16}}$, значит ${\displaystyle \alpha ^{15}=1,\;\alpha ^{16}=\alpha }$.

${\displaystyle {\begin{matrix}\{1\},\\\{\alpha ,\;\alpha ^{4}\},\;\{\alpha ^{2},\;\alpha ^{8}\},\\\{\alpha ^{3},\;\alpha ^{12}\},\;\{\alpha ^{5}\},\;\{\alpha ^{10}\},\\\{\alpha ^{6},\;\alpha ^{9}\},\;\{\alpha ^{7},\;\alpha ^{13}\},\\\{\alpha ^{11},\;\alpha ^{14}\}.\end{matrix}}}$

Подпись RLWE использует многочлены, которые считаются «малыми» по отношению к равномерной норме. Равномерная норма для полинома является просто наибольшим абсолютным значением коэффициентов полинома, и эти коэффициенты рассматриваются как целые числа в ${\displaystyle Z}$, а не в ${\displaystyle Z_{q}}$^[6].Алгоритм подписи создаёт случайные многочлены, равномерная норма которых мала по отношению к конкретной границе. Это легко сделать путём случайной генерации всех коэффициентов полинома ${\displaystyle a_{0},...,a_{n-1}}$ так, чтобы гарантировать с большой вероятностью норму меньше или равную этой границе. Имеется два распространённых способа сделать это^[9]:

• Используя равномерное распределение: коэффициенты малого полинома равномерно выбираются из набора коэффициентов. Пусть ${\displaystyle b}$ будет целым числом, которое намного меньше, чем ${\displaystyle q}$. Если мы случайным образом выберем полиномиальные коэффициенты из множества ${\displaystyle \{-b,-b+1,-b+2,...-2,-1,0,1,2,...,b-2,b-1,b\}}$, то норма многочлена будет ${\displaystyle \leqslant b}$.
• Используя дискретную гауссову выборку: для нечётного целого числа ${\displaystyle q}$, коэффициенты выбираются случайным образом путём выборки из набора ${\displaystyle \{-{\frac {q-1}{2}},...0,...{\frac {q-1}{2}}\}}$ в соответствии с дискретным распределением Гаусса со средним ${\displaystyle 0}$ и дисперсией ${\displaystyle \sigma ^{2}}$.

В подписи RLWE GLYPH, используемой в качестве примера ниже, для коэффициентов «малых» многочленов будет использоваться метод с равномерным распределением, и значение ${\displaystyle b}$ будет намного меньше значения ${\displaystyle q}$^[6].

Большинство алгоритмов подписи RLWE также требуют способности криптографического хэширования произвольных битовых строк в небольшие полиномы в соответствии с некоторым распределением^[6][10]. В приведённом ниже примере используется хеш-функция ${\displaystyle {\mathsf {POLYHASH}}(\omega )}$, которая принимает битовую строку ${\displaystyle \omega }$ в качестве входных данных и выводит полином с ${\displaystyle n}$ коэффициентами, так что ровно ${\displaystyle k}$ из этих коэффициентов имеет абсолютное значение больше нуля и меньше целочисленной границы ${\displaystyle b}$^[10].

Ключевой особенностью алгоритмов подписи RLWE является использование метода, известного как выборка с отклонением^[9][8]. В этом методе, если равномерная норма полинома подписи превышает фиксированную границу ${\displaystyle \beta }$, то этот полином будет отброшен, и процесс генерации подписи начнётся снова. Этот процесс будет повторяться до тех пор, пока равномерная норма полинома не станет меньше или равна границе. Выборка с отклонением гарантирует, что выходная подпись не может эксплуатироваться с использованием значений секретного ключа подписывающего лица^[10].

В данном примере граница ${\displaystyle \beta }$ будет равна ${\displaystyle (b-k)}$, где ${\displaystyle b}$ — это диапазон равномерной выборки, а ${\displaystyle k}$ — количество ненулевых коэффициентов, связанных с разрешённым полином^[6].

Согласно GLYPH^[10], максимальная степень многочленов будет ${\displaystyle n-1}$ и, следовательно, иметь ${\displaystyle n}$ коэффициентов^[6].Типичные значения для ${\displaystyle n}$ являются 512 и 1024^[6]. Коэффициенты этих многочленов будут элементами поля ${\displaystyle F_{q}}$ , где ${\displaystyle q}$ — нечётное простое число, соответствующее ${\displaystyle 1{\bmod {4}}}$. Для ${\displaystyle n=1024}$, GLYPH определяет ${\displaystyle q=59393,b=16383}$ и ${\displaystyle k}$ — количество ненулевых коэффициентов на выходе ${\displaystyle {\mathsf {POLYHASH}}}$ равное ${\displaystyle 16}$^[10].Безопасность схемы подписи тесно связана с относительными размерами ${\displaystyle n,q,b,k}$.

Как отмечено выше, многочлен ${\displaystyle \Phi (x)}$, который определяет кольцо используемых многочленов, будет равняться ${\displaystyle x^{n}+1}$. Наконец, ${\displaystyle a(x)}$ будет случайно выбранным и фиксированным полиномом с коэффициентами из множества ${\displaystyle \{-b,...0,...,b\}}$. Все подписывающие и проверяющие сущности будут знать ${\displaystyle n,q,b,k,\Phi (x),a(x)}$ и ${\displaystyle \beta =b-k}$^[10].

Согласно GLYPH^[10], открытый ключ для подписи сообщения ${\displaystyle M}$ генерируется посредством следующих шагов:

1. Генерация двух небольших полиномов ${\displaystyle s(x)}$ и ${\displaystyle e(x)}$ с коэффициентами, выбранными случайно с равномерным распределением из множества ${\displaystyle \{-b,...-1,0,1,...,b\}}$
2. Вычисление ${\displaystyle t(x)=a(x)s(x)+e(x)}$
3. Распределение ${\displaystyle t(x)}$ как открытого ключа объекта

Полиномы ${\displaystyle s(x)}$ и ${\displaystyle e(x)}$ служат закрытым ключом, а ${\displaystyle t(x)}$ — соответствующим открытым ключом. Безопасность этой схемы подписи основана на следующей проблеме: для заданного полинома ${\displaystyle t(x)}$ необходимо найти малые полиномы ${\displaystyle f_{1}(x)}$ и ${\displaystyle f_{2}(x)}$, такие что: ${\displaystyle a(x)f_{1}(x)+f_{2}(x)=t(x)}$. Если эту задачу трудно решить, то схему подписи будет трудно подделать.

Согласно GLYPH^[10], чтобы подписать сообщение ${\displaystyle M}$, выраженное в виде битовой строки, необходимо произвести следующие операции:

1. Генерация двух небольших полиномов ${\displaystyle y_{1}(x)}$ и ${\displaystyle y_{2}(x)}$ с коэффициентами из множества ${\displaystyle \{-b,...-1,0,1,...,b\}}$
2. Вычисление ${\displaystyle w(x)=a(x)y_{1}(x)+y_{2}(x)}$
3. Отображение ${\displaystyle w(x)}$ в битовую строку ${\displaystyle \omega }$
4. Вычисление ${\displaystyle c(x)={\mathsf {POLYHASH}}(\omega |M)}$ (Это многочлен с k ненулевыми коэффициентами. Символ "|" обозначает конкатенацию строк)
5. Вычисление ${\displaystyle z_{1}(x)=s(x)c(x)+y_{1}(x)}$
6. Вычисление ${\displaystyle z_{2}(x)=e(x)c(x)+y_{2}(x)}$
7. Если ${\displaystyle \|z_{1}(x)\|}$ и ${\displaystyle \|z_{2}(x)\|>\beta =(b-k)}$, то повторять пункты 1-6 (Норма ${\displaystyle \|\cdot \|}$ — равномерная норма)
8. Подпись — это тройка полиномов ${\displaystyle c(x),z_{1}(x)}$ и ${\displaystyle z_{2}(x)}$

Согласно GLYPH^[10], для проверки сообщения ${\displaystyle M}$, выраженного в виде битовой строки, необходимо использовать публичный ключ автора данного сообщения ${\displaystyle t(x)}$ и цифровую подпись (${\displaystyle c(x),z_{1}(x),z_{2}(x)}$):

1. ${\displaystyle \|z_{1}(x)\|}$, и ${\displaystyle \|z_{2}(x)\|\leqslant \beta }$, иначе подпись не принята
2. Вычисление ${\displaystyle w'(x)=a(x)z_{1}(x)+z_{2}(x)-t(x)c(x)}$
3. Отображение ${\displaystyle w'(x)}$ в битовую строку ${\displaystyle \omega '}$
4. Вычисление ${\displaystyle c'(x)={\mathsf {POLYHASH}}(\omega '|M)}$
5. Если ${\displaystyle c'(x)=c(x)}$, подпись считается действительной

Не сложно показать корректность проверки:
${\displaystyle a(x)z_{1}(x)+z_{2}(x)-t(x)c(x)=a(x)[s(x)c(x)+y_{1}(x)]+z_{2}(x)-[a(x)s(x)+e(x)]c(x)=}$
${\displaystyle =a(x)y_{1}(x)+z_{2}(x)-e(x)c(x)=a(x)y_{1}(x)+e(x)c(x)+y_{2}(x)-e(x)c(x)=}$
${\displaystyle =a(x)y_{1}(x)+y_{2}(x)=w(x)}$

В работе Любошевского^[1] много внимания уделяется безопасности алгоритма, однако, чтобы осветить данные свойства задачи и доказать их полное соответствие заявленным, следует провести ряд прямых атак на RLWE. Атака определяется выбором числового поля ${\displaystyle K}$ и простого числа ${\displaystyle q}$, называемого модулем, наряду с распределением ошибок.

Дукас и Дурмус предложили недвойственный вариант RLWE в циклотомической постановке и доказали, что сложность нового и прежнего варианта идентичны^[22]. Этот вариант RLWE порождает распределение ошибки как дискретная гауссова функция в кольце целых чисел ${\displaystyle R}$ при каноническом вложении, а не в изображении двойственного идеала. Двойственный и недвойственные варианты эквиваленты вплоть до распределения ошибок^[23]. Для недвойственного варианта RLWE авторы^[24] предложили атаку на версию «решение» RLWE. При атаке используется модуль ${\displaystyle q}$ степени вычетов 1, дающий кольцевой гомоморфизм ${\displaystyle p:R}$→ ${\displaystyle F_{q}}$. Атака работает, когда с подавляющей вероятностью распределение ошибок RLWE при наборе пар ${\textstyle p}$ принимает значения только в малом подмножестве ${\displaystyle F_{q}}$. Затем авторы^[24] дают целое семейство примеров, уязвимых для атак. Однако, уязвимые числовые поля не являются полями Галуа, поэтому теорема сведения версии «поиск» к версии «решение» не применима и атака не может быть прямо использована для варианта «поиск» задачи RLWE, на что собственно была нацелена представленная работа^[24].

Однако позже в другой работе^[23], эта атака была обобщена на некоторые числовые поля Галуа и модули более высокой степени. В ней же была представлена её реализация для конкретных экземпляров RLWE, включая вариант сведения «поиска» к «решению». Основным её принципом было то, что гомоморфизм в кольце рассматривался в виде ${\textstyle R}$→${\displaystyle F_{q}^{f}}$(где, ${\displaystyle f}$ — это степень ${\displaystyle q}$) для ${\displaystyle f>1}$, и то, что распределение ошибок отличается от случайного, используя статистический критерий хи-квадрат вместо того, чтобы полагаться на значения многочлена ошибок. Авторы акцентируют внимание также на том, что ими была проведена атака на вариацию RLWE с простыми циклотомическими кольцами при определённых предположениях о модуле и частоте ошибок, которая успешно выполняется с высокой вероятностью. А именно, они показали атаку на недвойственный вариант RLWE, когда модуль равен уникальному и простому ${\textstyle p}$.К примеру, если размерность n = 808, можно атаковать вариацию RLWE в циклотомическом кольце $Q$(ζ809) за 35 секунд, где модуль равен 809. Возникает тогда вопрос о том, безопасны ли циклотомические поля для криптографии в принципе, в зависимости от того, можно ли использовать большие модули (которые используются на практике) вместо тех, что были рассмотрены в примере статьи. В дополнение, авторами статьи была осуществлена ещё одна атака на двойственную RLWE версии «решение» в ${\displaystyle p}$-ом циклотомическом поле с произвольным модулем ${\textstyle q}$, предполагая, что ширина распределения ошибок составляет значение около ${\displaystyle 1/{\sqrt {p}}}$.

• Сагалович Ю. Л. Введение в алгебраические коды. — Review of General Psychology. — ИППИ РАН, 2014. — 310 с.
• Блейхут Р. Э. Теория и практика кодов, контролирующих ошибки. — Мир, 1986. — 576 с.
• Bakhtiari M., Maarof M. A. Serious Security Weakness in RSA Cryptosystem : [англ.]. — IJCSI, 2012. — 175 p.