Обучение с ошибками в кольце

Обучение с ошибками в кольце (англ. Ring learning with errors, RLWE) — это вычислительная задача, которая была сформулирована как вариант более общей задачи обучения с ошибками (с англ. LWE), с целью использовать преимущество дополнительной алгебраической структуры (т.е. кольца многочленов) из теории решёток, что дало возможность повысить и расширить возможности шифрования тех криптографических приложений, которые ранее основывались на LWE. Задача RLWE стала основой новых криптографических алгоритмов, предназначенных для защиты данных от криптоанализа квантовыми компьютерами, а также важным применением для построения схем гомоморфного шифрования. По причине того, что предполагаемая трудность решения задачи RLWE очень высока даже на квантовом компьютере, криптография на её основе может стать основополагающей криптографией с открытым ключом в будущем, так же как и задачи целочисленной факторизации и дискретного логарифмирования послужили основой для криптографии с открытым ключом в начале 1980-х годов. Следует отметить, что RLWE может быть аппроксимирована задачей нахождения кратчайшего вектора на идеальных решётках, которые представляют собой математически структурированные решётки, соответствующие идеалам в кольце.

Предпосылки

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

В настоящее время безопасность современной криптографии, в частности криптографии с открытым ключом, базируется на предполагаемой неразрешимости некоторых теоретических вычислительных задач таких как задача факторизации двух подобранных целых чисел или вычисления дискретного логарифма для предоставления цифровых подписей, обмена ключами и обеспечения конфиденциальности. При достаточно больших размерах ключа эти криптографические системы с открытым ключом считаются практически неуязвимыми для взлома на современных компьютерах, суперкомпьютерах или на специальных вычислительных кластерах. В 1994 г. Питер Шор предложил квантовый алгоритм выше упомянутой факторизации целых чисел. Его модифицированная версия умеет решать задачу дискретного логарифмирования в группе точек эллиптической кривой (ECDLP). Сам алгоритм не может быть использован на классических компьютерах, только лишь на квантовых, чтобы решать задачу факторизации или дискретного логарифмирования за полиномиальное время и так как в данный момент концепция квантовых компьютеров стала стремительно развиваться, то стало крайне важным использование эффективных квантовых алгоритмом с открытым ключом шифрования.

Описание алгоритма

Задача обучения с ошибками в кольце (RLWE) основывается на арифметике полиномов с коэффициентами из конечных полей. Полином a(x) выражается следующим образом:

a(x) = a₀ + a₁x + a₂x² + … + a_n-3x^n-3 + a_n-2x^n-2 + a_n-1x^n-1

Для полиномов определена операция умножения и сложения как и для обыкновенных чисел. В контексте задачи RLWE коэффициенты многочленов и все операции над ними будут выполняться в конечном поле, определяемое как ${\textstyle \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q}}$ для простого числа ${\textstyle q}$. Множество многочленов над конечным полем с операциями сложения и умножения образует бесконечное полиномиальное кольцо (${\textstyle \mathbf {F} _{q}[x]}$), с конечным подкольцом которого и работает задача RLWE. Обычно это подкольцо является факторкольцом, образованное сокращением всех полиномов в ${\textstyle \mathbf {F} _{q}[x]}$ по модулю неприводимого многочлена ${\textstyle \Phi (x)}$. Это конечное факторкольцо может быть записано в виде $\mathbf {F} _{q}[x]/\Phi (x)$.

Если степень полинома $\Phi (x)$ ${\textstyle n}$, тогда подкольцо становится кольцом полиномов степени меньше чем $n$ по модулю $\Phi (x)$ с коэффициентами из $F_{q}$. Значения ${\textstyle n}$, ${\textstyle q}$ вместе с многочленом $\Phi (x)$ частично определяют математический контекст для задачи RLWE.

Ещё одно важное для RLWE понятие — это понятие "малых" полиномов по отношению к некоторой мере. Обычая такая мера для RLWE есть «бесконечная» норма. Понятие бесконечной нормы полинома вводится просто как наибольший коэффициент многочлена, когда эти коэффициенты рассматриваются как целые числа. Следовательно, $||a(x)||_{\infty }=b$ означает, что бесконечная норма полинома $a(x)$ это $b$. Таким образом, $b$ — это наибольший коэффициент $a(x)$.

Последнее важное понятие для RLWE, которое нужно понимать, — генерация случайных полиномов в $\mathbf {Z} _{q}[x]/\Phi (x)$ и генерация "малых" полиномов. Случайный многочлен легко генерируется простым случайным распределением $n$ коэффициентов полинома из $\mathbf {F} _{q}$, где $\mathbf {F} _{q}$ обычно представляется как множество $\{-(q-1)/2,...,-1,0,1,...,(q-1)/2\}$.

