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

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

Фон

С 1980-х годов безопасность обмена криптографическими ключами и цифровых подписей через Интернет в первую очередь основывалась на небольшом количестве алгоритмов открытого ключа . Безопасность этих алгоритмов основана на столь же небольшом количестве вычислительно сложных задач в классических вычислениях. Этими задачами являются сложность факторизации произведения двух тщательно выбранных простых чисел , сложность вычисления дискретных логарифмов в тщательно выбранном конечном поле и сложность вычисления дискретных логарифмов в тщательно выбранной группе эллиптических кривых . Эти задачи очень сложно решить на классическом компьютере (тип компьютера, известный миру с 1940-х годов и по сей день), но их довольно легко решить с помощью относительно небольшого квантового компьютера, использующего всего от 5 до 10 тысяч бит памяти. В компьютерной индустрии есть оптимизм относительно того, что более масштабные квантовые компьютеры будут доступны около 2030 года. Если бы был построен квантовый компьютер достаточного размера, все алгоритмы открытого ключа, основанные на этих трех классически сложных задачах, были бы небезопасными. Эта криптография с открытым ключом используется сегодня для защиты веб-сайтов в Интернете, защиты информации для входа в систему компьютера и предотвращения установки на наши компьютеры вредоносного программного обеспечения.

Криптография, которая не подвержена атакам квантового компьютера, называется квантово-безопасной или постквантовой криптографией . Один класс квантово-устойчивых криптографических алгоритмов основан на концепции, называемой « обучение с ошибками », введенной Одедом Регевым в 2005 году. ^[1] Специализированная форма обучения с ошибками работает в кольце полиномов над конечным полем . Эта специализированная форма называется кольцевым обучением с ошибками или RLWE .

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

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

Обмен ключами RLWE разработан как « квантовая безопасная » замена широко используемых обменов ключами Диффи–Хеллмана и эллиптических кривых Диффи–Хеллмана , которые используются для обеспечения установления секретных ключей по ненадежным каналам связи. Как и Диффи–Хеллман и Диффи–Хеллман на эллиптических кривых, обмен ключами Ring-LWE обеспечивает криптографическое свойство, называемое « прямой секретностью »; цель которого — снизить эффективность программ массового наблюдения и гарантировать, что нет долгосрочных секретных ключей, которые могут быть скомпрометированы, что позволило бы выполнить массовое дешифрование.

Введение

Начиная с простого целого числа q, обмен ключами Ring-LWE работает в кольце многочленов по модулю многочлена с коэффициентами в поле целых чисел mod q (т.е. в кольце ). Умножение и сложение многочленов будут работать обычным образом с результатами умножения, уменьшенными по mod . ${\displaystyle \Phi (x)}$ ${\displaystyle R_{q}:=Z_{q}[x]/\Phi (x)}$ ${\displaystyle \Phi (x)}$

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

В 2014 году Пейкерт представил схему передачи ключей ^[3], основанную на той же базовой идее Дина, где также используется новая идея отправки дополнительного 1-битного сигнала для округления в конструкции Дина.

Реализация «Новой надежды» ^[4], выбранная для постквантового эксперимента Google ^[5] , использует схему Пейкерта с вариацией распределения ошибок.

Для немного большей, чем 128 бит безопасности , Сингх представляет набор параметров, которые имеют 6956-битные открытые ключи для схемы Пейкерта. ^[6] Соответствующий закрытый ключ будет иметь длину примерно 14 000 бит. Версия RLWE классического варианта MQV обмена ключами Диффи–Хеллмана была позже опубликована Чжаном и др. в 2014 году. Безопасность обоих обменов ключами напрямую связана с проблемой нахождения приближенных коротких векторов в идеальной решетке. Эта статья будет тесно связана с работой RLWE Дина в «Простой доказуемо безопасной схеме обмена ключами, основанной на проблеме обучения с ошибками». ^[2] Для этого представления типичный полином выражается как:

${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n-3}x^{n-3}+a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}$

Коэффициенты этого многочлена являются целыми числами mod  q . Многочлен будет циклотомическим многочленом . Когда n является степенью 2, то ^{[6] [7]} ${\displaystyle a_{i}}$ ${\displaystyle \Phi (x)}$ ${\displaystyle \Phi (x)=x^{n}+1.}$

