Алгоритмы свертывания решеток: теория и практика

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:47, 27 сентября 2015.
Lattice Reduction Algorithms: Theory and Practice
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Phong Q. Nguyen[@: 1]
Опубликован 2011 г.
Сайт Phong Q. Nguyen's webpage
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


Аннотация. Алгоритмы свертывания решеток находят множество применений в математике и информационных технологиях, а особенно в криптологии. С одной стороны, эти алгоритмы широко используются в криптоанализе систем с открытым ключом, например, для реализации атаки на специальные параметры RSA и DSA/ECDSA. С другой стороны, становится все больше криптосхем, надежность которых требует сложности в сворачивании решеток. В нашем разговоре мы изучаем алгоритмы сворачивания решеток, представляем их возможности и обсуждаем различия между теорией и практикой.

Интуитивно, решетка – это бесконечный массив точек в , расположенные в определенном порядке так, что можно перемещать любую точку в любую другую точку с некой симметрией расположения. Простейшая нетривиальная решетка – решетка гиперкуба , составленная из всех точек с интегральными координатами. Ветвь числовой теории, которая занимается решетками (и особенно их связью с выпуклыми множествами) известна как геометрия чисел [1][2][3][4], и её происхождение идет из двух исторических проблем: высокоразмерные обобщения алгоритма Евклида нахождения НОД и упаковка сфер. Более формально, решетка – это дискретная подгруппа , или, равносильно, всех целых комбинаций линейно независимых векторов в



Такой набор называется базисом решетки. Целью сворачивания решетки является нахождение сокращенных базисов, то есть базисов, состоящих из достаточно коротких и ортогональных векторов. Это связано с теорией сокращения квадратичных форм, разработанной Лагранжем[5], Гауссом[6] и Гермитом[7]. Алгоритмы сворачивания решеток бесценны во многих областях информационных технологий и математики(см. книгу [8]), особенно в криптоанализе с открытым ключом, где помимо прочего их использовали для взлома криптосистем-рюкзаков[9] и особых случаев RSA и DSA[10][11]. Сокращенный базис позволяет решить следующие важные проблемы, точно или приблизительно:

  • самая основная вычислительная проблема, связанная с решетками - проблема кратчайшего вектора (ПКВ), которая требует нахождения ненулевого вектора решетки наименьшей нормы с использованием базиса на входе. ПКВ можно рассматривать как геометрическое обобщение нахождения НОД: алгоритм Евклида на самом деле находит наименьшую(по модулю) ненулевую линейную комбинацию двух целых чисел, поскольку НОД, что означает что мы заменяем целые числа и произвольным числом векторов с целочисленными координатами. Поскольку ПКВ является NP-трудной при условии рандомизированных сокращений[3](см. [12][13] для исследований трудности проблем решеток), мы также заинтересованы в аппроксимации ПКВ, то есть в получении на выходе ненулевого вектора решетки не намного большего, чем наименьшая норма.
  • неоднородная версия ПКВ называется проблемой ближайшего вектора(ПБВ); здесь мы имеем произвольный начальный вектор в дополнение к базису решетки и требуется найти ближайшую к этому вектору точку решетки. Популярный частный случай ПБВ - связанное дистанционное расшифрование(СДД), когда известно, что начальный вектор близок к решетке.

