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

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

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

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

Фон [ править ]

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

Задача кольцевого обучения с ошибками (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 коэффициенты многочленов и все операции с этими коэффициентами будут выполняться в конечном поле, обычно поле для простого целого числа . Набор многочленов над конечным полем с операциями сложения и умножения образует бесконечное кольцо многочленов ( ). Контекст RLWE работает с конечным кольцом частных этого бесконечного кольца. Фактор-кольцо обычно представляет собой конечное фактор-кольцо (фактор-кольцо), образованное сокращением всех многочленов по модулю неприводимого многочлена . Это конечное кольцо частных можно записать так, как будто пишут многие авторы . ^[1]${\textstyle \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q}}$${\textstyle q}$${\textstyle \mathbf {F} _{q}[x]}$${\textstyle \mathbf {F} _{q}[x]}$ ${\textstyle \Phi (x)}$${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$${\displaystyle \mathbf {Z} _{q}[x]/\Phi (x)}$

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

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

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

Проблема RLWE [ править ]

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

• ${\displaystyle a_{i}(x)}$- набор случайных, но известных многочленов из с коэффициентами из всех .${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$${\displaystyle \mathbf {F} _{q}}$
• ${\displaystyle e_{i}(x)}$- набор малых случайных и неизвестных многочленов относительно границы в кольце .${\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 (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 \mathbf {F} _{q}[x]/\Phi (x)}$${\displaystyle \mathbf {F} _{q}}$

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

Снижение безопасности [ править ]

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

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

В этой цитате кольцо есть, а кольцо есть .${\displaystyle \mathbf {R} }$${\displaystyle \mathbf {Z} [x]/\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 Cryptography [ править ]

Основное преимущество криптографии на основе 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] представил ключевую транспортную схему, следуя той же базовой идее Динга, где также используется новая идея отправки дополнительного 1-битного сигнала для округления в конструкции Динга. RLWE-версия классического варианта MQV обмена ключами Диффи-Хеллмана была позже опубликована Zhang et al. ^[13] Безопасность обоих обменов ключами напрямую связана с проблемой поиска приближенных коротких векторов в идеальной решетке.

Обучение звонку с сигнатурой ошибок (RLWE-SIG) [ править ]

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

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

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

Ссылки [ править ]