Обмен ключами на основе обучения с ошибками

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

Предпосылки

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

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

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

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

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

Введение

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

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

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

RLWE-KEX использует полиномы, которые считаются «малыми» по отношению к мере, называемой «бесконечной» нормой^{[11][неавторитетный источник][источник не указан 3185 дней]}. Бесконечная норма для многочлена — значение наибольшего коэффициента полинома, когда коэффициенты рассматриваются как элементы множества {${\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^{[12][неавторитетный источник][источник не указан 3185 дней]}. Таким образом, коэффициенты будут выбраны из множества { 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 и дисперсией σ. Этот метод сложнее, чем дискретное равномерное распределение, но он позволяет доказать безопасность алгоритма^[13].

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

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

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

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

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

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

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

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 Алисе.

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

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₀ у Алисы и Боба будут совпадать^{[18][неавторитетный источник][источник не указан 3185 дней]}. В зависимости от специфики выбранных параметров n, q, σ и b, есть вероятность того, что t_A(x) и t_B(x) будут совпадать. Параметры для обмена ключами должны быть выбраны так, чтобы вероятность этой ошибки при обмене ключами была очень мала — гораздо меньше, чем вероятность неопределяемых искажений или сбоев устройств.

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

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

Для 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-битных параметров соответственно^{[19][неавторитетный источник][источник не указан 3185 дней]}.

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

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

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

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

В 2014 году Дуглас Стебила сделал патч для OpenSSL 1.0.1f. на основе работ, опубликованных в книге «Post-quantum key exchange for the TLS protocol from the ring learning with errors problem». Программное обеспечение работы Синга находится на GitHub  (неопр.).^{[неавторитетный источник][источник не указан 3185 дней][23][неавторитетный источник][источник не указан 3185 дней]}.

Ещё одним вариантом применения алгоритма является работа Чжана, Динга, Снука и Дагделена «Post Quantum Authenticated Key Exchange from Ideal Lattices»  (неопр.).. Концепция создания алгоритма Диффи-Хеллмана впервые была представлена французскими исследователями Агиларом, Габоритом, Лачармом, Шреком и Земором на PQCrypto 2010 года в их докладе «Noisy Diffie-Hellman Protocols»  (неопр.). Дата обращения: 1 декабря 2015. Архивировано из оригинала 24 сентября 2015 года.^{[неавторитетный источник][источник не указан 3185 дней]}. Затем эта тема была расширена и положила начало более строгим исследованиям Пейкерта в его работе  (неопр.).^[24].

См. также

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

Примечания

1. Валиев, 2000.
2. Lyubashevsky, Peikert, Regev, 2013, pp. 1-2.
3. Для взлома шифров АНБ потребовался квантовый компьютер  (неопр.). Дата обращения: 27 ноября 2015. Архивировано 8 декабря 2015 года.
4. Создание квантового компьютера становится инженерной задачей  (неопр.). Дата обращения: 5 декабря 2015. Архивировано 7 ноября 2015 года.
5. Криптосистемы с открытым ключом  (неопр.). Дата обращения: 27 ноября 2015. Архивировано 8 декабря 2015 года.
6. Regev, Oded. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (англ.) // Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing : journal. — New York, NY, USA: ACM, 2005. — Vol. STOC '05. — P. 84—93. — ISBN 1-58113-960-8. — doi:10.1145/1060590.1060603. Архивировано 21 августа 2008 года.
7. Lyubashevsky, Peikert, Regev, 2013, pp. 35-37.
8. Singh, 2015, pp. 2.
9. Singh, 2015, pp. 1.
10. Peikert, 2014, pp. 200-201.
11. Singh, 2015, pp. 1-2.
12. Singh, 2015, pp. 7.
13. Peikert, 2010, pp. 15-16.
14. Singh, 2015, pp. 9-10.
15. Alkim et al, 2015, pp. 18-20.
16. Singh, 2015, pp. 10-11.
17. Singh, 2015, pp. 8-11.
18. Singh, 2015, pp. 8.
19. Singh, 2015, pp. 21-24.
20. Alkim et al, 2015, pp. 6,15-16.
21. Peikert, 2014, pp. 204-205.
22. Singh, 2015, pp. 22.
23. Singh, 2015, pp. 26.
24. Lyubashevsky, Peikert, Regev, 2013, pp. 47-48.

Литература

• Peikert C. Lattice Cryptography for the Internet (англ.) // Post-Quantum Cryptography: 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014. Proceedings / M. Mosca — Berlin, Heidelberg, New York City, London: Springer Nature Switzerland AG, 2014. — P. 197—219. — (Lecture Notes in Computer Science; Vol. 8772) — ISBN 978-3-319-11658-7 — ISSN 0302-9743; 1611-3349 — doi:10.1007/978-3-319-11659-4_12
• Singh, Vikram. A Practical Key Exchange for the Internet using Lattice Cryptography (англ.) 31. International Association for Cryptologic Research (2015).
• Lyubashevsky, Vadim;Peikert, Chris; Regev,Chris. A Toolkit for Ring-LWE Cryptography (англ.) // Advances in Cryptology - EUROCRYPT 2013 : сборник. — Springer-Verlag Berlin Heidelberg, 2013. — P. 3—54. — ISBN 978-3-642-38348-9. — ISSN 0302-9743. — doi:10.1007/978-3-642-38348-9_3.
• Alkim, Erdem; Ducas, Leo; Pöppelman, Thomas; Schwabe, Peter. Post-quantum key exchange — a new hope (англ.) 32. International Association for Cryptologic Research (2015).
• Joppe W. Bos; Craig Costello; Michael Naehrig; Douglas Stebila. Post-quantum key exchange for the TLS protocol from the Ring Learning with Errors Problem (англ.) // Security and Privacy (SP) : сборник. — IEEE, 2015. — P. 553—570. — ISBN 978-3-642-38348-9. — ISSN 1081-6011. — doi:10.1109/SP.2015.40.
• Жиров А. О., Жирова О. В., Кренделев С. Ф. Безопасные облачные вычисления с помощью гомоморфной криптографии (рус.) // Безопасность информационных технологий : журнал. — 2013. — Январь (№ 1). — С. 1—12. — ISSN 2074-7128.
• Валиев К.А. Квантовая информатика: компьютеры, связь и криптография// (рус.) // Вестник Российской академии наук : журнал. — 2000. — Август (т. 70, № 8). — С. 688—695. — ISSN 0869-5873.
• Peikert, Chris. An Efficient and Parallel Gaussian Sampler for Lattices (англ.) // Advances in Cryptology – CRYPTO 2010 : сборник. — Springer Berlin Heidelberg, 2010. — P. 80—97. — ISBN 978-3-642-14622-0. — ISSN 0302-9743. — doi:10.1007/978-3-642-14623-7_5.