Первым ПКВ-алгоритмом был алгоритм свертки Лагранжа[5], который решал ПКВ точно в 2 размерностях за квадратичное время. В произвольных размерностях есть 2 типа ПКВ-алгоритмов:

  1. Точные алгоритмы. Эти алгоритмы доказательно находят кратчайший вектор, но они затратны, время выполнения как минимум экспоненциально размерности. Интуитивно, эти алгоритмы - исчерпывающий поиск всех сверхкоротких векторов, число которых в худшем случае экспоненциально размерности: фактически, есть решетки, для которых число кратчайших векторов уже экспоненциально. Точне алгоритмы можно разделить на 2 категории:
    1. Точные алгоритмы с полиномиальным ограничением простарнства. Они основаны на перечислении, датированном ранними 80ми в работах Поста[14], Каннана[15] и Финке-поста[16]. В своей простейшей форме перечисление - это просто исчерпывающий поиск наилучшей елой комбинации базисных векторов. лучший детерминистский алгоритм перечисления - алгоритм Каннана[15], с суперполиномиальной наихудшей сложностью, а именно полиномиальных операций (см. [17]), где есть размерность решетки. Алгоритмы перечисления, используюемые на практике (например, Шнор-Эйкнер[18]), обладают худшей предварительной обработкой, чем алгоритм Канна[15], и их сложность наихудшая сложность полиномиальных операций. Однако возможно получить существенные ускорения с использованием техник упрощения: упрощение было введено Шнор-Эйкнером[18] и Шнор-Хорнером[19] в 90х и недавно снова появились у Гама, Нгуен и Регева[20], где было показано, что можно достичь эвристического ускорения в по сравнению с базовым перечислением.
    2. Точные алгоритмы с экспоненциальным ограничением пространства. Эти алгоритмы обладают лучшим асимптотическим временем выполнения, но все они требуют экспоненциального пространства . Первый алгоритм такого типа - алгоритм рандомизированного решета Аджтаи, Кумара и Сивакумара (АКС)[4], с экспоненциальной наихудшей сложностью полиномиальных операций. Миккианчио и Вулгарис[21] недавно представили альтернативный детирминистичный алгоритм, который решает ПКВ и ПБВ в пределах полиномиальных операций. Интересно, что есть несколько эвристических вариантов [22][23][24] АКС с временем работы , где константа намного меньше, чем у всех известных доказательных алгоритмов. Например, недавни алгоритм Ванга[24] имеет временную сложность полиномиальных операций.
  2. Аппроксимационные алгоритмы. Эти алгоритмы намного быстрее точных, но их результатами являются просто короткие векторы решеток, не обязательно кратчайшие: обычно они дают на выходе весь сокращенный базис и поэтому являются алгоритмами свертывания решеток. Первый алгоритм такого типа - прославленный алгоритм Ленстры, Ленстры и Ловраза (ЛЛЛ)[20,30], который может аппроксимировать ПКВ в пределах множителя за полиномиальное время: его можно рассматривать как алгоритмическую версию неравенства Эрмита. С момента появления ЛЛЛ, исследования в этой области сфокусировались на двух темах:
    1. Ускоренный ЛЛЛ. Здесь мы заинтересованы в получении сокращенного базиса схожего с ЛЛЛ качества, возможно немного хуже, но за меньшее время. Это достигается стратегией "разделяй-и-властвуй" (как в [25][26]) или использованием арифметики с плавающей точкой (как в [27][28][29]). Наиболее известным применением ЛЛЛ являются типично эфристические варианты с плавающей точкой, такие как Шнор-Эйкнер[37]: см. исследование [30] ЛЛЛ с плавающей точкой.
    2. Усиленный ЛЛЛ. Здесь мы заинтересованы в получении лучших аппроксимаций чем в ЛЛЛ, за счет увеличения времени работы. Интуитивно, ЛЛЛ повторяет двухразмерное сокращение для нахождения кратчайших векторов в размерности . Алгоритмы блочного сокращения [31][32][33] получают лучшую аппроксимацию с помощью замены этих двухразмерных подзадач более высокоразмерными, с использованием точных алгоритмов ПКВ в низких размерностях. Лучший известный блочный полиномиальный алгоритм [33] достигает субэкспоненциальной аппроксимации порядка : это алгоритмическая версия неравенства Мордела. На практике популярен выбор БКЗ-алгоритма Шнора-Эйкнера [18] применительно к НТЛ-библиотеке[34], являющейся эвристической версией блочного алгоритма Шнора[31]. В статье [35] приводится экспериментальная оценка БКЗ.

Обе категории на самом деле дополняют друг друга: все известные точные алгоритмы сначала применяют аппроксимационные алгоритмы (обычно ЛЛЛ) в качестве предобработки, в то время как все блочные алгоритмы много раз вызывают точные алгоритмы в малых размерностях в качестве подзадач. Большинство ПКВ алгоритмов, о которых мы упомянули, могут быть адаптированы к ПБВ[36]. Доказательные ПКВ-алгоритмы исследуются в работе [37]. Рассмотренные эвристические алгоритмы таковы, что их время работы недоказуемо и результат не гарантирован. Эвристические алгоритмы на практике могут обгонять доказуемые по неизвестным пока причинам. Наконец, это все сказки что алгоритмы свертывания решеток дают лучие результаты, чем доказанные худшие теоретические границы. В 80х первые успехи таких алгоритмов в криптоанализе привели к вере, что сильные алгоритмы свертывания решеток ведут себя как идеальные оракулы, по крайней мере в малых размерностях. Но эта вера показала свои границы в 90е в NP-сложности и разработке криптографии на основе решеток и последовавшей за ними наихудшим/усредненным сокращением Аджтаих[38] и NTRU-криптосистем [39]. Статьи [40][35] проясняют, что можно ожидать на практике на основании результатов экспериментов. Такие оценки важны для лучшего понимания разрыва между теорией и практикой, но также и для оценки конкретной безопасности криптографии на основе решеток.

Контакты авторов материала

  1. INRIA and ENS, Dґepartement d’informatique, 45 rue d’Ulm, 75005 Paris, France, Phong Q. Nguyen's webpage

Примечание

