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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Сентябрь 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 a(x)}$

${\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 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)}$

"... we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in ${\displaystyle \mathbf {R} }$ to the search version of ring-LWE, where the goal is to recover the secret ${\displaystyle s\in \mathbf {R} _{q}}$ (with high probability, for any ${\displaystyle s}$) from arbitrarily many noisy products."^[1]

In that quote, The ring ${\displaystyle \mathbf {R} }$ is ${\displaystyle \mathbf {Z} [x]/\Phi (x)}$ and the ring ${\displaystyle \mathbf {R} _{q}}$ is ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$.

The α-SVP in regular lattices is known to be NP-hard due to work by Daniele Micciancio in 2001, although not for values of α required for a reduction to general learning with errors problem.^[5] However, there is not yet a proof to show that the difficulty of the α-SVP for ideal lattices is equivalent to the average α-SVP. Rather we have a proof that if there are any α-SVP instances that are hard to solve in ideal lattices then the RLWE Problem will be hard in random instances.^[1]

Regarding the difficulty of Shortest Vector Problems in Ideal Lattices, researcher Michael Schneider writes, "So far there is no SVP algorithm making use of the special structure of ideal lattices. It is widely believed that solving SVP (and all other lattice problems) in ideal lattices is as hard as in regular lattices."^[6] The difficulty of these problems on regular lattices is provably NP-hard.^[5] There are, however, a minority of researchers who do not believe that ideal lattices share the same security properties as regular lattices.^[7]

Peikert believes that these security equivalences make the RLWE problem a good basis for future cryptography. He writes: "There is a mathematical proof that the only way to break the cryptosystem (within some formal attack model) on its random instances is by being able to solve the underlying lattice problem in the worst case" (emphasis in the original).^[8]

RLWE Cryptography[edit]

A major advantage that RLWE based cryptography has over the original learning with errors (LWE) based cryptography is found in the size of the public and private keys. RLWE keys are roughly the square root of keys in LWE.^[1] For 128 bits of security an RLWE cryptographic algorithm would use public keys around 7000 bits in length.^[9] The corresponding LWE scheme would require public keys of 49 million bits for the same level of security.^{[1][failed verification]} On the other hand, RLWE keys are larger than the keys sizes for currently used public key algorithms like RSA and Elliptic Curve Diffie-Hellman which require public key sizes of 3072 bits and 256 bits, respectively, to achieve a 128-bit level of security. From a computational standpoint, however, RLWE algorithms have been shown to be the equal of or better than existing public key systems.^[10]

Three groups of RLWE cryptographic algorithms exist:

Ring learning with errors key exchanges (RLWE-KEX)[edit]

The fundamental idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The basic idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper^[11] appeared in 2012 after a provisional patent application was filed in 2012.

In 2014, Peikert^[12] presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional 1 bit signal for rounding in Ding's construction is also utilized. An RLWE version of the classic MQV variant of a Diffie-Hellman key exchange was later published by Zhang et al.^[13] The security of both key exchanges is directly related to the problem of finding approximate short vectors in an ideal lattice.

Ring learning with errors signature (RLWE-SIG)[edit]

A RLWE version of the classic Feige–Fiat–Shamir Identification protocol was created and converted to a digital signature in 2011 by Lyubashevsky.^[14] The details of this signature were extended in 2012 by Gunesyu, Lyubashevsky, and Popplemann in 2012 and published in their paper "Practical Lattice Based Cryptography – A Signature Scheme for Embedded Systems."^[15] These papers laid the groundwork for a variety of recent signature algorithms some based directly on the ring learning with errors problem and some which are not tied to the same hard RLWE problems.^[16]

Ring learning with errors homomorphic encryption (RLWE-HOM)[edit]

The purpose of homomorphic encryption is to allow the computations on sensitive data to occur on computing devices that should not be trusted with the data. These computing devices are allowed to process the ciphertext which is output from a homomorphic encryption. In 2011, Brakersky and Vaikuntanathan, published "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages" which builds a homomorphic encryption scheme directly on the RLWE problem.^[17]

References[edit]