Кольцевое обучение с ошибками
Вычислительная задача, возможно, полезная для постквантовой криптографии

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

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

Фон

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

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

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

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

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

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

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

  1. Использование равномерной выборки – Коэффициенты малого многочлена равномерно выбираются из набора малых коэффициентов. Пусть будет целым числом, которое намного меньше . Если мы случайным образом выберем коэффициенты из набора: многочлен будет малым относительно границы ( ). б {\textstyle б} д {\textstyle д} { − б , − б + 1 , − б + 2 , … , − 2 , − 1 , 0 , 1 , 2 , … , б − 2 , б − 1 , б } {\textstyle \{-b,-b+1,-b+2,\ldots ,-2,-1,0,1,2,\ldots ,b-2,b-1,b\}} б {\textstyle б}
  2. Использование дискретной гауссовой выборки – Для нечетного значения для коэффициенты полинома выбираются случайным образом путем выборки из набора в соответствии с дискретным гауссовым распределением со средним значением и параметром распределения . В ссылках подробно описано, как это можно сделать. Это сложнее, чем равномерная выборка, но позволяет доказать безопасность алгоритма. В статье «Выборка из дискретных гауссовских функций для решеточной криптографии на ограниченном устройстве» Двараканата и Гэлбрейта дается обзор этой проблемы. [4] д {\textstyle д} { − ( д − 1 ) / 2 , … , ( д − 1 ) / 2 } {\textstyle \{-(q-1)/2,\ldots ,(q-1)/2\}} 0 {\displaystyle 0} σ {\textstyle \сигма}

Проблема RLWE

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

  • а я ( х ) {\displaystyle a_{i}(x)} быть набором случайных, но известных полиномов из с коэффициентами из всех . Ф д [ х ] / Ф ( х ) {\displaystyle \mathbf {F} _{q}[x]/\Phi (x)} Ф д {\displaystyle \mathbf {F} _{q}}
  • е я ( х ) {\displaystyle e_{i}(x)} быть набором малых случайных и неизвестных полиномов относительно границы в кольце . б {\displaystyle б} Ф д [ х ] / Ф ( х ) {\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}
  • с ( х ) {\displaystyle s(x)} быть малым неизвестным многочленом относительно границы в кольце . б {\displaystyle б} Ф д [ х ] / Ф ( х ) {\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 \Фи (x)} н {\displaystyle n} Ф д {\displaystyle \mathbf {F} _{q}} б {\displaystyle б} с ( х ) {\displaystyle s(x)} е ( х ) {\displaystyle е(х)} а ( х ) {\displaystyle а(х)} Ф д [ х ] / Ф ( х ) {\displaystyle \mathbf {F} _{q}[x]/\Phi (x)} т ( х ) = ( а ( х ) ⋅ с ( х ) ) + е ( х ) {\displaystyle t(x)=(a(x)\cdot s(x))+e(x)} а ( х ) {\displaystyle а(х)} т ( х ) {\displaystyle t(x)} с ( х ) {\displaystyle s(x)}

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

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

