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

From Wikipedia, the free encyclopedia

In post-quantum cryptography, ring learning with errors (RLWE) is a computational problem which serves as the foundation of new cryptographic algorithms, such as NewHope, designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption. Public-key cryptography relies on construction of mathematical problems that are believed to be hard to solve if no further information is available, but are easy to solve if some information used in the problem construction is known. Some problems of this sort that are currently used in cryptography are at risk of attack if sufficiently large quantum computers can ever be built, so resistant problems are sought. Homomorphic encryption is a form of encryption that allows computation on ciphertext, such as arithmetic on numeric values stored in an encrypted database.

RLWE is more properly called learning with errors over rings and is simply the larger learning with errors (LWE) problem specialized to polynomial rings over finite fields.^[1] Because of the presumed difficulty of solving the RLWE problem even on a quantum computer, RLWE based cryptography may form the fundamental base for public-key cryptography in the future just as the integer factorization and discrete logarithm problem have served as the base for public key cryptography since the early 1980s.^[2] An important feature of basing cryptography on the ring learning with errors problem is the fact that the solution to the RLWE problem can be used to solve a version of the shortest vector problem (SVP) in a lattice (a polynomial-time reduction from this SVP problem to the RLWE problem has been presented^[1]).

Background[edit]

The security of modern cryptography, in particular public-key cryptography, is based on the assumed intractability of solving certain computational problems if the size of the problem is large enough and the instance of the problem to be solved is chosen randomly. The classic example that has been used since the 1970s is the integer factorization problem. It is believed that it is computationally intractable to factor the product of two prime numbers if those prime numbers are large enough and chosen at random.^[3] As of 2015 research has led to the factorization of the product of two 384-bit primes but not the product of two 512-bit primes. Integer factorization forms the basis of the widely used RSA cryptographic algorithm.

The ring learning with errors (RLWE) problem is built on the arithmetic of polynomials with coefficients from a finite field.^[1] A typical polynomial is expressed as:

Polynomials can be added and multiplied in the usual fashion. In the RLWE context the coefficients of the polynomials and all operations involving those coefficients will be done in a finite field, typically the field for a prime integer . The set of polynomials over a finite field with the operations of addition and multiplication forms an infinite polynomial ring (). The RLWE context works with a finite quotient ring of this infinite ring. The quotient ring is typically the finite quotient (factor) ring formed by reducing all of the polynomials in modulo an irreducible polynomial . This finite quotient ring can be written as though many authors write .^[1]

If the degree of the polynomial is , the quotient ring becomes the ring of polynomials of degree less than modulo with coefficients from . The values , , together with the polynomial partially define the mathematical context for the RLWE problem.

Another concept necessary for the RLWE problem is the idea of «small» polynomials with respect to some norm. The typical norm used in the RLWE problem is known as the infinity norm (also called the uniform norm). The infinity norm of a polynomial is simply the largest coefficient of the polynomial when these coefficients are viewed as integers. Hence, states that the infinity norm of the polynomial is . Thus is the largest coefficient of .

The final concept necessary to understand the RLWE problem is the generation of random polynomials in and the generation of «small» polynomials . A random polynomial is easily generated by simply randomly sampling the coefficients of the polynomial from , where is typically represented as the set .

Randomly generating a «small» polynomial is done by generating the coefficients of the polynomial from in a way that either guarantees or makes very likely small coefficients. When is a prime integer, there are two common ways to do this:

1. Using Uniform Sampling – The coefficients of the small polynomial are uniformly sampled from a set of small coefficients. Let be an integer that is much less than . If we randomly choose coefficients from the set: the polynomial will be small with respect to the bound ().
2. Using discrete Gaussian sampling – For an odd value for , the coefficients of the polynomial are randomly chosen by sampling from the set according to a discrete Gaussian distribution with mean and distribution parameter . The references describe in full detail how this can be accomplished. It is more complicated than uniform sampling but it allows for a proof of security of the algorithm. The paper «Sampling from Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device» by Dwarakanath and Galbraith provide an overview of this problem.^[4]

