Криптография на основе решеток

Конструкции криптографических примитивов, включающие решетки

Криптография на основе решеток — это общий термин для конструкций криптографических примитивов , которые включают решетки , либо в самой конструкции, либо в доказательстве безопасности. Конструкции на основе решеток поддерживают важные стандарты постквантовой криптографии . ^[1] В отличие от более широко используемых и известных схем с открытым ключом, таких как RSA , Диффи-Хеллмана или эллиптических кривых криптосистем, которые теоретически могут быть преодолены с помощью алгоритма Шора на квантовом компьютере , некоторые конструкции на основе решеток, по-видимому, устойчивы к атакам как классических, так и квантовых компьютеров. Более того, многие конструкции на основе решеток считаются безопасными, исходя из предположения , что некоторые хорошо изученные вычислительные проблемы решеток не могут быть решены эффективно.

В 2024 году NIST анонсировал стандарт цифровой подписи на основе модульной решетки для постквантовой криптографии. ^[2]

История

В 1996 году Миклош Айтай представил первую криптографическую конструкцию на основе решётки, безопасность которой могла быть основана на сложности хорошо изученных решёточных задач ^[3] , а Синтия Дворк показала, что определённая усреднённая решёточная задача, известная как короткие целочисленные решения (SIS), по крайней мере так же сложна для решения, как и наихудшая решёточная задача. ^[4] Затем она показала криптографическую хеш-функцию , безопасность которой эквивалентна вычислительной сложности SIS.

В 1998 году Джеффри Хоффштейн , Джилл Пайфер и Джозеф Х. Сильверман представили схему шифрования с открытым ключом на основе решетки , известную как NTRU . ^[5] Однако известно, что их схема не так сложна, как решение наихудшей решетчатой ​​задачи.

Первая схема шифрования с открытым ключом на основе решетки, безопасность которой была доказана при наихудших предположениях о сложности, была представлена ​​Одедом Регевым в 2005 году ^[6] вместе с проблемой обучения с ошибками (LWE). С тех пор большая часть последующей работы была сосредоточена на улучшении доказательства безопасности Регева ^{[7] [8]} и повышении эффективности исходной схемы. ^{[9] [10] [11] [12]} Гораздо больше работы было посвящено построению дополнительных криптографических примитивов на основе LWE и связанных с ними проблем. Например, в 2009 году Крейг Джентри представил первую полностью гомоморфную схему шифрования, которая была основана на проблеме решетки. ^[13]

Математическое образование

В линейной алгебре решетка — это множество всех целочисленных линейных комбинаций векторов из базиса . Другими словами, Например, — это решетка, порожденная стандартным базисом для . Важно отметить, что базис для решетки не является единственным. Например, векторы , , и образуют альтернативный базис для . ${\displaystyle L\subset \mathbb {R} ^{n}}$ ${\displaystyle \{\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle L={\Big \{}\sum a_{i}\mathbf {b} _{i}:a_{i}\in \mathbb {Z} {\Big \}}.}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle (3,1,4)}$ ${\displaystyle (1,5,9)}$ ${\displaystyle (2,-1,0)}$ ${\displaystyle \mathbb {Z} ^{3}}$

Самая важная вычислительная задача на основе решетки — это задача нахождения кратчайшего вектора (SVP или иногда GapSVP), которая требует от нас аппроксимации минимальной евклидовой длины ненулевого вектора решетки. Считается, что эту задачу трудно решить эффективно, даже с факторами аппроксимации, которые являются полиномиальными по , и даже с помощью квантового компьютера. Известно, что многие (хотя и не все) криптографические конструкции на основе решетки являются безопасными, если SVP на самом деле является сложным в этом режиме. ${\displaystyle n}$

Избранные схемы на основе решеток

В этом разделе представлены избранные схемы на основе решеток, сгруппированные по примитивам.

Шифрование

Выбранные схемы для целей шифрования:

• Схема шифрования GGH , которая основана на задаче о ближайшем векторе (CVP). В 1999 году Нгуен опубликовал критический недостаток в конструкции схемы. ^[14]
• NTRUEncrypt .

Гомоморфное шифрование

Избранные схемы для целей гомоморфного шифрования :

• Первоначальная схема Джентри. ^[13]
• Бракерски и Вайкунтанатан. ^{[15] [16]}

Хэш-функции

Выбранные криптографические схемы на основе решеток для целей хеширования:

• СВИФТ .
• Функция хэширования на основе решеток (LASH). ^{[17] [18]}

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