Литература

  1. Minkowski, H.: Geometrie der Zahlen. Teubner-Verlag, Leipzig (1896)
  2. Siegel, C.L.: Lectures on the Geometry of Numbers. Springer, Heidelberg (1989)
  3. Gruber, M., Lekkerkerker, C.G.: Geometry of Numbers. North-Holland, Amsterdam (1987)
  4. Cassels, J.: An Introduction to the Geometry of Numbers (1997)
  5. 5,0 5,1 Lagrange, L.: Recherches d’arithm ́etique. Nouv. M ́em. Acad. (1773)
  6. Gauss, C.: Disquisitiones Arithmeticæ, Leipzig (1801)
  7. Hermite, C.: Extraits de lettres de M. Hermite `a M. Jacobi sur diff ́erents objets de la th ́eorie des nombres. J. Reine Angew. Math. 40, 261–315 (1850)
  8. Nguyen, P.Q., Vall ́ee, B. (eds.): The LLL Algorithm: Survey and Applications. Information Security and Cryptography. Springer, Heidelberg (2010)
  9. Odlyzko, A.M.: The rise and fall of knapsack cryptosystems. In: Cryptology and Computational Number Theory. Proc. of Symposia in Applied Mathematics, vol. 42, pp. 75–88. AMS, Providence (1990)
  10. Nguyen, P.Q.: Public-key cryptanalysis. In: Luengo, I. (ed.) Recent Trends in Cryptography. Contemporary Mathematics, vol. 477. AMS–RSME (2009)
  11. May, A.: Using LLL-reduction for solving RSA and factorization problems: A sur- vey. In: [30] (2010)
  12. Khot, S.: Inapproximability results for computational problems on lattices. In: [30] (2010)
  13. Regev, O.: On the Complexity of Lattice Problems with Polynomial Approximation Factors. In: [30] (2010)
  14. Pohst, M.: On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. SIGSAM Bull. 15(1), 37–44 (1981)
  15. 15,0 15,1 15,2 Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proc. 15th ACM Symp. on Theory of Computing (STOC), pp. 193–206 (1983)
  16. Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of Computation 44(170), 463–471 (1985)
  17. Hanrot, G., Stehl ́e, D.: Improved analysis of Kannan’s shortest lattice vector algorithm (extended abstract). In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 170–186. Springer, Heidelberg (2007)
  18. 18,0 18,1 18,2 Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Programming 66, 181–199 (1994)
  19. Schnorr, C.-P., H ̈orner, H.H.: Attacking the chor-rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995)
  20. Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257–278. Springer, Heidelberg (2010)
  21. Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In: Proc. STOC 2010, pp. 351–358. ACM, New York (2010)
  22. Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. J. of Mathematical Cryptology 2(2), 181–207 (2008)
  23. Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1468–1480 (2010)
  24. 24,0 24,1 Wang, X., Liu, M., Tian, C., Bi, J.: Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. Cryptology ePrint Archive, Report 2010/647 (2010), http://eprint.iacr.org/
  25. Scho ̈nhage, A.: Factorization of univariate integer polynomials by diophantine aproximation and an improved basis reduction algorithm. In: Paredaens, J. (ed.) ICALP 1984. LNCS, vol. 172, pp. 436–447. Springer, Heidelberg (1984)
  26. Koy, H., Schnorr, C.-P.: Segment LLL-reduction of lattice bases. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 67–80. Springer, Heidelberg (2001)
  27. Schnorr, C.-P.: A more efficient algorithm for lattice basis reduction. J. Algorithms 9(1), 47–62 (1988)
  28. Nguyen, P.Q., Stehl ́e, D.: An LLL algorithm with quadratic complexity. SIAM J. Comput. 39(3), 874–903 (2009)
  29. Morel, I., Stehl ́e, D., Villard, G.: H-LLL: using householder inside LLL. In: Proc. ISSAC 2009, pp. 271–278. ACM, New York (2009)
  30. Stehl ́e, D.: Floating-point LLL: theoretical and practical aspects. In: [30] (2010)
  31. 31,0 31,1 Schnorr, C.-P.: A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science 53(2-3), 201–224 (1987)
  32. Gama, N., Howgrave-Graham, N., Koy, H., Nguyˆen, P.Q.: Rankin’s constant and blockwise lattice reduction. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 112–130. Springer, Heidelberg (2006)
  33. 33,0 33,1 Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Proc. 40th ACM Symp. on Theory of Computing (STOC) (2008)
  34. Shoup, V.: Number Theory C++ Library (NTL) version 5.4.1, http://www.shoup.net/ntl/
  35. 35,0 35,1 Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008)
  36. Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Trans. on Info. Theory 48(8), 2201–2214 (2002)
  37. Nguyen, P.Q.: Hermite’s constant and lattice algorithms. In: [30] (2010)
  38. Ajtai, M.: Generating hard instances of lattice problems. In: Proc. STOC 1996, pp. 99–108. ACM, New York (1996)
  39. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryp- tosystem. In: Buhler, J.P. (ed.) ANTS III 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
  40. Nguyˆen, P.Q., Stehl ́e, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS VII 2006. LNCS, vol. 4076, pp. 238–256. Springer, Heidelberg (2006)