The RLWE Problem[edit]

The RLWE problem can be stated in two different ways: a «search» version and a «decision» version. Both begin with the same construction. Let

The Search version entails finding the unknown polynomial given the list of polynomial pairs .

The Decision version of the problem can be stated as follows. Given a list of polynomial pairs , determine whether the polynomials were constructed as or were generated randomly from with coefficients from all of .

The difficulty of this problem is parameterized by the choice of the quotient polynomial (), its degree (), the field (), and the smallness bound (). In many RLWE based public key algorithms the private key will be a pair of small polynomials and . The corresponding public key will be a pair of polynomials , selected randomly from , and the polynomial . Given and , it should be computationally infeasible to recover the polynomial .

Security Reduction[edit]

In cases where the polynomial is a cyclotomic polynomial, the difficulty of solving the search version of RLWE problem is equivalent to finding a short vector (but not necessarily the shortest vector) in an ideal lattice formed from elements of represented as integer vectors.^[1] This problem is commonly known as the Approximate Shortest Vector Problem (α-SVP) and it is the problem of finding a vector shorter than α times the shortest vector. The authors of the proof for this equivalence write:

«… we give a quantum reduction from approximate SVP (in the worst case) on ideal lattices in to the search version of ring-LWE, where the goal is to recover the secret (with high probability, for any ) from arbitrarily many noisy products.»^[1]

In that quote, The ring is and the ring is .

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]

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

Связанные понятия

Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.

Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.

Криптосистема Накаша — Штерна (англ. Naccache — Stern cryptosystem)— криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи дискретного логарифмирования. В отличии от RSA, гомоморфен по сложению и вычитанию, а не по умножению…

Схема шифрования GGH (англ. Goldreich–Goldwasser–Halevi) — асимметричная криптографическая система, основанная на решётках. Также существует схема подписи GGH.

Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.

Постквантовая криптография — часть криптографии, которая остаётся актуальной и при появлении квантовых компьютеров и квантовых атак. Так как по скорости вычисления традиционных криптографических алгоритмов квантовые компьютеры значительно превосходят классические компьютерные архитектуры, современные криптографические системы становятся потенциально уязвимыми к криптографическим атакам. Большинство традиционных криптосистем опирается на проблемы факторизации целых чисел или задачи дискретного логарифмирования…

Разделение секрета (англ. Secret sharing) — термин в криптографии, под которым понимают любой из способов распределения секрета среди группы участников, каждому из которых достаётся своя некая доля. Секрет может воссоздать только коалиция участников из первоначальной группы, причём входить в коалицию должно не менее некоторого изначально известного их числа.

Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться…

Некоммутативная криптография — область криптологии, в которой шифровальные примитивы, методы и системы основаны на некоммутативных алгебраических структурах.

Случайный оракул является весьма мощным, поскольку обладает тремя свойствами: детерминированность, эффективность и обеспечение равномерного распределения результирующих значений.

Ранцевая криптосистема Меркла-Хеллмана, основанная на «задаче о рюкзаке», была разработана Ральфом Мерклем и Мартином Хеллманом в 1978 году. Это была одна из первых криптосистем с открытым ключом, но она оказалась криптографически нестойкой и, как следствие, не приобрела популярности.

Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством.

Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не известно существование субэкспоненциальных алгоритмов решения задачи дискретного логарифмирования.

Сдвиговая атака (англ. slide attack) – криптографическая атака, являющаяся, в общем случае, атакой на основе подобранного открытого текста, позволяющая проводить криптоанализ блоковых многораундовых шифров независимо от количества используемых раундов. Предложена Алексом Бирюковым и Дэвидом Вагнером в 1999 году.

Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 1986 году Харальдом Нидеррайтером. В отличие от криптосистемы McEliece, в криптосистеме Нидеррайтера используется проверочная матрица кода. Криптосистема Нидеррайтера позволяет создавать цифровые подписи и является кандидатом для постквантовой криптографии, поскольку устойчива к атаке с использованием алгоритма Шора.

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов шифрования с открытым ключом, таких как RSA.

