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

megan
  • 2020-02-06
  • 1

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

Предпосылки

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

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

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

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

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

Введение

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

a(x) = a 0 + a 1 x + a 2 x 2 + … + a n-3 x n-3 + a n-2 x n-2 + a n-1 x n-1

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

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

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

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

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

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

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

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

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

Действия Боба [ неавторитетный источник ] [ источник не указан 2981 день ] :

  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 = , то придумать случайный бит( b ). Если он — 0 то v j = иначе v j = .
  4. Формирование 2 битовых потоков c j и u j длины n из коэффициентов v(x) с помощью следующих преобразований. От j=0 до n-1 :
    1. Записать c j как младший бит от целой части 4v j /q , то есть .
    2. Записать .
  5. Формирование ключа k как конкатенации u n-1 , …, u 0 .
  6. Формирование строки «согласования»( C ) длины n , как конкатенации c n-1 , …, c 0 .
  7. Вычисление t B (x) = a(x)·s B (x) + e B (x) .
  8. Отправка t B (x) и C Алисе.

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

  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 и ≤ w j < тогда u j = 0 , иначе u j = 1 .
    2. Если c j = 1 и ≤ w j < тогда u j = 0 , иначе u j = 1 .
  4. Формирование ключа k , как конкатенации u n-1 , …, u 0 .

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

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

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

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

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

Так как обмен ключами использует случайную ограниченную выборку, есть вероятность того, что будут сгенерированы одинаковые ключи для Алисы и Боба . Предположим, гауссов параметр σ = или используется равномерная выборка при b = 5 , тогда вероятность ошибки совпадения открытых ключей меньше, чем 2 −71 и 2 −75 для 128 разрядных параметров и меньше 2 −91 и 2 −97 для 256 -битных параметров соответственно [ неавторитетный источник ] [ источник не указан 2981 день ] .

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

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

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

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

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

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

См. также

Примечания

  1. ↑ .
  2. , pp. 1-2.
  3. . Дата обращения: 27 ноября 2015. 8 декабря 2015 года.
  4. . Дата обращения: 5 декабря 2015. 7 ноября 2015 года.
  5. . Дата обращения: 27 ноября 2015. 8 декабря 2015 года.
  6. Regev, Oded. (англ.) // 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 : . 21 августа 2008 года.
  7. , pp. 35-37.
  8. ↑ , pp. 2.
  9. , pp. 1.
  10. ↑ , pp. 200-201.
  11. ↑ , pp. 1-2.
  12. , pp. 7.
  13. , pp. 15-16.
  14. , pp. 9-10.
  15. , pp. 18-20.
  16. , pp. 10-11.
  17. ↑ , pp. 8-11.
  18. , pp. 8.
  19. ↑ , pp. 21-24.
  20. , pp. 6,15-16.
  21. , pp. 204-205.
  22. , pp. 22.
  23. , pp. 26.
  24. , pp. 47-48.

Литература

  • (англ.) // : 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 : .
Источник —

megan
  • 2020-02-06
  • 1
  • Tags:

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

The title for the last searches