✖


Jump to content

Решеточная криптография

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

История [ править ]

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

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

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

Математическая основа [ править ]

В линейной решетка алгебре — множество всех целочисленных линейных комбинаций векторов из базиса из . Другими словами, Например, представляет собой решетку, порожденную стандартным базисом для . Важно отметить, что основа решетки не уникальна. Например, векторы , , и создать альтернативную основу для .

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

Избранные решетчатые схемы [ править ]

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

Шифрование [ править ]

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

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

Гомоморфное шифрование [ править ]

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

  • Оригинальная схема Джентри. [12]
  • Бракерски и Вайкунтанатан. [14] [15]

Хэш-функции [ править ]

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

Обмен ключами [ править ]

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

  • КРИСТАЛЛЫ-Кибер , [18] который построен на модульном обучении с ошибками (модуль-LWE). Kyber был выбран NIST для стандартизации в 2023 году. [1] В августе 2023 года NIST опубликовал FIPS 203 (первоначальный общедоступный проект) и начал называть свою версию Kyber механизмом инкапсуляции ключей на основе модульной решетки (ML-KEM). [19]
  • ФродоКЭМ, [20] [21] схема, основанная на проблеме обучения с ошибками (LWE). FrodoKEM присоединилась к конкурсу по стандартизации, проведенному Национальным институтом стандартов и технологий (NIST) . [1] и дожил до 3-го раунда процесса. Затем от него отказались из-за низкой производительности. В октябре 2022 года в аккаунте в Твиттере, связанном с криптологом Дэниелом Дж. Бернстайном, были опубликованы сообщения о проблемах безопасности в frodokem640. [22]
  • NewHope основан на проблеме кольцевого обучения с ошибками (RLWE). [23]
  • НТРУ Прайм. [24]
  • Работа Пейкерта , в основе которой лежит проблема кольцевого обучения с ошибками (RLWE). [9]
  • Чтобы знать, [25] который основан на проблеме обучения модуля с округлением (модуль-LWR).

Подписание [ править ]

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

  • КРИСТАЛЛЫ-Дилития, [26] [27] который построен на модульном обучении с ошибками (модуль-LWE) и модульном решении для коротких целых чисел (модуль-SIS). Дилитий был выбран для стандартизации NIST. [1] Согласно сообщению Рэя Перлнера, написанному от имени команды NIST PQC, стандарт подписи модуля NIST-LWE должен быть основан на версии 3.1 спецификации Dilithium.
  • Falcon , основанный на решении коротких целых чисел (SIS) поверх NTRU. Falcon был выбран для стандартизации NIST. [28] [1]
  • Схема подписи GGH .
  • Работа Гюнейсу, Любашевского и Пёппельмана, основанная на кольцевом обучении с ошибками (RLWE). [29]

КРИСТАЛЛЫ-Дилития [ править ]

КРИСТАЛЛЫ-Дилития или просто Дилития [26] [27] построен на модуле LWE и модуле SIS. Дилитий был выбран NIST в качестве основы для стандарта цифровой подписи. [1] Согласно сообщению Рэя Перлнера, написанному от имени команды NIST PQC, стандарт подписи модуля NIST-LWE должен быть основан на версии 3.1 спецификации Dilithium. Изменения NIST в Dilithium 3.1 направлены на поддержку дополнительной случайности при подписании (хеджированная подпись) и других улучшений. [32]

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

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

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

Безопасность [ править ]

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

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

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

Функциональность [ править ]

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

См. также [ править ]

