Кольцевое обучение с ошибками - Ring learning with errors

эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Сентябрь 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Задний план

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

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

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

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

Еще одна концепция, необходимая для задачи RLWE, - это идея «малых» многочленов относительно некоторой нормы. Типичная норма, используемая в задаче RLWE, известна как норма бесконечности (также называемая нормой бесконечности). единая норма ). Бесконечная норма полинома - это просто наибольший коэффициент полинома, когда эти коэффициенты рассматриваются как целые числа. Следовательно, ${ Displaystyle || а (х) || _ { infty} = b}$ утверждает, что бесконечная норма многочлена ${ Displaystyle а (х)}$ является ${ displaystyle b}$. Таким образом ${ displaystyle b}$ - наибольший коэффициент ${ Displaystyle а (х)}$.

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

Случайное создание «малого» полинома осуществляется путем генерации коэффициентов полинома из ${ displaystyle 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 {- (д-1) / 2, ldots, (д-1) / 2 }}$ согласно дискретному распределению Гаусса со средним ${ displaystyle 0}$ и параметр распределения ${ textstyle sigma}$. Ссылки подробно описывают, как это можно сделать. Это сложнее, чем единообразная выборка, но позволяет подтвердить безопасность алгоритма. В статье Двараканата и Гэлбрейта «Выборка из дискретных гауссианов для криптографии на основе решеток на устройстве с ограничениями» представлен обзор этой проблемы.^[4]

Проблема RLWE

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

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

Версия поиска предполагает нахождение неизвестного многочлена ${ displaystyle s (x)}$ учитывая список пар полиномов ${ Displaystyle (а_ {я} (х), b_ {я} (х))}$.

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

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

Снижение безопасности

В случаях, когда многочлен ${ Displaystyle Phi (х)}$ это круговой полином, трудность решения поискового варианта задачи RLWE эквивалентна нахождению короткого вектора (но не обязательно кратчайшего вектора) в идеальной решетке, образованной из элементов ${ Displaystyle mathbf {Z} [х] / Phi (x)}$ представлены как целые векторы.^[1] Эта проблема широко известна как Приближенная задача наикратчайшего вектора (α-SVP) и это проблема поиска вектора короче, чем кратчайший вектор в α. Авторы доказательства этой эквивалентности пишут:

«... мы даем квантовую редукцию из приближенной SVP (в худшем случае) на идеальных решетках в ${ displaystyle mathbf {R}}$ в поисковую версию ring-LWE, где цель - восстановить секрет ${ displaystyle s in mathbf {R} _ {q}}$ (с большой вероятностью для любого ${ displaystyle s}$) от сколь угодно шумных продуктов ".^[1]

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

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

Что касается сложности задач наикратчайших векторов в идеальных решетках, исследователь Майкл Шнайдер пишет: «Пока нет алгоритма SVP, использующего особую структуру идеальных решеток. Широко распространено мнение, что решение SVP (и всех других решеточных задач) в идеальных решетках так же сложно, как и в обычных решетках».^[6] Трудность этих задач на регулярных решетках доказуемо NP-жесткий.^[5] Однако есть меньшинство исследователей, которые не верят, что идеальные решетки обладают теми же свойствами безопасности, что и обычные решетки.^[7]

Пайкерт считает, что эти эквиваленты безопасности делают проблему RLWE хорошей основой для будущей криптографии. Он написал: "Есть математическое доказательство того, что только способ взломать криптосистему (в рамках некоторой формальной модели атаки) на ее случайных экземплярах заключается в том, чтобы решить основную проблему решетки в худший случай" (курсив в оригинале).^[8]

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

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

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

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

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

В 2014 году Пайкерт^[12] представил ключевую транспортную схему, следуя той же базовой идее Динга, где также используется новая идея отправки дополнительного однобитового сигнала для округления в конструкции Динга. Версия RLWE классического варианта MQV обмена ключами Диффи-Хеллмана была позже опубликована Zhang et al.^[13] Безопасность обоих обменов ключами напрямую связана с проблемой поиска приближенных коротких векторов в идеальной решетке.

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

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

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

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

использованная литература