RLWE-KEX использует полиномы, которые считаются «малыми» относительно меры, называемой « нормой бесконечности ». Норма бесконечности для полинома — это просто значение наибольшего коэффициента полинома, когда коэффициенты рассматриваются как целые числа в Z, а не (т.е. из набора {−( q  − 1)/2,..., 0, ... ( q  − 1)/2} ). Безопасность алгоритма зависит от способности генерировать случайные полиномы, которые малы относительно нормы бесконечности. Это делается просто путем случайной генерации коэффициентов для полинома (s _n-1 , ..., s ₀ ), которые гарантированно или с большой вероятностью будут малыми. Есть два распространенных способа сделать это: ${\displaystyle Zq}$

1. Использование равномерной выборки – коэффициенты малого многочлена равномерно выбираются из набора малых коэффициентов. Пусть b будет целым числом, которое намного меньше q . Если мы случайным образом выберем коэффициенты из набора: { − b , −b + 1, −b + 2. ... −2, −1, 0, 1, 2, ... , b  − 2, b  − 1, b }, многочлен будет малым относительно границы (b). Сингх предлагает использовать b = 5. ^[6] Таким образом, коэффициенты будут выбираться из набора { q  − 5, q  − 4, q  − 3, q  ​​− 2, q  − 1, 0, 1, 2, 3, 4, 5 }.
2. Использование дискретной гауссовой выборки – для нечетного значения q коэффициенты выбираются случайным образом путем выборки из набора { −(q − 1)/2 до ( q  − 1)/2 } в соответствии с дискретным гауссовым распределением со средним значением 0 и параметром распределения  σ . В ссылках подробно описано, как это можно сделать. Это сложнее, чем равномерная выборка, но позволяет доказать безопасность алгоритма. Обзор гауссовой выборки можно найти в презентации Пейкерта. ^[8]

В оставшейся части этой статьи случайные малые многочлены будут выбираться в соответствии с распределением, которое просто указывается как D. Далее q будет нечетным простым числом, таким, что q будет конгруэнтно 1 mod 4 и 1 mod 2n. Другие случаи для q и n подробно обсуждаются в "A Toolkit for Ring-LWE Cryptography" и в "Even More Practical Key Exchange for the Internet using Lattice Cryptography" Сингха. ^{[9] [10]} и другой статье Сингха. Фиксированный публичный многочлен a(x), общий для всех пользователей сети. Он детерминированно генерируется из криптографически безопасного источника.

Учитывая a ( x ), как указано, мы можем случайным образом выбрать малые многочлены s ( x ) и e ( x ) в качестве «закрытого ключа» в обмене открытым ключом. Соответствующий открытый ключ будет многочленом p ( x ) = a ( x ) s ( x ) + 2 e ( x ).

Обмен ключами