Ссылки [ править ]

  1. ↑ Перейти обратно: Перейти обратно: а б с д и ж г CSRC, Национальный институт стандартов и технологий. Постквантовая криптография. 2019. Доступно в Интернете по адресу < https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/ >, по состоянию на 2 ноября 2022 г.
  2. ↑ Перейти обратно: Перейти обратно: а б Айтай, Миклош (1996). «Создание жестких примеров решеточных задач». Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений . стр. 99–108. CiteSeerX   10.1.1.40.2489 . дои : 10.1145/237814.237838 . ISBN  978-0-89791-785-8 . S2CID   6864824 .
  3. ^ Криптосистема с открытым ключом с эквивалентностью наихудшего/среднего случая .
  4. ^ Хоффштейн, Джеффри; Пайфер, Джилл; Сильверман, Джозеф Х. (1998). «NTRU: кольцевая криптосистема с открытым ключом». Алгоритмическая теория чисел . Конспекты лекций по информатике. Том. 1423. стр. 267–288. CiteSeerX   10.1.1.25.8422 . дои : 10.1007/bfb0054868 . ISBN  978-3-540-64657-0 .
  5. ↑ Перейти обратно: Перейти обратно: а б Регев, Одед (1 января 2005 г.). «О решетках, обучении с ошибками, случайных линейных кодах и криптографии». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений – STOC '05 . АКМ. стр. 84–93. CiteSeerX   10.1.1.110.4776 . дои : 10.1145/1060590.1060603 . ISBN  978-1581139600 . S2CID   53223958 .
  6. ↑ Перейти обратно: Перейти обратно: а б Пейкерт, Крис (1 января 2009 г.). «Криптосистемы с открытым ключом из наихудшего случая задачи кратчайшего вектора». Материалы 41-го ежегодного симпозиума ACM по теории вычислений – STOC '09 . АКМ. стр. 333–342. CiteSeerX   10.1.1.168.270 . дои : 10.1145/1536414.1536461 . ISBN  9781605585062 . S2CID   1864880 .
  7. ^ Бракерски, Цвика; Ланглуа, Аделина; Пейкерт, Крис; Регев, Одед; Стеле, Дэмиен (01 января 2013 г.). «Классическая трудность обучения с ошибками». Материалы 45-го ежегодного симпозиума ACM по теории вычислений – STOC '13 . АКМ. стр. 575–584. arXiv : 1306.0281 . дои : 10.1145/2488608.2488680 . ISBN  9781450320290 . S2CID   6005009 .
  8. ^ Любашевский Вадим; Пейкерт, Крис; Регев, Одед (30 мая 2010 г.). «Об идеальных решетках и обучении с ошибками в кольцах». Достижения в криптологии – EUROCRYPT 2010 . Конспекты лекций по информатике. Том. 6110. стр. 1–23. CiteSeerX   10.1.1.352.8218 . дои : 10.1007/978-3-642-13190-5_1 . ISBN  978-3-642-13189-9 .
  9. ↑ Перейти обратно: Перейти обратно: а б Пейкерт, Крис (16 июля 2014 г.). «Решётчатая криптография для Интернета» (PDF) . МАКР . Проверено 11 января 2017 г.
  10. ^ Алким, Эрдем; Дукас, Лео; Поппельманн, Томас; Швабе, Питер (01 января 2015 г.). «Постквантовый обмен ключами – новая надежда» . Архив электронной печати по криптологии .
  11. ^ Бос, Йоппе; Костелло, Крейг; Дукас, Лео; Миронов Илья; Наэриг, Майкл; Николаенко Валерия; Рагунатан, Анант; Стебила, Дуглас (01 января 2016 г.). «Фродо: Сними кольцо! Практичный квантово-безопасный обмен ключами от LWE» . Архив электронной печати по криптологии .
  12. ↑ Перейти обратно: Перейти обратно: а б с Джентри, Крейг (1 января 2009 г.). Полностью гомоморфная схема шифрования (Диссертация). Стэнфорд, Калифорния, США: Стэнфордский университет.
  13. ^ НГУЕН, фон. Криптоанализ криптосистемы Гольдрайха-Гольдвассера-Халеви от crypto '97. В Crypto '99: материалы 19-й ежегодной международной конференции по криптологии, посвященной достижениям в криптологии , страницы 288–304, Лондон, Великобритания, 1999. Springer-Verlag.
  14. ^ Бракерски, Цвика; Вайкунтанатан, Винод (2011). «Эффективное полностью гомоморфное шифрование из (стандартного) LWE» . Архив электронной печати по криптологии .
  15. ^ Бракерски, Цвика; Вайкунтанатан, Винод (2013). «FHE на основе решетки так же безопасен, как PKE» . Архив электронной печати по криптологии .
  16. ^ «LASH: решетчатая хэш-функция» . Архивировано из оригинала 16 октября 2008 года . Проверено 31 июля 2008 г.
  17. ^ Контини, Скотт; Матусевич, Кристиан; Пепшик, Йозеф; Стейнфельд, Рон; Го, Цзянь; Линг, Сан; Ван, Хуасюн (2008). «Криптоанализ LASH» (PDF) . Быстрое программное шифрование . Конспекты лекций по информатике. Том. 5086. стр. 207–223. дои : 10.1007/978-3-540-71039-4_13 . ISBN  978-3-540-71038-7 . S2CID   6207514 .
  18. ^ АВАНЦИ, Р. и др. Спецификации алгоритма CRYSTALS-KYBER и сопроводительная документация. Команда КРИСТАЛЛЫ, 2021. Доступно в Интернете по адресу <https://www.pq-crystals.org/>, по состоянию на 4 ноября 2022 г.
  19. ^ Раймондо, Джина М., и Локаскио, Лори Э., FIPS 203 (проект) Публикация федеральных стандартов обработки информации - Стандарт механизма инкапсуляции ключей на основе модульной решетки. 24 августа 2023 г. Лаборатория информационных технологий Национального института стандартов и технологий. Гейтерсбург, Мэриленд, Соединенные Штаты Америки. DOI 10.6028/NIST.FIPS.203.ipd. Доступно в Интернете по адресу < https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf >, по состоянию на 30 октября 2023 г.
  20. ^ Команда ФродоКЕМ. ФродоКЕМ. 2022. Доступно в Интернете по адресу < https://frodokem.org/ >, по состоянию на 2 ноября 2022 г.
  21. ^ АЛКИМ, Э. и др. Обучение FrodoKEM с ошибками. Спецификации алгоритма инкапсуляции ключей и сопроводительная документация. 2020. Доступно в Интернете по адресу < https://frodokem.org/files/FrodoKEM-specification-20200930.pdf >, по состоянию на 1 ноября 2022 г.
  22. ^ Бернштейн, Дэниел Дж. В документации FrodoKEM утверждается, что «наборы параметров FrodoKEM комфортно соответствуют целевым уровням безопасности с большим запасом». Предупреждение: это неправда. Отправьте 2^40 зашифрованных текстов на открытый ключ frodokem640; один из них будет расшифрован в результате крупномасштабной атаки, осуществимой сегодня. 2022. Доступно в Интернете по адресу < https://twitter.com/hashbreaker/status/1587184970258255872 >, по состоянию на 2 ноября 2022 г.
  23. ^ ШВАБЕ, Питер и др. Веб-сайт NewHope. 2022. Доступно в Интернете по адресу < https://newhopecrypto.org/ >, по состоянию на 6 декабря 2022 г.
  24. ^ Бернштейн, Дэниел Дж. и др., NTRU Prime: раунд 3. 2020. Доступно в Интернете по адресу < https://ntruprime.cr.yp.to/ >, доступ осуществлен 8 ноября 2022 г.
  25. ^ Д'АНВЕРС, Ян-Питер, КАРМАКАР, Ангшуман, РОЙ, Суджой Синха и ВЕРКАУТЕРЕН, Фредерик. Sabre: обмен ключами на основе Module-LWR, шифрование с защитой CPA и KEM с защитой CCA. 2018. Доступно в Интернете по адресу < https://eprint.iacr.org/2018/230 >, по состоянию на 5 ноября 2022 г.
  26. ↑ Перейти обратно: Перейти обратно: а б БАЙ, С. и др. Спецификации алгоритма CRYSTALS-Dilitium и сопроводительная документация (версия 3.1). Команда CRYSTALS, 2021 г. Доступно в Интернете по адресу < https://www.pq-crystals.org/ >, по состоянию на 2 ноября 2021 г.
  27. ↑ Перейти обратно: Перейти обратно: а б ЗЕЙЛЕР, Грегор и др. pq-crystals/dilithium (Dilithium на GitHub), 2022 г. Доступно в Интернете по адресу < https://github.com/pq-crystals/dilithium >, доступ осуществлен 29 декабря 2022 г.
  28. ^ ФУК, Пьер-Ален и др. Falcon: компактные сигнатуры на основе решетки быстрого Фурье через NTRU. 2020. Доступно в Интернете по адресу < https://falcon-sign.info/ >, по состоянию на 8 ноября 2020 г.
  29. ^ Гюнейсу, Тим; Любашевский Вадим; Пёппельманн, Томас (2012). «Практическая решетчатая криптография: схема подписи для встраиваемых систем» (PDF) . Криптографическое оборудование и встраиваемые системы – CHES 2012 . Конспекты лекций по информатике. Том. 7428. МАКР. стр. 530–547. дои : 10.1007/978-3-642-33027-8_31 . ISBN  978-3-642-33026-1 . Проверено 11 января 2017 г.
  30. ^ ЭСПИТАУ, Томас и др. МИТАКА: более простой, параллелизуемый и маскируемый вариант Falcon. 2021.
  31. ^ АЛКИМ, Э. и др. Схема цифровой подписи на основе решетки qTESLA. IACR, 2019. Архив электронной печати криптологии, отчет 2019/085. Доступно в Интернете по адресу < https://eprint.iacr.org/2019/085 >, по состоянию на 1 НОЯБРЯ 2022 г.
  32. ^ Перлнер, Рэй А.. Планируемые изменения в спецификации Дилитиума. 20 апреля 2023 г. Группы Google. Доступно в Интернете по адресу < https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/3pBJsYjfRw4/m/GjJ2icQkAQAJ >, по состоянию на 14 июня 2023 г.
  33. ^ Раймондо, Джина М., и Локаскио, Лори Э., FIPS 204 (проект) Публикация федеральных стандартов обработки информации – Стандарт цифровой подписи на основе модульной решетки. 24 августа 2023 г. Лаборатория информационных технологий Национального института стандартов и технологий. Гейтерсбург, Мэриленд, Соединенные Штаты Америки. DOI 10.6028/NIST.FIPS.204.ipd. Доступно в Интернете по адресу < https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf >, доступ осуществлен 2 сентября 2023 г.
  34. ^ Список рассылки Gcrypt-devel. Реализация дилития в Libgcrypt. 24 октября 2023 г. Доступно в Интернете по адресу < https://lists.gnupg.org/pipermail/gcrypt-devel/2023-October/005572.html >, по состоянию на 24 октября 2023 г.
  35. ^ Миччанчо, Даниэле; Регев, Одед (22 июля 2008 г.). «Решеточная криптография» (PDF) . Нью.еду . Проверено 11 января 2017 г.
  36. ^ Шор, Питер В. (1 октября 1997 г.). «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере». SIAM Journal по вычислительной технике . 26 (5): 1484–1509. arXiv : Quant-ph/9508027 . дои : 10.1137/S0097539795293172 . ISSN   0097-5397 . S2CID   2337707 .
  37. ^ Белларе, Михир (1998), Практико-ориентированная доказуемая безопасность , Конспекты лекций по информатике, том. 1396, Springer-Verlag, стр. 221–231, doi : 10.1007/BFb0030423.
  38. ^ Коблиц, Нил; Самайдер, Субхабрата; Саркар, Палаш; Сингха, Субхадип (2022). «Конкретный анализ приближенного идеала-SIVP к сокращению кольца решений-LWE» . Достижения в математике связи . дои : 10.3934/amc.2022082 .
  39. ^ Гертнер, Джоэл (2023), Конкретная безопасность от наихудшего случая к среднему сокращению решетки , Конспекты лекций по информатике, том. 14064, Springer-Verlag, стр. 344–369, ISBN.  978-3-031-37678-8
  40. ↑ Перейти обратно: Перейти обратно: а б Гарг, Санджам; Джентри, Крейг; Халеви, Шай; Райкова, Мариана; Сахай, Амит; Уотерс, Брент (1 января 2013 г.). «Кандидат на неразличимость, обфускацию и функциональное шифрование для всех схем» . Архив электронной печати по криптологии . CiteSeerX   10.1.1.400.6501 .

Библиография [ править ]

  • Одед Гольдрейх, Шафи Гольдвассер и Шай Халеви. «Криптосистемы с открытым ключом из задач редукции решетки». В Crypto '97: материалы 17-й ежегодной международной конференции по криптологии, посвященной достижениям в криптологии , страницы 112–131, Лондон, Великобритания, 1997. Springer-Verlag.
  • Одед Регев. Решётчатая криптография. В «Достижениях в криптологии» (CRYPTO) , страницы 131–141, 2006 г.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Lattice-based_cryptography&oldid=1209231233"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 18c10653e99617e60df0dc36aa1ac63e__1708457700
URL1:https://arc.ask3.ru/arc/aa/18/3e/18c10653e99617e60df0dc36aa1ac63e.html
Заголовок, (Title) документа по адресу, URL1:
Lattice-based cryptography - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)