Генерация случайным образом "малых" полиномов осуществляется путём генерации коэффициентов многочлена из $\mathbf {F} _{q}$ что гарантирует или, по крайней мере, делает очень вероятным тот факт, что эти коэффициенты будут малы. Есть два распространённых способа это осуществить:

1. Используя дискретное равномерное распределение — коэффициенты малого полинома равномерно отбираются из множества малых коэффициентов. Пусть ${\textstyle b}$ целое число, которое много меньше ${\textstyle q}$. Если мы случайным образом выберем коэффициенты из множества ${\textstyle \{-b,-b+1,-b+2,\ldots ,-2,-1,0,1,2,\ldots ,b-2,b-1,b\}}$, то полином будет "малым" по отношению к граничному значению( ${\textstyle b}$).
2. Используя Гауссову функцию — для нечётного значения ${\textstyle q}$ коэффициенты полинома выбираются случайным образом из множества ${\textstyle \{-(q-1)/2,\ldots ,(q-1)/2\}}$ в соответствии с дискретным распределением Гаусса с математическим ожиданием $0$ и дисперсией ${\textstyle \sigma }$. Этот метод сложнее, чем дискретное равномерное распределение, но он позволяет доказать безопасность алгоритма.

Задача RLWE

Постановку задачи обучения с ошибками в кольце можно дать двумя различными способами: первый вариант - "поиск", второй вариант - "решение". Оба в начале построения алгоритма одинаковы. Предположим:

• $a_{i}(x)$ - множество случайных но известных полиномов из $\mathbf {Z} _{q}[x]/\Phi (x)$ с различными коэффициентами из всех $\mathbf {F} _{q}$.
• $e_{i}(x)$ - множество малых случайных и неизвестных полиномов относительно границы $b$ в кольце $\mathbf {Z} _{q}[x]/\Phi (x)$.
• $s(x)$ - малый неизвестный полином относительно границы $b$ в кольце $\mathbf {Z} _{q}[x]/\Phi (x)$.
• $b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$.

Версия "поиска" задачи RLWE заключается в том, чтобы найти полином $s(x)$ по списку полиномиальных пар $(a_{i}(x),b_{i}(x))$.

Версия "решения" данной задачи может быть сформулирована следующим образом: данный список полиномиальных пар $(a_{i}(x),b_{i}(x))$ определяет были ли полиномы $b_{i}(x)$ построены как $b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$ или были сгенерированы случайным образом из $\mathbf {Z} _{q}[x]/\Phi (x)$ с коэффициентами из всех $\mathbf {F} _{q}$.

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

Безопасность

В случаях когда полином $\Phi (x)$ круговой, сложность решения задачи RLWE версии "поиск" эквивалентна сложности нахождения короткого вектора (совершенно не обязательно кратчайшего) в идеальной решётке, состоящей из элементов $\mathbf {Z} [x]/\Phi (x)$, представленных в виде целочисленных векторов. Эта задача широко известна как задача приближённого нахождения кратчайшего вектора (α-ЗКВ) и она заключается в том, чтобы найти вектор в α раз короче, чем кратчайший. Задача α-ЗКВ в регулярных решётках как известно имеет сложность NP согласно работе Даниэля Мичансио в 2001 и это не из-за значений α, которые сводят её к общей задаче обучения с ошибками. Однако, до сих пор нет доказательства, которое показывало бы, что сложность задачи α-ЗКВ для идеальных решёток эквивалентна в среднем задаче α-ЗКВ. Впрочем, есть доказательство, что если любая отдельная задача α-ЗКВ сложно разрешима на идеальных решётках, то задача RLWE будет сложно разрешима в любом случайном виде.

Насчёт сложности задачи нахождения кратчайшего вектора в идеальных решётках, исследователь Майкл Шнайдер пишет, "До сих пор нет алгоритма использующего специальную структуру идеальных решёток. Широко распространённым мнением является то, что решение задачи кратчайшего вектора (и других задач) в идеальных решётках настолько же сложно как и в регулярных решётках." Доказано, что сложность этих задача в регулярных решётках есть NP.. Однако, есть небольшое число сторонников и другого мнения, считающее, что идеальные решётки настолько же безопасны как и регулярные.

Пейкерт считает, что это сходство в безопасности делает задачу RLWE хорошим базисом для будущей криптографии. Он пишет: "Существует математическое доказательство 'единственности' (в рамках некоторой модели атаки) способа взлома криптосистемы в её случайных экземплярах - это возможность решить соответствующую ей задачу решёток в наихудшем случае"

