Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

Решетки является множество всех целочисленных линейных комбинаций базисных векторов . Т.е., например, это решетка, порожденная стандартным ортонормированным базисом для . Принципиально то, что основа решетки не уникальна. Например, векторы , и образуют альтернативную основу для .

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

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

Схемы шифрования [ править ]

  • Кольцо Пайкерта - Обучение с ошибками (Ring-LWE) Обмен ключами [8]
  • Схема шифрования GGH
  • NTRUEncrypt

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

  • Кольцо Гюнесу, Любашевского и Попплемана - Обучение с ошибками (Ring-LWE) Подпись [12]
  • Схема подписи GGH
  • NTRUSign

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

  • SWIFFT
  • LASH (хеш-функция на основе решетки) [13] [14]

Полностью гомоморфное шифрование [ править ]

См. Также: Полностью гомоморфное шифрование
  • Оригинальная схема Джентри. [11]
  • Бракерски и Вайкунтанатан. [15] [16]

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

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

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

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

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

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

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

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

  1. ^ a b Ajtai, Miklós (1996). «Генерация жестких экземпляров решетчатых задач». Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений . С. 99–108. CiteSeerX  10.1.1.40.2489 . DOI : 10.1145 / 237814.237838 . ISBN 978-0-89791-785-8. S2CID  6864824 .
  2. ^ Криптосистема с открытым ключом с эквивалентностью наихудшего / среднего случая
  3. ^ Хоффштейн, Джеффри; Пайфер, Джилл; Сильверман, Джозеф Х. (1998). «NTRU: криптосистема с открытым ключом на основе кольца». Алгоритмическая теория чисел . Конспект лекций по информатике. 1423 . С. 267–288. CiteSeerX 10.1.1.25.8422 . DOI : 10.1007 / bfb0054868 . ISBN  978-3-540-64657-0.
  4. ^ a b Регев, Одед (1 января 2005 г.). «На решетках, обучение с ошибками, случайные линейные коды и криптография». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05 . ACM. С. 84–93. CiteSeerX 10.1.1.110.4776 . DOI : 10.1145 / 1060590.1060603 . ISBN  978-1581139600. S2CID  53223958 .
  5. ^ a b Пайкерт, Крис (1 января 2009 г.). «Криптосистемы с открытым ключом из задачи кратчайшего вектора наихудшего случая». Материалы 41-го ежегодного симпозиума ACM по теории вычислений - STOC '09 . ACM. С. 333–342. CiteSeerX 10.1.1.168.270 . DOI : 10.1145 / 1536414.1536461 . ISBN  9781605585062. S2CID  1864880 .
  6. ^ Бракерски, Цвика; Ланглуа, Аделина; Пайкерт, Крис; Регев, Одед; Стеле, Дэмиен (1 января 2013 г.). «Классическая трудность обучения с ошибками». Материалы 45-го ежегодного симпозиума ACM по теории вычислений - STOC '13 . ACM. С. 575–584. arXiv : 1306.0281 . DOI : 10.1145 / 2488608.2488680 . ISBN 9781450320290. S2CID  6005009 .
  7. ^ a b Любашевский, Вадим; Пайкерт, Крис; Регев, Одед (30 мая 2010 г.). Об идеальных решетках и обучении с ошибками по кольцам . Достижения в криптологии - 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.
  8. ^ a b Пайкерт, Крис (2014-07-16). «Решеточная криптография для Интернета» (PDF) . МАКР . Проверено 11 января 2017 .
  9. ^ Алким, Эрдем; Дукас, Лео; Пёппельманн, Томас; Швабе, Питер (01.01.2015). «Постквантовый обмен ключами - новая надежда» . Цитировать журнал требует |journal=( помощь )
  10. ^ Bos, Joppe; Костелло, Крейг; Дукас, Лео; Миронов Илья; Naehrig, Майкл; Николаенко, Валерия; Рагхунатан, Анант; Стебила, Дуглас (01.01.2016). «Фродо: Снимите кольцо! Практический квантово-безопасный обмен ключами от LWE» . Цитировать журнал требует |journal=( помощь )
  11. ^ a b c Джентри, Крейг (01.01.2009). Схема полностью гомоморфного шифрования (тезис). Стэнфорд, Калифорния, США: Стэнфордский университет.
  12. ^ Güneysu, Тим; Любашевский, Вадим; Пёппельманн, Томас (2012). «Практическая криптография на основе решеток: схема подписи для встроенных систем» (PDF) . Криптографическое оборудование и встроенные системы - CHES 2012 . Конспект лекций по информатике. 7428 . МАКР. С. 530–547. DOI : 10.1007 / 978-3-642-33027-8_31 . ISBN  978-3-642-33026-1. Проверено 11 января 2017 .
  13. ^ "LASH: Хеш-функция на основе решетки" . Архивировано 16 октября 2008 года . Проверено 31 июля 2008 .CS1 maint: bot: исходный статус URL неизвестен ( ссылка ) (сломанный)
  14. ^ Скотт Контини, Кристиан Матусевич, Йозеф Пипшик, Рон Стейнфельд, Цзянь Гуо, Сан Линь и Хуаксионг Ван (2008). «Криптоанализ LASH» (PDF) . Быстрое программное шифрование . Конспект лекций по информатике. 5086 . С. 207–223. DOI : 10.1007 / 978-3-540-71039-4_13 . ISBN  978-3-540-71038-7.CS1 maint: uses authors parameter (link)
  15. ^ Бракерски, Цвика; Вайкунтанатан, Винод (2011). «Эффективное полностью гомоморфное шифрование из (стандартного) LWE» . Cite journal requires |journal= (help)
  16. ^ Бракерски, Цвика; Вайкунтанатан, Винод (2013). «Решетчатый FHE такой же безопасный, как и PKE» . Cite journal requires |journal= (help)
  17. ^ Micciancio, Даниэле; Регев, Одед (22 июля 2008 г.). «Криптография на основе решеток» (PDF) . Проверено 11 января 2017 . Cite journal requires |journal= (help)
  18. ^ Шор, Питер В. (1997-10-01). "Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере". SIAM Journal on Computing . 26 (5): 1484–1509. arXiv : квант-ph / 9508027 . DOI : 10,1137 / S0097539795293172 . ISSN 0097-5397 . S2CID 2337707 .  
  19. ^ а б Гарг, Санджам; Джентри, Крейг; Халеви, Шай; Райкова, Марьяна; Сахай, Амит; Уотерс, Брент (01.01.2013). «Возможное запутывание неразличимости и функциональное шифрование для всех схем» . CiteSeerX 10.1.1.400.6501 .  Cite journal requires |journal= (help)

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

  • Одед Гольдрайх, Шафи Гольдвассер и Шай Халеви. «Криптосистемы с открытым ключом от задач редукции решетки». В CRYPTO '97: Материалы 17-й ежегодной международной криптологической конференции по достижениям в криптологии , страницы 112–131, Лондон, Великобритания, 1997. Springer-Verlag.
  • Фонг К. Нгуен. «Криптоанализ криптосистемы Голдрайха – Гольдвассера – Галеви из крипто-97». В CRYPTO '99: Материалы 19-й ежегодной международной криптологической конференции по достижениям в криптологии , страницы 288–304, Лондон, Великобритания, 1999. Springer-Verlag.
  • Одед Регев. Криптография на основе решеток. В « Достижения в криптологии» (CRYPTO) , страницы 131–141, 2006 г.