Выбранные схемы для обмена ключами, также называемые установлением ключей, инкапсуляцией ключей и механизмом инкапсуляции ключей (KEM):

• CRYSTALS-Kyber , ^[19] который построен на модульном обучении с ошибками (модуль-LWE). Kyber был выбран для стандартизации NIST в 2023 году. ^[1] В августе 2023 года NIST опубликовал FIPS 203 (первоначальный публичный проект) и начал называть свою версию Kyber Механизмом инкапсуляции ключей на основе модульной решетки (ML-KEM). ^[20]
• FrodoKEM, ^{[21] [22]} схема, основанная на проблеме обучения с ошибками (LWE). FrodoKEM присоединился к стандартизации, проводимой Национальным институтом стандартов и технологий (NIST) , ^[1] и дожил до 3-го раунда процесса. Затем он был отклонен из-за низкой производительности. В октябре 2022 года аккаунт Twitter, связанный с криптологом Дэниелом Дж. Бернстайном, опубликовал информацию о проблемах безопасности в frodokem640. ^[23]
• NewHope основан на проблеме кольцевого обучения с ошибками (RLWE). ^[24]
• NTRU Prime. ^[25]
• Работа Пейкерта , основанная на проблеме кольцевого обучения с ошибками (RLWE). ^[10]
• Saber, ^[26] основанный на проблеме модульного обучения с округлением (модуль-LWR).

Подписание

В этом разделе перечислен ряд схем на основе решеток для цифровых подписей.

• CRYSTALS-Dilithium, ^{[27] [28]} который построен на модульном обучении с ошибками (модуль-LWE) и модульном коротком целочисленном решении (модуль-SIS). Dilithium был выбран для стандартизации NIST. ^[1] Согласно сообщению Рэя Перлнера, пишущего от имени команды NIST PQC, стандарт подписи NIST module-LWE должен быть основан на версии 3.1 спецификации Dilithium.

• Falcon , который построен на решении коротких целых чисел (SIS) над NTRU. Falcon был выбран для стандартизации NIST. ^{[29] [1]}
• Схема подписи GGH .
• Работа Гюнейсу, Любашевского и Пёппельмана, основанная на кольцевом обучении с ошибками (RLWE). ^[30]

• МИТАКА, вариант Сокола. ^[31]
• NTRUSign .
• qTESLA, которая основана на кольцевом обучении с ошибками (RLWE). Схема qTESLA присоединилась к стандартизации, проводимой Национальным институтом стандартов и технологий (NIST) . ^{[32] [1]}

КРИСТАЛЛЫ-Дилитий

CRYSTALS-Dilithium или просто Dilithium ^{[27] [28]} построен на module-LWE и module-SIS. Dilithium был выбран NIST в качестве основы для стандарта цифровой подписи. ^[1] Согласно сообщению Рэя Перлнера, написанному от имени команды NIST PQC, стандарт подписи NIST module-LWE должен быть основан на версии 3.1 спецификации Dilithium. Изменения NIST в Dilithium 3.1 направлены на поддержку дополнительной случайности в подписи (хеджированная подпись) и другие улучшения. ^[33]

Dilithium была одной из двух схем цифровой подписи, изначально выбранных NIST в процессе постквантовой криптографии; другой схемой была SPHINCS⁺, которая основана не на решетках, а на хэшах.

В августе 2023 года NIST опубликовал FIPS 204 (первоначальный публичный проект) и начал называть Dilithium алгоритмом цифровой подписи на основе модульной решетки (ML-DSA). ^[34]

По словам Фалько Стренцке , по состоянию на октябрь 2023 года ML-DSA внедряется как часть Libgcrypt . ^[35]

Безопасность

Криптографические конструкции на основе решеток имеют большие перспективы для постквантовой криптографии с открытым ключом . ^[36] Действительно, основными альтернативными формами криптографии с открытым ключом являются схемы, основанные на сложности факторизации и связанных с ней проблемах , и схемы, основанные на сложности дискретного логарифма и связанных с ней проблемах . Однако известно, что и факторизация, и проблема дискретного логарифма разрешимы за полиномиальное время на квантовом компьютере . ^[37] Более того, алгоритмы факторизации имеют тенденцию давать алгоритмы для дискретного логарифма, и наоборот. Это дополнительно мотивирует изучение конструкций, основанных на альтернативных предположениях, таких как сложность решеточных проблем.