Криптография RLWE

Основным преимуществом криптографии основанной на обучении с ошибками в кольце по сравнению с изначальной (на обучении с ошибками с англ. LWE) является длина открытого и закрытого ключей. Для RLWE он приблизительно равняется квадратному корню из длины ключа в LWE. Для 128-битного уровня криптостойкости алгоритм на RLWE будет использовать открытый ключ длиной 7000 бит. Соответствующая схема LWE — 49 миллионов бит для того же уровня криптостойкости. С другой стороны, ключи RLWE всё же длиннее тех, что используют его предшественники RSA и эллиптические кривые Диффи-Хеллмана. которые требуют 3072 и 256 битные ключи соответственно, чтобы достичь 128-битного уровня криптостойкости. С вычислительной точки зрения, алгоритмы RLWE как минимум равны или даже лучше по эффективности чем существующие с открытыми ключами.

Существует три группы криптографических алгоритмов RLWE:

Обмен ключами при обучении с ошибками (англ. RLWE-KEX)

Основная статья: Обмен ключами при обучении с ошибками

Фундаментальная идея использования LWE и RLWE для обмена ключами была предложенна и озвучена в 2011 году Цзиньтай Дин в университете Цинциннати. Основная идея заключается в ассоциативности умножения матриц, а ошибки используются для обеспечения безопасности. В 2012 появляется статья после подачи заявки на патент в том же году.

В 2014 Пейкерт представил схему транспортировки ключей, следуя базовой идее Дина, который так же использует дополнительный 1-битный сигнал для округления в его конструкции. RLWE версия классического MQV Диффи-Хеллмена обмена ключами была позже опубликована Зангом . Безопасность обеих методов обмена ключами напрямую связана с задачей приближённого нахождения коротких векторов в идеальной решётке.

Подпись при обучении с ошибками в кольце(RLWE-SIG)

RLWE версия классического протокола Фейга-Фиата-Шамира была создана и преобразована в цифровую подпись в 2011 году Любашевским. Детали этой подписи были раскрыты в 2012 году Гунесю, Любашевским и Попплеманом и опубликованы в их статье «Практическая криптография на основе решётки - схема подписи для встроенных систем». Эти документы заложили основу для множества современных алгоритмов, некоторые из которых основаны непосредственно на задаче RLWE, а некоторые и не связаны с RLWE вовсе.

Гомоморфное шифрование в обучении с ошибками в кольце(RLWE-HOM)

Цель гомоморфного шифрования заключается в том, чтобы позволить обсчёт конфиденциальных данных на вычислительных устройствах, которым не следует доверять эти данные. Этим устройствам разрешается обрабатывать зашифрованный текст на выходе из гомоморфного шифрования. В 2011 году Бракерский и Вайкунтанатан опубликовали «Полное гомоморфное шифрование для Ring-LWE и безопасность сообщений зависимых от ключа», в котором описывается гомоморфная схема шифрования непосредственно по задаче RLWE.

Атаки на RLWE

Очень важно понимать насколько RLWE безопасно как таковое. В работе Любошевского много внимания уделяется безопасности алгоритма, однако, чтобы осветить эти свойства задачи и доказать их полное соответствие заявленным, следует провести ряд прямых атак на RLWE. Данная задача определяется выбором числового поля ${\textstyle K}$ и простого числа ${\textstyle q}$, называемого модулем, наряду с распределением ошибок. Дукас и Дурмус предложили недвойственный вариант RLWE в циклотомической постановке и доказали, что сложность нового и прежнего варианта идентичны. Этот вариант RLWE порождает распределение ошибки как дискретная гауссова функция в кольце целых чисел ${\textstyle R}$ при каноническом вложении, а не в изображении двойственного идеала. Двойственный и недвойственные варианты эквиваленты вплоть до распределения ошибок. Для недвойственного варианта RLWE авторы предложили атаку на версию "решение" RLWE. При атаке используется модуль ${\textstyle q}$ степени вычетов 1, дающий кольцевой гомоморфизм ${\textstyle p:R}$→ ${\textstyle \mathbf {F} _{q}}$. Атака работает, когда с подавляющей вероятностью распределение ошибок RLWE при наборе пар ${\textstyle p}$принимает значения только в малом подмножестве ${\textstyle \mathbf {F} _{q}}$. Затем авторы дают целое семейство примеров, уязвимых для атак. Однако, уязвимые числовые поля не являются полями Галуа, поэтому теорема сведения версии "поиск" к версии "решение" не применима и атака не может быть прямо использована для варианта "поиск" задачи RLWE, на что собственно была нацелена представленная работа.

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