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

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

Предыстория

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

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

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

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

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

Введение

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

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

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

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

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

$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}$

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

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

1. Использование равномерной выборки . Коэффициенты малого полинома равномерно выбираются из набора малых коэффициентов. Пусть b — целое число, намного меньшее q . Если мы случайным образом выберем коэффициенты из набора: { − b , −b + 1, −b + 2. ... −2, −1, 0, 1, 2, ... , b − 2, b − 1, b } полином будет мал относительно границы (b). Сингх предлагает использовать b = 5. Таким образом, коэффициенты будут выбираться из набора { 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 и параметр распределения σ . В ссылках подробно описано, как это можно сделать. Это сложнее, чем равномерная выборка, но позволяет доказать безопасность алгоритма. Обзор гауссовой выборки можно найти в презентации Пейкерта.

В оставшейся части этой статьи случайные малые полиномы будут выбираться в соответствии с распределением, которое просто обозначается как D . Далее q будет нечетным простым числом, таким что q конгруэнтно 1 по модулю 4 и 1 по модулю 2n. Другие случаи для q и n подробно обсуждаются в «Наборе инструментов для криптографии Ring-LWE» и в книге Сингха «Еще более практичный обмен ключами для Интернета с использованием решетчатой ​​криптографии». и еще одна статья Сингха. Фиксированный общедоступный полином 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 ) и обладают способностью генерировать небольшие полиномы в соответствии с распределением $\chi _{\alpha }$ с параметром $\alpha$. Распределение $\chi _{\alpha }$ обычно представляет собой дискретное распределение Гаусса на кольце $R_{q}=Zq[x]/\Phi (x)$. Следующее описание не содержит никаких объяснений того, почему обмен ключами приводит к одному и тому же ключу на обоих концах ссылки. Скорее, в нем кратко указаны шаги, которые необходимо предпринять. Для полного понимания того, почему обмен ключами приводит к тому, что инициатор и ответчик имеют один и тот же ключ, читателю следует просмотреть указанную работу Дина и др.

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

Инициирование:

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

Ответ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализации

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

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

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

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

См. также

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