Известно, что многие решетчатые криптографические схемы безопасны, если предположить, что наихудшая сложность определенных решетчатых проблем нарушит их. ^{[3] [6] [7]} То есть, если существует алгоритм, который может эффективно взломать криптографическую схему с не пренебрежимо малой вероятностью, то существует эффективный алгоритм, который решает определенную решетчатую проблему на любых входных данных. Однако для практических решетчатых конструкций (таких как схемы, основанные на NTRU, и даже схемы, основанные на LWE с эффективными параметрами) значимые гарантии безопасности, основанные на редукции, неизвестны.

Оценки уровней безопасности, предоставляемые аргументами редукции от сложных проблем - основанные на рекомендуемых размерах параметров, стандартных оценках вычислительной сложности сложных проблем и подробном изучении шагов редукции - называются конкретной безопасностью и иногда доказуемой безопасностью, ориентированной на практику . ^[38] Авторы, исследовавшие конкретную безопасность для криптосистем на основе решеток, обнаружили, что доказуемые результаты безопасности для таких систем не обеспечивают никакой значимой конкретной безопасности для практических значений параметров. ^{[39] [40]}

Функциональность

Для многих криптографических примитивов единственные известные конструкции основаны на решетках или тесно связанных объектах. Эти примитивы включают полностью гомоморфное шифрование , ^[13] неразличимость обфускации , ^[41] криптографические мультилинейные карты и функциональное шифрование . ^[41]

Смотрите также

• Проблемы с решеткой
• Обучение на ошибках
• Гомоморфное шифрование
• Постквантовая криптография
• Кольцевое обучение с ошибками
• Кольцевое обучение с ошибками обмена ключами

Ссылки