«... мы даем квантовое сокращение от приближенного SVP (в худшем случае) на идеальных решетках к поисковой версии кольцевого LWE, где целью является восстановление секрета (с высокой вероятностью для любого ) из произвольного числа зашумленных продуктов». Р {\displaystyle \mathbf {R} } с ∈ Р д {\displaystyle s\in \mathbf {R} _{q}} с {\displaystyle с} [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

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

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

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

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

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

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

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

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

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

Ссылки

  1. ^ abcdefghi Любашевский, Вадим; Пейкерт, Крис; Регев, Одед (2012). «Об идеальных решетках и обучении с ошибками над кольцами». Архив Cryptology ePrint .
  2. ^ Peikert, Chris (2014). «Криптография решеток для Интернета». В Mosca, Michele (ред.). Постквантовая криптография . Конспект лекций по информатике. Том 8772. Springer International Publishing. С.  197–219 . CiteSeerX 10.1.1.800.4743 . doi :10.1007/978-3-319-11659-4_12. ISBN  978-3-319-11658-7. S2CID  8123895.
  3. ^ Шор, Питер (20 ноября 1994 г.). Алгоритмы квантовых вычислений: дискретные логарифмы и факторизация . 35-й ежегодный симпозиум по основам компьютерной науки. Санта-Фе: IEEE. doi :10.1109/SFCS.1994.365700. ISBN 0-8186-6580-7. В этой статье приводятся алгоритмы Лас-Вегаса для поиска дискретных логарифмов и факторизации целых чисел на квантовом компьютере, которые выполняют ряд шагов, полиномиальных по размеру входных данных, например, количеству цифр факторизуемого целого числа. Эти две проблемы обычно считаются сложными для классического компьютера и были использованы в качестве основы для нескольких предлагаемых криптосистем.
  4. ^ Двараканат, Нагарджун С.; Гэлбрейт, Стивен Д. (2014-03-18). «Выборка из дискретных гауссианов для криптографии на основе решетки на ограниченном устройстве». Прикладная алгебра в инженерии, связи и вычислениях . 25 (3): 159– 180. CiteSeerX 10.1.1.716.376 . doi :10.1007/s00200-014-0218-3. ISSN  0938-1279. S2CID  13718364. 
  5. ^ ab Micciancio, D. (1 января 2001 г.). «Самый короткий вектор в решетке трудно приблизить с точностью до некоторой константы». SIAM Journal on Computing . 30 (6): 2008–2035 . CiteSeerX 10.1.1.93.6646 . doi :10.1137/S0097539700373039. ISSN  0097-5397. 
  6. ^ Шнайдер, Майкл (2011). «Просеивание для кратчайших векторов в идеальных решетках». Архив Cryptology ePrint .
  7. ^ "cr.yp.to: 2014.02.13: Атака подполя-логарифма против идеальных решеток". blog.cr.yp.to . Получено 2015-07-03 .
  8. ^ «Что означает «предостерегающая история» GCHQ для решетчатой ​​криптографии?». www.eecs.umich.edu . Архивировано из оригинала 2016-03-17 . Получено 2016-01-05 .
  9. ^ Сингх, Викрам (2015). «Практический обмен ключами для Интернета с использованием решетчатой ​​криптографии». Архив Cryptology ePrint .
  10. ^ Вербаухеде, Руан де Клерк, Суджой Синха Рой, Фредерик Веркаутерен, Ингрид (2014). «Эффективная программная реализация шифрования Ring-LWE». Архив электронной печати по криптологии .{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  11. ^ Дин, Цзиньтай; Се, Сян; Линь, Сяодун (2012-01-01). «Простая доказуемо безопасная схема обмена ключами, основанная на проблеме обучения с ошибками». Архив Cryptology ePrint .
  12. ^ Пейкерт, Крис (2014-01-01). "Решеточная криптография для Интернета". Архив Cryptology ePrint .
  13. ^ Чжан, Цзян; Чжан, Чжэньфэн; Дин, Цзиньтай; Снук, Майкл; Дагделен, Озгюр (2014). «Аутентифицированный обмен ключами из идеальных решеток». Архив Cryptology ePrint .
  14. ^ Любашевский, Вадим (2011). «Решетчатые подписи без лазеек». Архив Cryptology ePrint .
  15. ^ Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). Prouff, Emmanuel; Schaumont, Patrick (ред.). Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems . Lecture Notes in Computer Science. Springer Berlin Heidelberg. стр.  530– 547. doi :10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1.
  16. ^ "Схема подписи BLISS". bliss.di.ens.fr . Получено 2015-07-04 .
  17. ^ Brakerski, Zvika; Vaikuntanathan, Vinod (2011). Rogaway, Phillip (ред.). Полностью гомоморфное шифрование с помощью Ring-LWE и безопасность сообщений, зависящих от ключей . Конспект лекций по информатике. Springer Berlin Heidelberg. стр.  505– 524. doi :10.1007/978-3-642-22792-9_29. ISBN 978-3-642-22791-2.
Взято с "https://en.wikipedia.org/w/index.php?title=Кольцевое_обучение_с_ошибками&oldid=1257213239"