Задача о кратчайшем векторе: различия между версиями

В последнее время редукция базиса решетки широко использовалась для решения многих задач криптоанализа и теории кодирования, включая взлом нескольких вариантов криптосистемы RSA и алгоритма цифровой подписи DSA, поиск малых решений модулярных уравнений и расшифровку списков кодов китайской теоремы об остатках (Chinese Reminder Theorem, CRT). Обзор недавних вариантов применения, в основном в области криптоанализа, можно найти в работах [7, 13].

Последний класс приложений задач с решетками – это разработка криптографических функций (например, устойчивых к столкновениям хэш-функций, схем шифрования с открытым ключом и т.д.), основанное на очевидной неразрешимости задачи решения <math>SVP_\gamma</math> в пределах малых коэффициентов аппроксимации. В [12, глава 8] и [13] можно найти обзор таких приложений и указатели на соответствующую литературу. Отличительной особенностью многих таких криптографических функций, основанных на решетках, является доказанная сложность их взлома ''в среднем'', основываясь на предположении о неразрешимости ''в наихудшем случае'' лежащей в их основе задачи на решетки.