1. CSRC, Национальный институт стандартов и технологий. Постквантовая криптография. 2019. Доступно в Интернете по адресу <https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/>, дата обращения 2 ноября 2022 г.
2. «Стандарт цифровой подписи на основе модульной решетки» (PDF) . NIST.gov . Август 2024 г.
3. Ajtai, Miklós (1996). "Generating Hard Instances of Lattice Problems". Труды Двадцать восьмого ежегодного симпозиума ACM по теории вычислений . стр. 99–108. CiteSeerX 10.1.1.40.2489 . doi :10.1145/237814.237838. ISBN  978-0-89791-785-8. S2CID  6864824.
4. Криптосистема с открытым ключом с эквивалентностью наихудшего и среднего случая.
5. Хоффштейн, Джеффри; Пайфер, Джилл; Сильверман, Джозеф Х. (1998). "NTRU: криптосистема с открытым ключом на основе кольца". Алгоритмическая теория чисел . Конспект лекций по информатике. Том 1423. С. 267–288. CiteSeerX 10.1.1.25.8422 . doi :10.1007/bfb0054868. ISBN  978-3-540-64657-0.
6. Regev, Oded (2005-01-01). "О решетках, обучении с ошибками, случайных линейных кодах и криптографии". Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений – STOC '05 . ACM. стр. 84–93. CiteSeerX 10.1.1.110.4776 . doi :10.1145/1060590.1060603. ISBN  978-1581139600. S2CID  53223958.
7. Peikert, Chris (2009-01-01). "Криптосистемы с открытым ключом из проблемы наихудшего кратчайшего вектора". Труды 41-го ежегодного симпозиума ACM на Симпозиуме по теории вычислений – STOC '09 . ACM. стр. 333–342. CiteSeerX 10.1.1.168.270 . doi :10.1145/1536414.1536461. ISBN  9781605585062. S2CID  1864880.
8. Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien (2013-01-01). "Классическая сложность обучения с ошибками". Труды 45-го ежегодного симпозиума ACM на Симпозиуме по теории вычислений – STOC '13 . ACM. С. 575–584. arXiv : 1306.0281 . doi : 10.1145/2488608.2488680. ISBN 9781450320290. S2CID  6005009.
9. Любашевский, Вадим; Пейкерт, Крис; Регев, Одед (2010-05-30). «Об идеальных решетках и обучении с ошибками в кольцах». Достижения в криптологии – EUROCRYPT 2010. Конспект лекций по информатике. Том 6110. С. 1–23. CiteSeerX 10.1.1.352.8218 . doi :10.1007/978-3-642-13190-5_1. ISBN  978-3-642-13189-9.
10. Peikert, Chris (2014-07-16). "Решеточная криптография для Интернета" (PDF) . IACR . Получено 2017-01-11 .
11. Алким, Эрдем; Дюкас, Лео; Пёппельманн, Томас; Швабе, Питер (2015-01-01). «Постквантовый обмен ключами – новая надежда». Архив Cryptology ePrint .
12. Бос, Йоппе; Костелло, Крейг; Дукас, Лео; Миронов Илья; Наэриг, Майкл; Николаенко Валерия; Рагунатан, Анант; Стебила, Дуглас (01 января 2016 г.). «Фродо: Сними кольцо! Практичный квантово-безопасный обмен ключами от LWE». Архив электронной печати по криптологии .
13. Джентри, Крейг (2009-01-01). Полностью гомоморфная схема шифрования (диссертация). Стэнфорд, Калифорния, США: Стэнфордский университет.
14. НГУЕН, Фон. Криптоанализ криптосистемы Голдрайха-Гольдвассера-Халеви из Crypto '97. В Crypto '99: Труды 19-й ежегодной международной криптологической конференции по достижениям в криптологии , страницы 288–304, Лондон, Великобритания, 1999. Springer-Verlag.
15. Бракерски, Звика; Вайкунтанатан, Винод (2011). «Эффективное полностью гомоморфное шифрование из (стандартного) LWE». Архив Cryptology ePrint .
16. Бракерски, Звика; Вайкунтанатан, Винод (2013). «FHE на основе решетки так же безопасен, как PKE». Архив электронной печати по криптологии .
17. "LASH: A Lattice Based Hash Function". Архивировано из оригинала 16 октября 2008 г. Получено 2008-07-31 .
18. Контини, Скотт; Матусевич, Кристиан; Пиепшик, Йозеф; Штайнфельд, Рон; Го, Цзянь; Лин, Сан; Ван, Хуасюн (2008). "Криптоанализ LASH" (PDF) . Быстрое программное шифрование . Конспект лекций по информатике. Том 5086. С. 207–223. doi :10.1007/978-3-540-71039-4_13. ISBN 978-3-540-71038-7. S2CID  6207514.
19. AVANZI, R. et al. CRYSTALS-KYBER Algorithm Specifications And Supporting Documentation. CRYSTALS Team, 2021. Доступно в Интернете по адресу <https: //www.pq-crystals.org/>, дата обращения 4 ноября 2022 г.
20. Raimondo, Gina M. и Locascio, Laurie E., FIPS 203 (Draft) Federal Information Processing Standards Publication – Module-Lattice-based Key-Encapsulation Mechanism Standard. 24 августа 2023 г. Лаборатория информационных технологий, Национальный институт стандартов и технологий. Гейтерсберг, Мэриленд, Соединенные Штаты Америки. DOI 10.6028/NIST.FIPS.203.ipd. Доступно в Интернете по адресу <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf>, по состоянию на 30 октября 2023 г.
21. Команда FrodoKEM. FrodoKEM. 2022. Доступно в Интернете по адресу <https://frodokem.org/>, дата обращения 2 ноября 2022 г.
22. ALKIM, E. et al. Спецификации алгоритма инкапсуляции ключей обучения FrodoKEM с ошибками и сопроводительная документация. 2020. Доступно в Интернете по адресу <https://frodokem.org/files/FrodoKEM-specification-20200930.pdf>, дата обращения 1 ноября 2022 г.
23. Бернстайн, Дэниел Дж. В документации FrodoKEM утверждается, что «наборы параметров FrodoKEM с большим запасом соответствуют целевым уровням безопасности». Предупреждение: это неправда. Отправьте 2^40 шифротекстов на открытый ключ frodokem640; один из них будет расшифрован крупномасштабной атакой, осуществимой сегодня. 2022. Доступно в Интернете по адресу <https://twitter.com/hashbreaker/status/1587184970258255872>, просмотрено 2 ноября 2022 г.
24. SCHWABE, Peter et al. Веб-сайт NewHope. 2022. Доступно в Интернете по адресу <https://newhopecrypto.org/>, просмотрено 6 декабря 2022 г.
25. Бернстайн, Дэниел Дж. и др., NTRU Prime: раунд 3. 2020. Доступно в Интернете по адресу <https://ntruprime.cr.yp.to/>, дата обращения 8 ноября 2022 г.
26. D'ANVERS, Jan-Pieter, KARMAKAR, Angshuman, ROY, Sujoy Sinha и VERCAUTEREN, Frederik. Saber: обмен ключами на основе Module-LWR, шифрование CPA-secure и KEM-secure CCA. 2018. Доступно в Интернете по адресу <https://eprint.iacr.org/2018/230>, дата обращения 5 ноября 2022 г.
27. BAI, S. et al. CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation (Version 3.1). CRYSTALS Team, 2021. Доступно в Интернете по адресу <https://www.pq-crystals.org/>, просмотрено 2 ноября 2021 г.
28. SEILER, Gregor et al. pq-crystals/dilithium (Dilithium на GitHub), 2022. Доступно в Интернете по адресу <https://github.com/pq-crystals/dilithium>, просмотрено 29 декабря 2022 г.
29. FOUQUE, Pierre-Alain et al. Falcon: Компактные подписи на основе решеток быстрого преобразования Фурье в NTRU. 2020. Доступно в Интернете по адресу <https://falcon-sign.info/>, дата обращения 8 ноября 2020 г.
30. Гюнейсу, Тим; Любашевский, Вадим; Пёппельманн, Томас (2012). «Практическая решеточная криптография: схема подписи для встроенных систем» (PDF) . Криптографическое оборудование и встроенные системы – CHES 2012 . Конспект лекций по информатике. Том 7428. IACR. С. 530–547. doi :10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1. Получено 11.01.2017 .
31. ЭСПИТАУ, Томас и др. МИТАКА: более простой, параллелизуемый и маскируемый вариант Falcon. 2021.
32. ALKIM, E. et al. Схема цифровой подписи на основе решетки qTESLA. IACR, 2019. Архив Cryptology ePrint, отчет 2019/085. Доступно в Интернете по адресу <https://eprint.iacr.org/2019/085>, просмотрено 1 НОЯБРЯ 2022 г.
33. Perlner, Ray A.. Планируемые изменения в спецификации Dilithium. 20 апреля 2023 г. Группы Google. Доступно в Интернете по адресу <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/3pBJsYjfRw4/m/GjJ2icQkAQAJ>, просмотрено 14 июня 2023 г.
34. Raimondo, Gina M. и Locascio, Laurie E., FIPS 204 (Draft) Federal Information Processing Standards Publication – Module-Lattice-Based Digital Signature Standard. 24 августа 2023 г. Лаборатория информационных технологий Национального института стандартов и технологий. Гейтерсберг, Мэриленд, Соединенные Штаты Америки. DOI 10.6028/NIST.FIPS.204.ipd. Доступно в Интернете по адресу <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf>, дата обращения 2 сентября 2023 г.
35. Список рассылки Gcrypt-devel. Реализация Dilithium в Libgcrypt. 24 октября 2023 г. Доступно в Интернете по адресу <https://lists.gnupg.org/pipermail/gcrypt-devel/2023-October/005572.html>, дата обращения 24 октября 2023 г.
36. Micciancio, Daniele; Regev, Oded (2008-07-22). "Криптография на основе решеток" (PDF) . Nyu.edu . Получено 2017-01-11 .
37. Шор, Питер В. (1997-10-01). «Алгоритмы полиномиального времени для разложения на простые множители и дискретных логарифмов на квантовом компьютере». Журнал SIAM по вычислениям . 26 (5): 1484–1509. arXiv : quant-ph/9508027 . doi : 10.1137/S0097539795293172. ISSN  0097-5397. S2CID  2337707.
38. Белларе, Михир (1998), Практически-ориентированная доказуемая безопасность , Lecture Notes in Computer Science, т. 1396, Springer-Verlag, стр. 221–231, doi :10.1007/BFb0030423
39. Коблиц, Нил; Самайдер, Субхабрата; Саркар, Палаш; Сингха, Субхадип (2022). «Конкретный анализ приближенного идеального SIVP для сокращения кольца решений LWE». Успехи в области математики коммуникаций . doi : 10.3934/amc.2022082 .
40. Гертнер, Джоэл (2023), Конкретная безопасность от худшего случая к среднему случаю сокращения решетки, Lecture Notes in Computer Science, т. 14064, Springer-Verlag, стр. 344–369, ISBN 978-3-031-37678-8
41. Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2013-01-01). "Обфускация неразличимости кандидатов и функциональное шифрование для всех схем". Архив Cryptology ePrint . CiteSeerX 10.1.1.400.6501 . 

Библиография

• Одед Голдрайх, Шафи Голдвассер и Шай Халеви. «Криптосистемы с открытым ключом из проблем сокращения решеток». В Crypto '97: Труды 17-й ежегодной международной криптологической конференции по достижениям в криптологии , страницы 112–131, Лондон, Великобритания, 1997. Springer-Verlag.
• Одед Регев. Криптография на основе решеток. В Advances in cryptology (CRYPTO) , страницы 131–141, 2006.