Идеальная решётка
Идеальная решётка — определённая математическая структура, которая используется для уменьшения числа параметров, необходимых для описания решёток (представляющих собой свободные коммутативные группы конечного ранга). Данный вид решёток часто встречается во многих областях математики, в частности, в разделе теории чисел. Таким образом идеальные решётки более эффективны в применении, чем другие решётки, применяющихся в криптографии. Идеальные решётки используются в криптографических системах с открытым ключом NTRUEncrypt и NTRUSign для построения эффективных криптографических примитивов. Также идеальные решётки составляют фундаментальную основу квантовой криптографии, которая защищает от атак, связанных с квантовыми компьютерами.
Введение
[править | править код]Схемы RSA и ECC, основанные либо на сложности факторизации, либо на сложности проблемы дискретного логарифма, являются самыми популярными асимметричными криптосистемами, которые для шифрования информации и её последующего расшифровывания используют различные ключи. Несмотря на преобладание схем RSA и ECC, они, как известно, подвержены атакам с использованием квантовых компьютеров[1]. Кроме того, RSA и ECC довольно неэффективны на очень небольших и ограниченных устройствах, таких как 8-битные микроконтроллеры AVR, использующиеся по сей день в различных областях, таких как робототехника, энергетика, спутниковые системы связи и многие другие. Возможной альтернативой упомянутых схем являются асимметричные криптосистемы, основанные на жёстких задачах в идеальных решётках[2]. Специальная алгебраическая структура идеальных решёток позволяет значительно уменьшить размеры ключа и шифротекста, обеспечивая при этом эффективную арифметику с использованием теоретико-числового преобразования. Таким образом благодаря использованию идеальных решёток повышается степень защиты зашифрованной информации[3].
Базовые понятия
[править | править код]![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/98/A_lattice_with_unit_balls_for_two_different.png/220px-A_lattice_with_unit_balls_for_two_different.png)
Теория решёток может быть описана с помощью линейной алгебры. Решётка обычно рассматривается как любая равномерно распределённая сетка точек в n-мерном реальном линейном пространстве со всеми координатами, являющимися целыми числами. Это множество образует группу при сложении по координатам и является дискретным, что означает, что для каждой точки в множестве есть открытый шар вокруг неё, который не содержит никакой другой точки множества, таким образом решёткой называется множество всех целочисленных линейных комбинаций заданного набора линейно независимых точек в . Решётки — являются группами, а идеальные решётки идеалами[4].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Two-dimensional_lattice_with_two_bases.png/220px-Two-dimensional_lattice_with_two_bases.png)
В частности, идеальные решётки соответствуют кольцам вида для некоторого неприводимого многочлена степени [5]. Основная операция в идеальной решёточной криптографии — полиномиальное умножение.
Математическое определение идеальной решётки
[править | править код]Идеальная решётка — это целочисленная решётка такая, что для некоторого заданного базиса такого, что и для некоторого приведённого многочлена степени существует идеал
Ограничения, накладываемые на :
- — должен быть неприводимым
- норма кольца не должна быть больше, чем норма для любого многочлена
- Лемма
Если является нормированным неприводимым целочисленным многочленом степени , то любой идеал есть изоморфная решётка полного ранга в ,то есть базис состоит из линейно независимых векторов, координаты которых и являются коэффициентам многочлена степени
![]() | В разделе не хватает ссылок на источники (см. рекомендации по поиску). |
Алгоритм идентификации идеальных решёток с базисами полного ранга
[править | править код]![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Algorithm_Ideal_lattice.png/440px-Algorithm_Ideal_lattice.png)
Пусть задан базис
Условие: если охватывает идеальную решётку относительно параметра , тогда правда, иначе ложь
- привести к эрмитовой форме
- , то есть — присоединённая матрица, — детерминант и
- если все столбцы кроме последнего нулевые тогда
- положить в ненулевой столбец (а именно, последний столбец )
- иначе вернуть ложь
- если , то есть множество элементов z, удовлетворяющих для всех тогда
- применить китайскую теорему об остатках для нахождения и
- иначе вернуть ложь
- если тогда
- вернуть правду,
- иначе вернуть ложь
Дополнение: матрица принимает вид
![]() | В разделе не хватает ссылок на источники (см. рекомендации по поиску). |
Пример использования алгоритма идентификации идеальных решёток с базисами полного ранга
[править | править код]Используя данный алгоритм[6], можно убедиться в том, что немногие решётки являются идеальными решётками[6].
Рассмотрим пример:
Пусть и , тогда
является идеальной, в отличие от
с пример, придуманным Любашевским В. и Миссиансио Д.[7]
Для использования данного алгоритма, матрица обязана являться эрмитовой нормальной формой, таким образом первый шаг алгоритма обязателен к выполнению. Детерминант равен, а присоединённая матрица
и наконец, произведение матриц есть
На этом этапе алгоритм останавливается, потому что все столбцы кроме последнего, должны быть равны нулю, если является идеальной решёткой.
Распространённые задачи теории решёток
[править | править код]- поиск кратчайшего вектора — поиск кратчайшего ненулевого вектора, по представленной произвольными базисными векторами решётке. В действительности, обычно рассматривается приближённый вариант задачи поиска кратчайшего вектора, целью которой — получение вектора в решётке, длина которого не превосходит длину кратчайшего ненулевого вектора в μ(n)-раз, где μ(n)- коэффициент приближения, а - размерность решётки.[8]
- поиск ближайшего вектора — обобщение задачи поиска кратчайшего вектора[9]
- поиск кратчайших независимых векторов[10].
Применение идеальных решёток
[править | править код]Хэш-функции, устойчивые к коллизиям
[править | править код]Устойчивая к коллизиям хеш-функция — это функция заданная отображением так, что мощность множества (области некоторого числового пространства) больше мощности множества , , тем самым затрудняя нахождение коллизии, то есть пару . Таким образом, по случайно выбранному ни один злоумышленник не сможет эффективно (за разумное время) найти коллизии в , даже несмотря на тот факт, что коллизии присутствуют[11]. Основное использование идеальных решёток в криптографии связано с тем, что достаточно эффективные и практичные коллизионные хэш-функции могут быть построены на основе твёрдости нахождения приближённого кратчайшего вектора в таких решётках[5]. Группы учёных, изучающие идеальные криптографические решётки, исследовали коллизионные устойчивые хэш-функции, построенные на основе идеальных решёток, а именно Пейкрет К. и Розен С.[12]. Эти результаты проложили путь для других эффективных криптографических конструкций, включая схемы идентификации и подписи.
Лобашевский В. и Миссиансио Д.[7] предложили конструкции эффективных и устойчивых к коллизиям хэш-функций, которые могут быть доказаны на основе наихудшей жёсткости задачи о кратчайшем векторе для идеальных решёток. Тем самым были определены рассматриваемые семейства хэш-функции для элементов:
, где есть выборка случайных элементов из , .
В данном случае размер ключа, то есть хэш-функции определяется как [13], используя алгоритм быстрого преобразования Фурье, для подходящего , операция может быть выполнена за время . Поскольку есть константой, то для хеширования требуется конечное время .
Цифровые подписи
[править | править код]Схемы цифровых подписей относятся к числу наиболее важных криптографических примитивов. Они могут быть получены с помощью односторонних функций, основанных на наихудшей жёсткости решёточных задач, однако являются непрактичными. С момента использования проблемы обучения с ошибками в криптографическом контексте был разработан ряд новых схем цифровой подписи, основанных на обучении с ошибками и кольцевом обучении с ошибками.[14]
Прямое построение цифровых подписей основано на сложности аппроксимации кратчайшего вектора в идеальных решётках.[15] Схема Любашёвского В. и Миссиансио Д.[15], основанная на идеальных решётках, имеет гарантии безопасности даже в худшем случае и является наиболее асимптотически эффективной конструкцией, известной на сегодняшний день, также позволяющей генерировать сигнатуры и проверять алгоритмы, работающие за почти линейное время[16].
Одна из главных открытых проблем, которые были подняты в описанных выше работах, заключается в создании одноразовой подписи с аналогичной эффективностью, но основанной на более слабом допущении твёрдости. Например, было бы здорово обеспечить однократную подпись с защитой, основанную на сложности аппроксимации задачи кротчайшего вектора (SVP) (в идеальных решётках) с точностью до .[17]
Построение таких цифровых подписей основано на стандартном преобразовании одноразовых подписей (то есть подписей, которые позволяют надёжно подписывать одно сообщение) в общие схемы подписи вместе с новой конструкцией одноразовой подписи на основе решётки, безопасность которой, в конечном счёте, основана на наихудшей жёсткости аппроксимации кратчайшего вектора во всех решётках, соответствующий идеалам в кольце для любого неприводимого многочлена [16].
Хэш-функция SWIFT
[править | править код]Хэш-функция достаточно эффективна и может быть вычислена асимптотически за время с использованием быстрого преобразования Фурье по комплексным числам. Однако на практике это несёт значительные накладные расходы. Набор криптографических хеш-функций с доказанной стойкостью SWIFFT, определённый Миссиансио Д. и Регевом[16], по сути, высоко оптимизированный вариант хэш-функции, описанной выше с использованием быстрого преобразования Фурье в . Вектор f определён в для равного степени 2, так что соответствующий полином является неприводимым многочленом. Обнаружение коллизий функций SWIFFT равносильно нахождению коллизиций в базовой функции идеальной решётки. Заявленное свойство коллизий SWIFFT[18] поддерживается при наихудшем случае в задачах на идеальных решётках.
Алгоритм хэш-функции SWIFFT :
- Параметры: Натуральные числа такие, что степень двойки, простое, и .
- Ключ: векторы выбраны независимо и случайным образом в .
- Вход: вектора .
- Выход: вектор , где — компонентное векторное произведение, а — обратимой матрицей над
См. также
[править | править код]Примечания
[править | править код]- ↑ Shah, Agam Quantum computing breakthrough claim from IBM . Дата обращения: 1 июня 2015. Архивировано из оригинала 23 сентября 2015 года.
- ↑ Nicolas Gama, Phong Q. Nguyen Lattice-Based Identification Schemes Secure Under Active Attacks Архивная копия от 28 апреля 2015 на Wayback Machine. Predicting Lattice Reduction, 1995.
- ↑ Daniele Micciancio,Oded Regev Lattice-based Cryptography Архивная копия от 17 февраля 2020 на Wayback Machine, 2008.
- ↑ Vadim Lyubashevsky, Chris Peikert,Oded Regev On Ideal Lattices and Learning with Errors Over Rings Архивная копия от 5 ноября 2020 на Wayback Machine, 2013.
- ↑ 1 2 Vadim Lyubashevsky. Lattice-Based Identification Schemes Secure Under Active Attacks Архивная копия от 8 октября 2011 на Wayback Machine. In Proceedings of the Practice and theory in public key cryptography , 11th international conference on Public key cryptography, 2008.
- ↑ 1 2 Jintai Ding and Richard Lindner. Identifying Ideal Lattices Архивная копия от 28 августа 2021 на Wayback Machine. In Cryptology ePrint Archive, Report 2007/322, 2007.
- ↑ 1 2 Lyubashevsky, V., Micciancio, D. Generalized compact knapsacks are collision resistant. Архивная копия от 8 октября 2011 на Wayback Machine. In CBugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144—155. Springer, Heidelberg (2006).
- ↑ Lenstra A., Lenstra H., Lovasz L. Factoring polynomials with rational coefficients Архивная копия от 24 сентября 2020 на Wayback Machine, 1982.
- ↑ V.Lyubashevsky, Daniele Micciancio Generalized compact knapsacks are collision resistant. In International colloquium on automata, languages and programming, 2008.
- ↑ Complexity of lattice problems: a cryptographic perspective. The Kluwer international series in engineering and computer science (BIB), Архивировано 29 мая 2015, Дата обращения: 7 декабря 2019 Источник . Дата обращения: 7 декабря 2019. Архивировано 29 мая 2015 года.
- ↑ O. Goldreich, S. Goldwasser, S. Halevi. Collision-Free Hashing from Lattice Problems Архивная копия от 29 сентября 2020 на Wayback Machine, 1996.
- ↑ Vadim Lyubashevsky, Chris Peikert and Oded Regev. On Ideal Lattices and Learning with Errors over Rings (недоступная ссылка). In Eurocrypt 2010, Lecture Notes in Computer Science, 2010.
- ↑ Mikl´os Ajtai Representing Hard Lattices with O(n log n) Bits Архивная копия от 7 декабря 2019 на Wayback Machine, 2005.
- ↑ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded. On ideal lattices and learning with errors over rings (англ.) // In Proc. Of EUROCRYPT, Volume 6110 of LNCS : journal. — 2010. — P. 1—23.
- ↑ 1 2 Vadim Lyubashevsky and Daniele Micciancio. Asymptotically efficient lattice-based digital signatures Архивная копия от 28 августа 2021 на Wayback Machine. In Proceedings of the 5th conference on Theory of cryptography, 2008.
- ↑ 1 2 3 Daniele Micciancio, Oded Regev Lattice-based Cryptography Архивная копия от 20 сентября 2020 на Wayback Machine. In POST-QUANTUM CRYPTOGRAPHY, 2009.
- ↑ Vadim Lyubashevsky, Daniele Micciancio. Asymptotically efficient lattice-based digital signatures Архивная копия от 28 августа 2021 на Wayback Machine. In Proceedings of the 5th conference on Theory of cryptography, 2008.
- ↑ Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert,Alon Rosen [https://web.archive.org/web/20190408115349/https://link.springer.com/chapter/10.1007%2F978-3-540-71039-4_4 Архивная копия от 8 апреля 2019 на Wayback Machine: A Modest Proposal for FFT Hashing, 2008.
Литература
[править | править код]- J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, W. Whyte. Topics in Cryptology — CT-RSA 2003. — 2003. — С. 122—140.
- J. Hoffstein, J. Pipher, and J.H. Silverman. NTRU: A ring-based public key cryptosystem. — 1998. — С. 267—288.
- V. Lyubashevsky and D. Micciancio. Generalized Compact Knapsacks Are Collision Resistant. — 2006. — С. 144—155.
- Peikert, C., Rosen, A. Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices. — 2006. — С. 145—166.
- Craig Gentry. Fully homomorphic encryption using ideal lattices. — 2009. — С. 169—178.
- Phong Q. Nguyen, Jacques Stern. Lattice Reduction in Cryptology: An Update // Proceedings of the 4th International Symposium on Algorithmic Number Theory. — Springer-Verlag, 2000. — С. 85–112. — ISBN 3-540-67695-3.
Ссылки
[править | править код]- Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. Inform. Theory. — 2002. — Т. 48, вып. 8.
- Daniele Micciancio. The Shortest Vector Problem is {NP}-hard to approximate to within some constant // SIAM Journal on Computing. — 2001. — Т. 30, вып. 6. — С. 2008—2035.
- Lyubashevsky, V., Micciancio, D. Generalized compact knapsacks are collision resistant. — 2006. — С. 1—27.
- Lyubashevsky, V., Micciancio, D. Asymptotically efficient lattice-based digital signatures. — 2008.
- Lyubashevsky V. Lattice-Based Identification Schemes Secure Under Active Attacks. — 2008. — С. 1—18.
- Vadim Lyubashevsky, Chris Peikert and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. — 2010. — С. 1—27.
- Léo Ducas. Advances on quantum cryptanalysis of ideal lattices. — 2017. — С. 184—189.
- Eva Bayer-Fluckiger. Ideal Lattices. — 2017. — С. 1—17.
- Identifying Ideal Lattices. Jintai Ding and Richard Lindner. — 2007. — С. 1—12.
- Jintai Ding, Xiang Xie, Xiaodong Lin. A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem. — 2012. — С. 1—15.
- C. Peikert. Lattice Cryptography for the Internet. — 2014. — С. 1—25.
- V. Lyubashevsky. Lattice Signatures Without Trapdoors. — 2014. — С. 1—24.
- Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa. Efficient public key encryption based on ideal lattices. — 2009. — С. 1—19.