Криптосистема — это завершённая комплексная модель, способная производить двусторонние криптопреобразования над данными произвольного объёма и подтверждать время отправки сообщения, обладающая механизмом преобразования паролей, ключей и системой транспортного кодирования.

Криптосистема Гольдвассер — Микали (GM) — криптографическая система с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Однако, криптосистема GM является неэффективной, так как шифртекст может быть в сотни раз длиннее, чем шифруемое сообщение. Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели широко используемое…

Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем.

Универса́льное хеши́рование (англ. Universal hashing) — это вид хеширования, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Такой подход обеспечивает равномерное хеширование: для очередного ключа вероятности помещения его в любую ячейку совпадают. Известно несколько семейств универсальных хеш-функций, которые имеют многочисленные применения в информатике, в частности в хеш-таблицах, вероятностных алгоритмах и криптографии…

Задача о рюкзаке (или Задача о ранце) в криптографии (англ. Knapsack problem) — это задача, на основе которой американские криптографы Ральф Меркл и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом. Он носит название криптосистема Меркла-Хеллмана. Для шифрования сообщений использовалось решение задачи о рюкзаке, как известно, являющейся NP-сложной. Потому, как считалось, она могла обеспечивать криптостойкость системы. На данный момент создано множество рюкзачных криптосистем…

Интегральный криптоанализ — метод криптоанализа, объединяющий ряд атак на симметричные блочные криптографические алгоритмы. В отличие от дифференциального криптоанализа, который рассматривает воздействие алгоритма на пару открытых текстов, интегральный криптоанализ подразумевает исследование отображения в шифротекст множества открытых текстов. Впервые применен в 1997 Ларсом Кнудсеном.

Лемма разветвления (англ. Forking lemma) — лемма в области криптографических исследований.

Разделяй и властвуй (англ. divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.

Полностью гомоморфное шифрование — шифрование, позволяющее для данного шифротекста π1,…,πt любому (не только держателю ключа) получить шифротекст любой желаемой функции f(π1,…,πt), до тех пор, пока данная функция может быть эффективно вычислена.

Криптосистема Джентри (от фамилии создателя Крейга Джентри) — первая возможная конструкция для полностью гомоморфной криптосистемы, основанная на криптографии на решетках. Впервые была предложена Крейгом Джентри в 2009 году и являлась темой его докторской диссертации. Схема Джентри поддерживает операции сложения и умножения над шифротекстом, что позволяет построить кольца для реализации любых произвольных вычислений. Впоследствии имела множество доработок и модификаций с целью улучшения её производительности…

Алгоритмы быстрого возведения в степень по модулю — разновидность алгоритмов возведения в степень по модулю, широко использующихся в различных криптосистемах, для ускорения вычислительных операций с большими числами.

Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется…

Геометрическая криптография — теоретические криптографические методы, в которых сообщения и шифротексты представлены в виде геометрических величин: углов, отрезков, а вычисления проводятся с помощью циркуля и линейки. Основана на сложности решения определенного класса геометрических задач, например, трисекции угла.

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

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

Вероятностный алгоритм — алгоритм, предусматривающий обращение на определённых этапах своей работы к генератору случайных чисел с целью получения экономии во времени работы за счёт замены абсолютной достоверности результата достоверностью с некоторой вероятностью.

Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения…

Семплирование по Гиббсу — алгоритм для генерации выборки совместного распределения множества случайных величин. Он используется для оценки совместного распределения и для вычисления интегралов методом Монте-Карло. Этот алгоритм является частным случаем алгоритма Метрополиса-Гастингса и назван в честь физика Джозайи Гиббса.

Неразличимость шифротекста — это свойство многих систем шифрования. Интуитивно понятно, что если система обладает свойством неразличимости, то злоумышленник не сможет отличить пары шифротекстов, основываясь на открытых текстах, которые они шифруют. Свойство неразличимости для атак на основе подобранного открытого текста рассматривается как основное требование для доказуемо наиболее безопасных криптосистем с открытым ключом, хотя некоторые системы шифрования также обладают свойством неразличимости…

Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.

Атака Копперсмита описывает класс криптографических атак на открытый ключ криптосистемы RSA, основанный на методе Копперсмита. Особенность применения этого метода для атак RSA включает случаи, когда открытая экспонента мала или когда частично известен секретный ключ.

Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) — это криптографически стойкий алогоритм генерации псевдослучайных последовательностей, с использованием зерна (Random seed). Идеи алгоритма были изложены Блюмом и Микали в 1984 году. Алгоритм был разработан на основе алгоритма генератора Шамира, предложенного Ади Шамиром годом ранее. Алгоритм отличается от предшественника более сильными требованиями к сложности вычисления выходной последовательности. В отличие от генератора Шамира выходом данного…

Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.

