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

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

Предпосылки

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

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

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

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

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

Введение

Используя простое число q, RLWE работает в кольце многочленов по модулю полинома Ф(х) с коэффициентами в поле целых чисел по модулю q (кольцо F_q[x]/Φ(x)). Полином 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 использует полиномы, которые считаются «малыми» по отношению к мере, называемой «бесконечной» нормой. Бесконечная норма для многочлена — значение наибольшего коэффициента полинома, когда коэффициенты рассматриваются как элементы множества {${-{\tfrac {q-1}{2}}}$,…, 0, …, ${\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. Таким образом, коэффициенты будут выбраны из множества { q-5, q-4, q-3, q-2, q-1, 0 , 1, 2, 3, 4, 5 }.
2. Использование дискретного нормального распределения — коэффициенты выбираются случайным образом для нечетного значения q с помощью выборки из множества { $-{\tfrac {q-1}{2}}$; ${\tfrac {q-1}{2}}$ } в соответствии с дискретным распределением Гаусса с математическим ожиданием 0 и дисперсией σ. Этот метод сложнее, чем дискретное равномерное распределение, но он позволяет доказать безопасность алгоритма.

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

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

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

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

Первоначальные действия Алисы:

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

Действия Боба:

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 = ${\tfrac {q-1}{4}}$, то придумать случайный бит(b). Если он — 0 то v_j = ${\tfrac {q-1}{4}}$ иначе v_j = ${\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. Записать $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 Алисе.

Дальнейшие шаги Алисы:

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 и ${\tfrac {-q}{8}}$ ≤ w_j < ${\tfrac {3q}{8}}$ тогда u_j = 0, иначе u_j = 1.
   2. Если c_j = 1 и ${\tfrac {-3q}{8}}$ ≤ w_j < ${\tfrac {q}{8}}$ тогда u_j = 0, иначе u_j = 1.
4. Формирование ключа k, как конкатенации u_n-1, …, u₀.

Если обмен ключами сработает должным образом то строки u_n-1, …, u₀ у Алисы и Боба будут совпадать. В зависимости от специфики выбранных параметров n, q, σ и b, есть вероятность того, что t_A(x) и t_B(x) будут совпадать. Параметры для обмена ключами должны быть выбраны так, чтобы вероятность этой ошибки при обмене ключами была очень мала — гораздо меньше, чем вероятность неопределяемых искажений или сбоев устройств.

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• 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 International Publishing, 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.