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

В постквантовой криптографии кольцевое обучение с ошибками ( RLWE ) — это вычислительная задача , которая служит основой новых криптографических алгоритмов , таких как NewHope , предназначенных для защиты от криптоанализа с помощью квантовых компьютеров , а также обеспечивающих основу для гомоморфного шифрования . Криптография с открытым ключом основана на построении математических задач, которые, как полагают, трудно решить, если нет дополнительной информации, но которые легко решить, если известна некоторая информация, использованная при построении проблемы. Некоторые проблемы такого рода, которые в настоящее время используются в криптографии, могут подвергнуться риску атаки, если когда-либо удастся построить достаточно большие квантовые компьютеры, поэтому ведется поиск устойчивых проблем. Гомоморфное шифрование — это форма шифрования, которая позволяет выполнять вычисления с зашифрованным текстом, например арифметические операции с числовыми значениями, хранящимися в зашифрованной базе данных.

RLWE правильнее называть обучением с ошибками над кольцами и представляет собой просто более широкую задачу обучения с ошибками (LWE), специализирующуюся на кольцах полиномов над конечными полями. Из-за предполагаемой сложности решения проблемы RLWE даже на квантовом компьютере криптография на основе RLWE может сформировать фундаментальную основу для криптографии с открытым ключом в будущем, точно так же, как задача целочисленной факторизации и дискретного логарифма послужила основой для криптографии с открытым ключом. с начала 1980-х годов. Важной особенностью основы криптографии на проблеме кольцевого обучения с ошибками является тот факт, что решение проблемы RLWE может быть использовано для решения версии задачи о кратчайшем векторе (SVP) в решетке (полиномиальное сокращение по времени от этой SVP). проблема с проблемой RLWE была представлена ).

Фон

Безопасность современной криптографии, в частности криптографии с открытым ключом , основана на предполагаемой неразрешимости решения определенных вычислительных задач, если размер проблемы достаточно велик и экземпляр решаемой проблемы выбирается случайным образом. Классический пример, который использовался с 1970-х годов, — это задача факторизации целых чисел . Считается, что с вычислительной точки зрения невозможно факторизовать произведение двух простых чисел, если эти простые числа достаточно велики и выбраны случайным образом. По состоянию на 2015 год исследования привели к факторизации произведения двух 384-битных простых чисел, но не произведения двух 512-битных простых чисел. Целочисленная факторизация составляет основу широко используемого криптографического алгоритма RSA .

Задача кольцевого обучения с ошибками (RLWE) построена на арифметике многочленов с коэффициентами из конечного поля . Типичный полином ${\textstyle a(x)}$ выражается как:

$a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-2}x^{n-2}+a_{n-1}x^{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)$ хотя многие авторы пишут $\mathbf {Z} _{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 {F} _{q}[x]/\Phi (x)$ и генерация «маленьких» полиномов. Случайный полином легко генерируется путем простой случайной выборки $n$ коэффициенты полинома от $\mathbf {F} _{q}$, где $\mathbf {F} _{q}$ обычно представляется в виде набора $\{-(q-1)/2,...,-1,0,1,...,(q-1)/2\}$.

Случайная генерация «маленького» полинома осуществляется путем генерации коэффициентов полинома из $\mathbf {F} _{q}$ таким образом, что либо гарантирует, либо делает весьма вероятными небольшие коэффициенты. Когда $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

Проблему RLWE можно сформулировать двумя разными способами: версией «поиска» и версией «решения». Оба начинаются с одной и той же конструкции. Позволять

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

Версия поиска предполагает поиск неизвестного полинома. $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 {F} _{q}[x]/\Phi (x)$ с коэффициентами от всех $\mathbf {F} _{q}$.

Сложность этой задачи параметризуется выбором фактор-полинома ( $\Phi (x)$), его степень ( $n$), поле ( $\mathbf {F} _{q}$) и граница малости ( $b$). Во многих алгоритмах открытого ключа, основанных на RLWE, закрытый ключ представляет собой пару небольших полиномов. $s(x)$ и $e(x)$. Соответствующий открытый ключ будет представлять собой пару полиномов. $a(x)$, выбранный случайным образом из $\mathbf {F} _{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)$ представлены в виде целочисленных векторов. Эта проблема широко известна как задача о приближенном кратчайшем векторе (α-SVP) и представляет собой проблему нахождения вектора короче, чем в α раз кратчайший вектор. Авторы доказательства этой эквивалентности пишут:

«...мы даем квантовую редукцию от приближенного СВП (в худшем случае) на идеальных решетках в $\mathbf {R}$ к поисковой версии Ring-LWE, целью которой является восстановление секрета $s\in \mathbf {R} _{q}$ (с большой вероятностью для любого $s$) от произвольного количества шумных продуктов».

В этой цитате Кольцо $\mathbf {R}$ является $\mathbf {Z} [x]/\Phi (x)$ и кольцо $\mathbf {R} _{q}$ является $\mathbf {F} _{q}[x]/\Phi (x)$.

Известно, что α-SVP в регулярных решетках является NP-трудной благодаря работе Даниэле Миччанчо в 2001 году, хотя и не для значений α, необходимых для сведения к общей проблеме обучения с ошибками. Однако пока нет доказательства того, что сложность α-СВП для идеальных решеток эквивалентна средней сложности α-СВП. Скорее, у нас есть доказательство того, что если существуют какие-либо случаи α-SVP, которые трудно решить в идеальных решетках, то проблема RLWE будет сложной в случайных случаях.

Что касается сложности решения задач о кратчайших векторах в идеальных решетках, исследователь Майкл Шнайдер пишет: «До сих пор не существует алгоритма SVP, использующего специальную структуру идеальных решеток. Широко распространено мнение, что решение SVP (и всех других задач о решетках) в идеальных решетки такие же твердые, как и обычные решетки». Сложность этих задач на регулярных решетках доказуемо NP-трудна . Однако есть меньшинство исследователей, которые не верят, что идеальные решетки обладают теми же свойствами безопасности, что и обычные решетки.

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

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

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

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

Кольцевое обучение с ошибками обмена ключами (RLWE-KEX)

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

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

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

Кольцевое обучение с сигнатурой ошибок (RLWE-SIG)

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

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

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

Основная статья: Гомоморфное шифрование

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