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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Июнь 2015 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Фон [ править ]

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

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

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

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

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

Введение [ править ]

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

Коэффициенты этого многочлена a _i s являются целыми числами mod  q . Многочлен будет циклотомическим многочленом . Когда n является степенью двойки, тогда ^{[6] [7]}${\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 по модулю 4 и 1 по модулю 2n. Другие случаи для q и n подробно обсуждаются в «Инструментарии для кольцевой криптографии LWE» и в книге Сингха «Еще более практичный обмен ключами для Интернета с использованием решетчатой ​​криптографии». ^{[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 ) и могут генерировать небольшие многочлены в соответствии с распределением с параметром . Распределение обычно представляет собой дискретное гауссово распределение на кольце${\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. Образец из и Compute .${\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} }$

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

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

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

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

Выбор параметров [ править ]

Обмен RLWE-KEX, представленный выше, работал в Кольце многочленов степени n  - 1 или меньше по модулю многочлена . В представлении предполагалось, что 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 (см. Сингх), ^[6], то вероятность отказа согласования ключей будет меньше 2 ⁻⁷¹ для 128-битных параметров безопасности и меньше чем 2 ^-91 для 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 открыт для амортизации, но в целом позволяет избежать атаки Бернштейна, если используются только общие математические константы, такие как 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] Программное обеспечение, основанное на работах Алкима, Дукаса, Пёппельмана и Швабе, можно найти на GitHub по адресу https://github.com/tpoeppelmann/newhope ^[11]

См. Также [ править ]

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

Ссылки [ править ]