В криптографии обмен ключами при обучении с ошибками — криптографический алгоритм, позволяющий двум сторонам создавать и обмениваться секретным ключом, который они используют для шифрования сообщений между собой. RLWE-KEX ( англ. Ring Learning with Errors Key Exchange ) является одним из алгоритмов с открытым ключом , который предназначен для защиты от противника, обладающего квантовым компьютером . Это важно, потому что криптографические системы с открытым ключом , широко используемые сегодня, легко взламываются квантовым компьютером . RLWE-KEX является одним из множества постквантовых криптографических алгоритмов , основанных на сложности решения математических задач, связанных с криптографией на решётках .

Предпосылки

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

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

Существует множество криптографических алгоритмов , которые работают с использованием парадигмы RLWE. Есть криптосистема с открытым ключом , гомоморфные алгоритмы шифрования и RLWE цифровая подпись алгоритма в дополнение к открытому ключу. Обмен ключами является типом асимметричного шифрования , который устанавливает общий секретный ключ между двумя взаимодействующими агентами на линии связи. Классическим примером обмена ключами является протокол Диффи — Хеллмана (и, как его расширение, Протокол Диффи — Хеллмана на эллиптических кривых ). Обмен состоит из одной передачи с одного конца линии и одной передачи с другого конца линии ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} .

RLWE обмен ключами разработан как квантово-безопасная замена для протоколов , которые используются для обеспечения безопасности создания секретных ключей по ненадежным каналам связи. Также как и протокол Диффи—Хеллмана, RLWE обеспечивает криптографическое свойство « совершенно прямой секретности » ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} , целью которого является снижение эффективности программ массового наблюдения и убеждение, что нет долгосрочных секретных ключей, которые могут быть скомпрометированы, что позволит осуществить объемную расшифровку.

Описание алгоритма

Введение

Используя простое число q, RLWE работает в кольце многочленов по модулю полинома Ф(х) с коэффициентами в поле целых чисел по модулю q (кольцо F _q [x]/Φ(x)) ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} . Полином a(x) выражается следующим образом:

a(x) = a ₀ + a ₁ x + a ₂ x ² + … + a _n-3 x ^n-3 + a _n-2 x ^n-2 + a _n-1 x ^n-1

Коэффициенты этого полинома являются целыми числами по модулю q . Полином Φ(x) = x ⁿ +1 , где n является степенью 2 (в большинстве случаев значения для n = 256, 512 или 1024).

RLWE-KEX использует полиномы, которые считаются «малыми» по отношению к мере, называемой ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} . Бесконечная норма для многочлена — значение наибольшего коэффициента полинома, когда коэффициенты рассматриваются как элементы множества { ${\displaystyle {-{\tfrac {q-1}{2}}}}$ ,…, 0, …, ${\displaystyle {\tfrac {q-1}{2}}}$ }. Для обеспечения безопасности алгоритма необходимо генерировать случайные полиномы s(x) , малые по отношению к бесконечной норме. Это делается случайным формированием коэффициентов для многочлена ( s _n-1 , …, s ₀ ), которые гарантированно или с большой вероятностью будут небольшими. Есть два распространенных способа:

1. Использование дискретного равномерного распределения — коэффициенты полинома небольшой равномерной пробы из набора малых коэффициентов. Пусть b — целое число, намного меньшее q. При выборе случайным образом коэффициентов из множества { -b, -b+1, -b+2. … −2, −1, 0, 1, 2, … , b-2, b-1, b }, полином будет небольшим по отношению к a(x) . Синг предлагает использовать b = 5 ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} . Таким образом, коэффициенты будут выбраны из множества { q-5, q-4, q-3, q-2, q-1, 0 , 1, 2, 3, 4, 5 }.
2. Использование дискретного нормального распределения — коэффициенты выбираются случайным образом для нечетного значения q с помощью выборки из множества { ${\displaystyle -{\tfrac {q-1}{2}}}$ ; ${\displaystyle {\tfrac {q-1}{2}}}$ } в соответствии с дискретным распределением Гаусса с математическим ожиданием 0 и дисперсией σ . Этот метод сложнее, чем дискретное равномерное распределение, но он позволяет доказать безопасность алгоритма .

Пусть случайные небольшие полиномы будут соответствовать распределению, обозначенному как D . Число q будет нечетным простым таким, что q ≡ 1 mod 4 и
q ≡ 1 mod 2n с целью минимизировать количество операций выбора случайного бита на границе множеств ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} . Это позволит реализовать алгоритм наиболее эффективно . Степень полинома Ф(x) является степенью 2 ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} .