Обмен ключами будет происходить между двумя устройствами. Будет инициатор обмена ключами, обозначенный как (I), и респондент, обозначенный как (R). И I, и R знают q , n , a ( x ) и имеют возможность генерировать небольшие полиномы в соответствии с распределением с параметром . Распределение обычно представляет собой дискретное гауссовское распределение на кольце . Нижеследующее описание не содержит никаких объяснений того, почему обмен ключами приводит к одному и тому же ключу на обоих концах связи. Вместо этого оно кратко указывает шаги, которые необходимо предпринять. Для полного понимания того, почему обмен ключами приводит к тому, что инициатор и респондент имеют один и тот же ключ, читатель должен ознакомиться с упомянутой работой Дина и др. ^[2]. ${\displaystyle \chi _{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \chi _{\alpha }}$ ${\displaystyle R_{q}=Z_{q}[x]/\Phi (x)}$

Обмен ключами начинается с того, что инициатор (I) выполняет следующие действия:

Посвящение:

1. Сгенерировать два полинома и с малыми коэффициентами путем выборки из распределения . ${\displaystyle s_{I}}$ ${\displaystyle e_{I}}$ ${\displaystyle \chi _{\alpha }}$
2. Вычислить ${\displaystyle p_{I}=as_{I}+2e_{I}.}$
3. Инициатор отправляет полином Ответчику. ${\displaystyle p_{I}}$

Ответ:

1. Сгенерировать два полинома и с малыми коэффициентами путем выборки из распределения . ${\displaystyle s_{R}}$ ${\displaystyle e_{R}}$ ${\displaystyle \chi _{\alpha }}$
2. Вычислить . ${\displaystyle p_{R}=as_{R}+2e_{R}}$
3. Сгенерировать небольшое из . Вычислить . Затем . ${\displaystyle e'_{R}}$ ${\displaystyle \chi _{\alpha }}$ ${\displaystyle k_{R}=p_{I}s_{R}+2e'_{R}}$ ${\displaystyle k_{R}=as_{I}s_{R}+2e_{I}s_{R}+2e'_{R}}$
4. Используйте функцию сигнала , чтобы найти . Это вычисляется путем применения функции к каждому коэффициенту ${\displaystyle \operatorname {Sig} }$ ${\displaystyle w=\operatorname {Sig} (k_{R})}$ ${\displaystyle Sig}$ ${\displaystyle k_{R}}$
5. Ключевой поток стороны респондента рассчитывается на основе информации о сверке и полинома . ${\displaystyle sk_{R}=\operatorname {Mod} _{2}(k_{R},w)}$ ${\displaystyle w}$ ${\displaystyle k_{R}}$
6. Ответчик направляет Инициатору . ${\displaystyle p_{R}}$ ${\displaystyle w}$

Заканчивать:

1. Получать и получать от Ответчика. ${\displaystyle p_{R}}$ ${\displaystyle w}$
2. Выборка из и вычисление . ${\displaystyle e'_{I}}$ ${\displaystyle \chi _{\alpha }}$ ${\displaystyle k_{I}=p_{R}s_{I}+2e'_{I}=as_{I}s_{R}+2e_{R}s_{I}+2e'_{I}}$
3. Поток ключей на стороне инициатора формируется на основе информации о согласовании и полинома . ${\displaystyle sk_{I}=\operatorname {Mod} _{2}(k_{I},w)}$ ${\displaystyle w}$ ${\displaystyle k_{I}}$

В приведенном выше обмене ключами функция сигнала определена следующим образом: ${\displaystyle \operatorname {Sig} }$

Определим подмножество . Здесь и обозначают пол и округление до ближайшего целого числа соответственно. ${\displaystyle \mathbf {E} :=\{-\lfloor {\frac {q}{4}}\rfloor ,\ldots ,\lfloor {\frac {q}{4}}\rceil \}}$ ${\displaystyle Zq=\{-{\frac {q-1}{2}},\ldots ,{\frac {q-1}{2}}\}}$ ${\displaystyle \lfloor .\rfloor }$ ${\displaystyle \lfloor .\rceil }$

Функция является характеристической функцией дополнения E. ${\displaystyle \operatorname {Sig} }$

${\displaystyle \operatorname {Sig} :Zq\rightarrow \{0,1\}}$: ${\displaystyle \operatorname {Sig} (v)={\begin{cases}0,&{\text{if }}v\in E\\1,&{\text{if }}v\notin E.\end{cases}}}$

${\displaystyle \operatorname {Mod} _{2}}$— это операция mod 2 для устранения ошибок, определяемая следующим образом: ${\displaystyle \operatorname {Mod} _{2}(v,w)={\biggl (}v+w.{\frac {q-1}{2}}{\Biggr )}{\bmod {q}}{\bmod {2}}}$

Обратите внимание, что значения и лишь приблизительно равны. Чтобы извлечь общий ключ с использованием этих приблизительно равных значений, используется функция согласования, также известная как сигнальная функция. Эта функция указывает область, в которой лежит каждый коэффициент полинома в , и помогает убедиться, что члены ошибки в и не приводят к различным операциям mod q. ${\displaystyle k_{I}}$ ${\displaystyle k_{R}}$ ${\displaystyle v}$ ${\displaystyle R_{q}}$ ${\displaystyle k_{R}}$ ${\displaystyle k_{I}}$

Методы согласования и генерации ключевых строк зависят от конкретной рассматриваемой схемы RLWE-KEX. Некоторые методы основаны на модульной арифметике, в то время как другие могут быть основаны на геометрии высокой размерности. ^{[6] [11]}

Если обмен ключами прошел правильно, строка инициатора и строка ответчика будут одинаковыми.

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

Выбор параметров

Представленный выше обмен RLWE-KEX работал в кольце многочленов степени n  − 1 или меньше mod a polynomial . В презентации предполагалось, что n является степенью 2, а q — простым числом, сравнимым с 1 (mod 2n). Следуя указаниям, данным в статье Пейкерта, Сингх предложил два набора параметров для RLWE-KEX. ${\displaystyle \Phi (x)}$

Для 128 бит безопасности n = 512, q = 25601 и ${\displaystyle \Phi (x)=x^{512}+1}$

Для 256 бит безопасности n = 1024, q = 40961 и ${\displaystyle \Phi (x)=x^{1024}+1}$

Поскольку обмен ключами использует случайную выборку и фиксированные границы, существует небольшая вероятность того, что обмен ключами не сможет создать один и тот же ключ для инициатора и ответчика. Если предположить, что гауссовский параметр σ равен и граница равномерной выборки ( b ) = 5 (см. Singh), ^[6], то вероятность сбоя согласования ключей меньше 2 ⁻⁷¹ для 128-битных безопасных параметров и меньше 2 ⁻⁹¹ для 256-битных безопасных параметров. ${\textstyle {\frac {8}{\sqrt {2\pi }}}}$

В своей статье от ноября 2015 года Алким, Дукас, Пёппельманн и Швабе рекомендуют следующие параметры: n = 1024, q = 12289 и = x ¹⁰²⁴ + 1. ^[11] Это представляет собой 70%-ное сокращение размера открытого ключа по сравнению с параметрами Сингха n = 1024 и было представлено в проект NIST по стандартизации постквантовой криптографии под названием NewHope . ${\displaystyle \Phi (x)}$

Также в своей статье от ноября 2015 года Алким, Дукас, Пёппельманн и Швабе рекомендуют, чтобы выбор базового полинома для обмена ключами (a(x) выше) либо генерировался случайным образом с помощью безопасного генератора случайных чисел для каждого обмена, либо создавался проверяемым образом с использованием техники «ничего в рукаве» или NUMS. ^[11] Примером параметров, сгенерированных таким образом, являются простые числа для Internet Key Exchange (RFC 2409), которые встраивают цифры математической константы пи в цифровое представление простого числа. ^[12] Их первый метод предотвращает амортизацию затрат на атаку во многих обменах ключами, рискуя оставить открытой возможность скрытой атаки, подобной той, что описана Дэном Бернстайном против эллиптических кривых NIST. ^[13] Подход NUMS открыт для амортизации, но в целом позволяет избежать атаки Бернстайна, если используются только общие математические константы, такие как пи и e.

Безопасность обмена ключами

Безопасность этого обмена ключами основана на базовой сложности проблемы кольцевого обучения с ошибками , которая, как было доказано, так же сложна, как и худшее решение задачи поиска кратчайшего вектора (SVP) в идеальной решетке . ^{[1] [2]} Лучшим методом оценки практической безопасности заданного набора параметров решетки является алгоритм сокращения решетки BKZ 2.0. ^[14] Согласно алгоритму BKZ 2.0, перечисленные выше параметры обмена ключами обеспечат более 128 или 256 бит безопасности соответственно.

Реализации

В 2014 году Дуглас Стебила сделал патч для OpenSSL 1.0.1f. на основе своей работы и других работ, опубликованных в «Постквантовый обмен ключами для протокола TLS из проблемы кольцевого обучения с ошибками». ^[15] Программное обеспечение, реализующее работу Сингха, можно найти на GitHub по адресу https://github.com/vscrypto/ringlwe. ^[6]

Другие подходы

Вариант подхода, описанного выше, является аутентифицированной версией в работе Чжана, Чжана, Дина, Снука и Дагделена в их статье «Постквантовый аутентифицированный обмен ключами из идеальных решеток». ^[16] Концепция создания того, что было названо обменом ключами типа Диффи–Хеллмана с использованием решеток с функцией согласования, по-видимому, впервые была представлена ​​французскими исследователями Агиларом, Габори, Лашармом, Шреком и Земором на PQCrypto 2010 в их докладе «Шумные протоколы Диффи–Хеллмана». ^[17]

В ноябре 2015 года Алким, Дукас, Пёппельманн и Швабе, основываясь на предыдущей работе Пейкерта, использовали то, что они считают более консервативной оценкой стоимости решетчатых атак, чтобы рекомендовать параметры. ^[11] Программное обеспечение, основанное на работе Алкима, Дукаса, Пёппельманна и Швабе, можно найти на GitHub по адресу https://github.com/tpoeppelmann/newhope ^[11]

Смотрите также

• Постквантовая криптография
• Криптография на основе решеток
• Идеальная решетчатая криптография
• Кольцевое обучение с сигнатурой ошибок
• Кольцевое обучение с ошибками

Ссылки

1. Regev, Oded (2005). «О решетках, обучении с ошибками, случайных линейных кодах и криптографии». Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений . STOC '05. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 84–93. CiteSeerX  10.1.1.110.4776 . doi :10.1145/1060590.1060603. ISBN 978-1-58113-960-0. S2CID  53223958.
2. Дин, Цзиньтай; Се, Сян; Линь, Сяодун (2012). Простая доказуемо безопасная схема обмена ключами, основанная на проблеме обучения с ошибками (PDF) .
3. Пейкерт, Крис (2014-01-01). "Решеточная криптография для Интернета". Архив Cryptology ePrint .
4. Алким, Эрдем; Дюкас, Лео; Пёппельманн, Томас; Швабе, Питер (2015-01-01). "Постквантовый обмен ключами - новая надежда". Архив Cryptology ePrint .
5. "Эксперименты с постквантовой криптографией". Блог Google Online Security . Получено 2017-02-08 .
6. Сингх, Викрам (2015). «Практический обмен ключами для Интернета с использованием решетчатой ​​криптографии». Архив Cryptology ePrint .
7. "Архив Cryptology ePrint: Отчет 2015/1120". eprint.iacr.org . Получено 2015-12-23 .
8. "Эффективный и параллельный гауссовский сэмплер для решеток" (PDF) . www.cc.gatech.edu . Получено 29.05.2015 .
9. Любашевский, Вадим; Пейкерт, Крис; Регев, Одед (2013). «Набор инструментов для криптографии Ring-LWE». Архив Cryptology ePrint .
10. "Архив Cryptology ePrint: Отчет 2015/1120". eprint.iacr.org . Получено 2016-01-17 .
11. "Архив Cryptology ePrint: Отчет 2015/1092". eprint.iacr.org . Получено 2015-11-11 .
12. Д., Каррел; Д., Харкинс (ноябрь 1998 г.). "Обмен ключами в Интернете (IKE)". tools.ietf.org . Получено 16.03.2017 .
13. «Уязвим ли решетчатый обмен ключами «Новая надежда» к решетчатому аналогу атаки Бернстайна BADA55?». crypto.stackexchange.com . Получено 16.03.2017 .
14. Чен, Юаньми; Нгуен, Фонг К. (2011). «BKZ 2.0: Лучшая оценка безопасности решеток». В Ли, Донг Хун; Ванг, Сяоюнь (ред.). Достижения в криптологии – ASIACRYPT 2011. Конспект лекций по информатике. Том 7073. Springer Berlin Heidelberg. стр. 1–20. doi :10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.
15. Бос, Йоппе В.; Костелло, Крейг; Наериг, Майкл; Стебила, Дуглас (2014-01-01). «Постквантовый обмен ключами для протокола TLS из проблемы кольцевого обучения с ошибками». Архив Cryptology ePrint .
16. "Семинар по кибербезопасности в постквантовом мире". NIST . 2015-04-02 . Получено 2015-06-06 .
17. "Noisy Diffie–Hellman protocols" (PDF) . pqc2010.cased.de . Архивировано из оригинала (PDF) 2015-06-14 . Получено 2015-06-06 .

Внешние ссылки