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

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

История

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

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

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

Математический фон

А решетка ${displaystyle Lsubset mathbb {R} ^{n}}$ - множество всех целочисленных линейных комбинаций базисных векторов ${displaystyle mathbf {b} _{1},ldots ,mathbf {b} _{n}in 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), который просит нас аппроксимировать минимальную евклидову длину ненулевого вектора решетки. Считается, что эту проблему трудно решить эффективно даже с коэффициентами аппроксимации, полиномиальными от ${displaystyle n}$, и даже с квантовым компьютером. Известно, что многие (хотя и не все) криптографические конструкции на основе решеток являются безопасными, если SVP действительно сложен в этом режиме.

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

Схемы шифрования

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

Подписи

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

Хеш-функции

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

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

Смотрите также: Полностью гомоморфное шифрование

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

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

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

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

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

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

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

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

Рекомендации

1. Айтай, Миклош (1996). «Генерация трудных экземпляров решеточных задач». Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений. С. 99–108. CiteSeerX  10.1.1.40.2489. Дои: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. Дои:10.1007 / bfb0054868. ISBN  978-3-540-64657-0.
4. Регев, Одед (01.01.2005). «На решетках, обучение с ошибками, случайные линейные коды и криптография». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05. ACM. С. 84–93. CiteSeerX  10.1.1.110.4776. Дои:10.1145/1060590.1060603. ISBN  978-1581139600. S2CID  53223958.
5. Пайкерт, Крис (2009-01-01). «Криптосистемы с открытым ключом из задачи кратчайшего вектора наихудшего случая». Материалы 41-го ежегодного симпозиума ACM по теории вычислений - STOC '09. ACM. С. 333–342. CiteSeerX  10.1.1.168.270. Дои:10.1145/1536414.1536461. ISBN  9781605585062. S2CID  1864880.
6. Бракерски, Цвика; Ланглуа, Аделина; Пайкерт, Крис; Регев, Одед; Стеле, Дэмиен (1 января 2013 г.). «Классическая трудность обучения с ошибками». Материалы 45-го ежегодного симпозиума ACM по теории вычислений - STOC '13. ACM. С. 575–584. arXiv:1306.0281. Дои:10.1145/2488608.2488680. ISBN  9781450320290. S2CID  6005009.
7. Любашевский, Вадим; Пайкерт, Крис; Регев, Одед (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.
8. Пайкерт, Крис (16.07.2014). «Решеточная криптография для Интернета» (PDF). МАКР. Получено 2017-01-11.
9. Алким, Эрдем; Дукас, Лео; Пёппельманн, Томас; Швабе, Питер (01.01.2015). «Постквантовый обмен ключами - новая надежда».
10. Бос, Йоппе; Костелло, Крейг; Дукас, Лео; Миронов Илья; Наэриг, Майкл; Николаенко, Валерия; Рагхунатан, Анант; Стебила, Дуглас (01.01.2016). «Фродо: Снимите кольцо! Практический квантово-безопасный обмен ключами от LWE».
11. Джентри, Крейг (01.01.2009). Схема полностью гомоморфного шифрования (Тезис). Стэнфорд, Калифорния, США: Стэнфордский университет.
12. Гюнесу, Тим; Любашевский, Вадим; Пёппельманн, Томас (2012). «Практическая криптография на основе решеток: схема подписи для встроенных систем» (PDF). Криптографическое оборудование и встроенные системы - CHES 2012. Конспект лекций по информатике. 7428. МАКР. С. 530–547. Дои:10.1007/978-3-642-33027-8_31. ISBN  978-3-642-33026-1. Получено 2017-01-11.
13. «LASH: хеш-функция на основе решетки». Архивировано 16 октября 2008 года.. Получено 2008-07-31. (сломанный)
14. Скотт Контини, Кристиан Матусевич, Йозеф Пипшик, Рон Штайнфельд, Цзянь Го, Сан Линь и Хуаксионг Ван (2008). «Криптоанализ LASH» (PDF). Быстрое программное шифрование. Конспект лекций по информатике. 5086. С. 207–223. Дои:10.1007/978-3-540-71039-4_13. ISBN  978-3-540-71038-7.
15. Бракерски, Цвика; Вайкунтанатан, Винод (2011). «Эффективное полностью гомоморфное шифрование из (стандартного) LWE».
16. Бракерски, Цвика; Вайкунтанатан, Винод (2013). «Решетчатый FHE так же безопасен, как PKE».
17. Микчанчо, Даниэле; Регев, Одед (22 июля 2008 г.). «Криптография на основе решеток» (PDF). Получено 2017-01-11.
18. Шор, Питер В. (1997-10-01). "Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере". SIAM Журнал по вычислениям. 26 (5): 1484–1509. arXiv:Quant-ph / 9508027. Дои:10.1137 / S0097539795293172. ISSN  0097-5397. S2CID  2337707.
19. Гарг, Санджам; Джентри, Крейг; Халеви, Шай; Райкова, Марьяна; Сахай, Амит; Уотерс, Брент (01.01.2013). «Возможное запутывание неразличимости и функциональное шифрование для всех схем». CiteSeerX  10.1.1.400.6501.

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

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