Пусть фиксированный многочлен а(х) — общий для всех пользователей сети, генерируемый с помощью криптографическистойкого генератора псевдослучайных чисел . Взяв а(х) , произвольно выбираются небольшие многочлены s(x) и e(x) , s(x) — закрытый ключ в обмене открытыми ключами. Соответствующим открытым ключом будет многочлен t(х) = а(х)s(х) + е(х) ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} . Безопасность обмена ключами основана на трудности найти пару небольших многочленов s'(х) и e'(х) таких, что для данной t(х) а(х)s'(х) + е'(х) = t(х) .

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

Обмен ключами происходит между агентами обмена ключами Алисой , обозначенной как A , и Бобом , обозначенным как B . И A , и B знают q , n , a(x) и умеют генерировать небольшие полиномы в соответствии с распределением D .

Первоначальные действия Алисы ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} :

1. Генерация двух малых полиномов s _A (x) и e _A (x) путём выборки из распределения D .
2. Вычисление t _A (x) = a(x)•s _A (x) + e _A (x) .
3. Отправка t _A (x) Бобу.

Действия Боба ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} :

1. Генерация двух малых полиномов s _B (x) и e _B (x) путём выборки из распределения D .
2. Вычисление v(x) = t _A (x)·s _B (x) + e _B (x) . Заметим, что v(x) = a(x)s _A (x)s _B (x) + e _A (x)s _B (x) + e _B (x) и что e _B (x) + e _A (x)s _B (x) также будет малым, так как e _B (x) был выбран малым, коэффициенты e _A (x)s _B (x) ограничены в росте и также будут малы.
3. Распределение коэффициентов v(x) сглаживается с помощью цикла по коэффициентам и случайной корректировки определенных значений. От j=0 до n-1 :
   1. Если v _j = 0 , то придумать случайный бит(обозначим b ). Если он — 0 , то v _j = 0 , иначе v _j = q-1 .
   2. Если v _j = ${\displaystyle {\tfrac {q-1}{4}}}$ , то придумать случайный бит( b ). Если он — 0 то v _j = ${\displaystyle {\tfrac {q-1}{4}}}$ иначе v _j = ${\displaystyle {\tfrac {q+3}{4}}}$ .
4. Формирование 2 битовых потоков c _j и u _j длины n из коэффициентов v(x) с помощью следующих преобразований. От j=0 до n-1 :
   1. Записать c _j как младший бит от целой части 4v _j /q , то есть ${\textstyle c_{j}=\lfloor 4v_{j}/q\rfloor \mod 2}$ .
   2. Записать ${\displaystyle u_{j}=\lfloor 2v_{j}\rceil \mod 2}$ .
5. Формирование ключа k как конкатенации u _n-1 , …, u ₀ .
6. Формирование строки «согласования»( C ) длины n , как конкатенации c _n-1 , …, c ₀ .
7. Вычисление t _B (x) = a(x)·s _B (x) + e _B (x) .
8. Отправка t _B (x) и C Алисе.

Дальнейшие шаги Алисы ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} :

1. Получение t _B (x) и C от Боба.
2. Вычисление w(x) = t _B (x)·s _A (x) + e _A (x) = a(x)s _A (x)s _B (x) + e _B (x)s _A (x) + e _A (x) .
3. Формирование битового потока u _j длины n следующим образом:
   1. Если c _j = 0 и ${\displaystyle {\tfrac {-q}{8}}}$ ≤ w _j < ${\displaystyle {\tfrac {3q}{8}}}$ тогда u _j = 0 , иначе u _j = 1 .
   2. Если c _j = 1 и ${\displaystyle {\tfrac {-3q}{8}}}$ ≤ w _j < ${\displaystyle {\tfrac {q}{8}}}$ тогда u _j = 0 , иначе u _j = 1 .
4. Формирование ключа k , как конкатенации u _n-1 , …, u ₀ .

Если обмен ключами сработает должным образом то строки u _n-1 , …, u ₀ у Алисы и Боба будут совпадать ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} . В зависимости от специфики выбранных параметров n , q , σ и b , есть вероятность того, что t _A (x) и t _B (x) будут совпадать. Параметры для обмена ключами должны быть выбраны так, чтобы вероятность этой ошибки при обмене ключами была очень мала — гораздо меньше, чем вероятность неопределяемых искажений или сбоев устройств.

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

Обмен работает в кольце многочленов степени не больше n-1 по модулю многочлена Φ(х) . Предполагается, что n — степень 2 , а q — простое, q ≡ 1 mod 4 . Исходя из работы Пейкерта, Синг предложил два набора параметров для RWLE-KEX ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} .