Криптографические примитивы — низкоуровневые криптографические алгоритмы, которые часто используются для построения криптографических протоколов. В узком смысле это операции и процедуры, определяющие требуемые свойства криптосистемы.

Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предопределённый результат для заданных входных данных.

Поиск с возвратом, бэктрекинг (англ. backtracking) — общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.

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

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

Фон

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

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

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

Если степень полинома равна , подкольцо становится кольцом многочленов степени меньше, чем по модулю, с коэффициентами из . Значения , вместе с полиномом частично определить математический контекст проблемы RLWE.

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

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

Случайная генерация «малого» полинома выполняется путем генерации коэффициентов полинома таким способом, который либо гарантирует, либо делает очень вероятные малые коэффициенты. Это можно сделать двумя распространенными способами:

1. Использование равномерной выборки — коэффициенты малого полинома равномерно выбираются из набора малых коэффициентов. Позвольте быть целым числом, которое намного меньше, чем . Если случайным образом выбрать коэффициенты из набора: многочлен будет мал по отношению к границе ( ).
2. Использование дискретной гауссовой выборки — для нечетного значения коэффициенты полинома выбираются случайным образом путем выборки из набора в соответствии с дискретным гауссовым распределением со средним значением и параметром распределения . Ссылки подробно описывают, как это можно сделать. Это сложнее, чем единообразная выборка, но позволяет подтвердить безопасность алгоритма. В статье Двараканата и Гэлбрейта «Выборка из дискретных гауссианов для криптографии на основе решеток на устройстве с ограничениями» представлен обзор этой проблемы.

Проблема RLWE

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

Версия поиска влечет за собой поиск неизвестного многочлена по списку пар многочленов .

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

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

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

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

«… мы даем квантовую редукцию от приближенного SVP (в худшем случае) на идеальных решетках в поисковую версию ring-LWE, где цель — восстановить секрет (с большой вероятностью, для любого ) из произвольного множества шумные продукты «.

В этой цитате кольцо есть, а кольцо есть .

Известно, что α-SVP в регулярных решетках является NP-трудным из-за работы Даниэле Миччансио в 2001 году, хотя и не для значений α, необходимых для сведения к общей проблеме обучения с ошибками. Однако пока нет доказательства того, что сложность α-SVP для идеальных решеток эквивалентна средней сложности α-SVP. Скорее у нас есть доказательство того, что если есть какие- либо экземпляры α-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 обмена ключами Диффи-Хеллмана была позже опубликована Zhang et al. Безопасность обоих обменов ключами напрямую связана с проблемой поиска приближенных коротких векторов в идеальной решетке.

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

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

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

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

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

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

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

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

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