Кольцевое обучение с ошибками обмен ключами - Ring learning with errors key exchange

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

Задний план

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

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

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

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

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

Введение

Начиная с премьер целое число q, Кольцо-LWE обмен ключами работает в кольцо многочленов по модулю многочлена ${\displaystyle \Phi (x)}$ с коэффициентами в поле целых чисел mod q (т. е. кольцо ${\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 обмена ключами Диффи-Хеллмана была позже опубликована Zhang et al. в 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}}$

Коэффициенты этого полинома а_яs, целые числа modq. Полином ${\displaystyle \Phi (x)}$ будет круговой полином. Когда п является степенью двойки, то ${\displaystyle \Phi (x)=x^{n}+1.}$^[6][7]

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

1. С помощью Равномерная выборка - Коэффициенты малого полинома равномерно выбираются из набора малых коэффициентов. Позволять б быть целым числом, которое намного меньше, чем q. Если случайным образом выбрать коэффициенты из набора: {-б, −b + 1, −b + 2. ... −2, −1, 0, 1, 2, ..., б − 2, б − 1, б} многочлен будет малым относительно оценки (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 по модулю 4 и 1 по модулю 2n. Другие случаи для q и n подробно обсуждаются в «Инструментарии для кольцевой криптографии LWE» и в книге Сингха «Еще более практичный обмен ключами для Интернета с использованием решетчатой ​​криптографии».^[9][10] и еще одна статья Сингха. Фиксированный общедоступный многочлен a (x), общий для всех пользователей сети. Он детерминированно генерируется из криптографически безопасного источника.

Данный а(Икс), как указано, мы можем случайным образом выбрать малые многочлены s(Икс) и е(Икс) быть «закрытым ключом» при обмене открытым ключом. Соответствующий открытый ключ будет полиномом п(Икс) = а(Икс)s(Икс) + 2е(Икс).

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

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

Обмен ключами начинается с того, что инициатор (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}}$.

1. Ключевой поток на стороне инициатора создается как ${\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 }$обозначает пол и округление до ближайшего целого числа соответственно.

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

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

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

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

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

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

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

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

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

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

Поскольку обмен ключами использует случайную выборку и фиксированные границы, существует небольшая вероятность того, что обмен ключами не сможет создать один и тот же ключ для инициатора и ответчика. Если предположить, что параметр Гаусса σ равно 8 / √ (2π) и равномерная граница выборки (б) = 5 (см. Сингха),^[6] тогда вероятность отказа ключевого соглашения равна меньше, чем 2⁻⁷¹ для 128-битных безопасных параметров и меньше, чем 2⁻⁹¹ для 256-битных безопасных параметров.

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

Также в своей статье от ноября 2015 года Алким, Дукас, Пёппельманн и Швабе рекомендуют, чтобы выбор базового полинома для обмена ключами (a (x) выше) либо генерировался случайным образом из безопасного генератора случайных чисел для каждого обмена, либо проверяемая мода с использованием техники «ничего в рукаве» или NUMS.^[11] Примером параметров, сгенерированных таким образом, являются простые числа для Internet Key Exchange (RFC 2409), которые включают цифры математической константы «пи» в цифровое представление простого числа.^[12] Их первый метод предотвращает амортизацию затрат на атаку на многих обменах ключами, рискуя оставить открытой возможность скрытой атаки, подобной описанной Дэном Бернстайном на эллиптических кривых NIST.^[13] Подход NUMS открыт для амортизации, но обычно позволяет избежать атаки Бернштейна, если используются только общие математические константы, такие как pi и 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] Программное обеспечение, основанное на работе Alkim, Ducas, Pöppelmann и Schwabe, можно найти на GitHub по адресу https://github.com/tpoeppelmann/newhope^[11]

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

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

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

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