Для 128 -битовой защиты: n = 512 , q = 25601 и Φ(x) = x ⁵¹² + 1

Для 256 -битовой защиты: n = 1024 , q = 40961 и Φ(x) = x ¹⁰²⁴ + 1

Так как обмен ключами использует случайную ограниченную выборку, есть вероятность того, что будут сгенерированы одинаковые ключи для Алисы и Боба . Предположим, гауссов параметр σ = ${\displaystyle {\tfrac {8}{\sqrt {2\pi }}}}$ или используется равномерная выборка при b = 5 , тогда вероятность ошибки совпадения открытых ключей меньше, чем 2 ⁻⁷¹ и 2 ⁻⁷⁵ для 128 разрядных параметров и меньше 2 ⁻⁹¹ и 2 ⁻⁹⁷ для 256 -битных параметров соответственно ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} .

В работе Алким, Дука, Попплеманн и Швабе (ноябрь 2015) рекомендуют следующие параметры: n = 1024 , q = 12289 , и Φ(x) = x ¹⁰²⁴ + 1 , так как они обеспечивают эффективность и безопасность алгоритма. В случае 256 -битовой защиты этот набор обеспечивает вероятность ошибки совпадения 2 ⁻¹¹⁰ .

Надежность алгоритма

Вычислительная сложность взлома RLWE-KEX того же порядка, что и решение кратчайшей векторной задачи (SVP) в идеальной решетке . Лучшим способом оценить практическую безопасность данного набора параметров решетки является (неопр.) . . В соответствии с алгоритмом BKZ 2.0, основные параметры обмена, перечисленные выше, будут обеспечивать больше чем 128 и 256 бит безопасности соответственно ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} .

Примеры реализации

В 2014 году Дуглас Стебила сделал патч для OpenSSL 1.0.1f. на основе работ, опубликованных в книге . Программное обеспечение работы Синга находится на (неопр.) . ^{[ неавторитетный источник ] [ источник не указан 2945 дней ] [ неавторитетный источник ] [ источник не указан 2945 дней ]} .

Ещё одним вариантом применения алгоритма является работа Чжана, Динга, Снука и Дагделена (неопр.) . . Концепция создания алгоритма Диффи-Хеллмана впервые была представлена французскими исследователями Агиларом, Габоритом, Лачармом, Шреком и Земором на PQCrypto 2010 года в их докладе (неопр.) . Дата обращения: 1 декабря 2015. Архивировано из 24 сентября 2015 года. ^{[ неавторитетный источник ] [ источник не указан 2945 дней ]} . Затем эта тема была расширена и положила начало более строгим исследованиям Пейкерта в его (неопр.) . .

См. также

• Постквантовая криптография
• Криптография на решётках
• Обучение с ошибками

Примечания

Литература

• (англ.) // : 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014. Proceedings / — Berlin, Heidelberg, New York City, London: , 2014. — P. 197—219. — ( ; Vol. 8772) — ISBN 978-3-319-11658-7 — ISSN ; —
• Singh, Vikram. (англ.) 31. International Association for Cryptologic Research (2015).
• Lyubashevsky, Vadim;Peikert, Chris; Regev,Chris. (англ.) // Advances in Cryptology - EUROCRYPT 2013 : сборник. — Springer-Verlag Berlin Heidelberg, 2013. — P. 3—54 . — ISBN 978-3-642-38348-9 . — ISSN . — doi : .
• Alkim, Erdem; Ducas, Leo; Pöppelman, Thomas; Schwabe, Peter. (англ.) 32. International Association for Cryptologic Research (2015).
• Joppe W. Bos; Craig Costello; Michael Naehrig; Douglas Stebila. (англ.) // Security and Privacy (SP) : сборник. — IEEE, 2015. — P. 553—570 . — ISBN 978-3-642-38348-9 . — ISSN . — doi : .
• Жиров А. О., Жирова О. В., Кренделев С. Ф. (рус.) // Безопасность информационных технологий : журнал. — 2013. — Январь ( № 1 ). — С. 1—12 . — ISSN .
• Валиев К.А. (рус.) // Вестник Российской академии наук : журнал. — 2000. — Август ( т. 70 , № 8 ). — С. 688—695 . — ISSN .
• Peikert, Chris. (англ.) // Advances in Cryptology – CRYPTO 2010 : сборник. — Springer Berlin Heidelberg, 2010. — P. 80—97 . — ISBN 978-3-642-14622-0 . — ISSN . — doi : .