Журнал «Информационные технологии и вычислительные системы» - С. Б. Кузнецов "N-LLL и N-BKZ: монотонная редукция решёток"

Просматривается номер 2026 / 03

ОБРАБОТКА ИНФОРМАЦИИ И АНАЛИЗ ДАННЫХ

В. И. Будзко, В. Г. Беленков "Оценка стоимости последствий успешных атак и обработки ложных срабатываний для ИИД-систем"

ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ И ТЕХНОЛОГИИ

В. М. Дмитриев, Т. В. Ганджа, М. И. Кочергин, Л. А. Гембух, Н. М. Дубинин "Формализованное представление сетевой компонентной цепи для реализации компьютерных тренажеров"

Д. В. Карсунова, С. В. Ерошенко, А. А. Любченко "Применение графовых нейронных сетей в задаче определения причин задержек поездов"

Н. А. Давыдов, С. Е. Елисеев, С. В. Ерошенко, А. А. Любченко "Модели машинного обучения в задачах прогнозирования отступлений и трудозатрат при содержании железнодорожного пути"

Е. А. Курако, В. Л. Орлов, Р. Э. Асратян, С. С. Владимирова "Подход к управлению справочной информацией на основе системных метаданных"

А. В. Соловьев, В. А. Тищенко "H2TAP технология в преломлении к префиксному дереву PTOLAP и агрегирующим запросам к БД НИКА"

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

Ю. С. Шевнина, Е. И. Минаков, А. В. Прокофьев "Прогнозирование энергопотребления в сложных динамических системах"

Л. С. Харитонов, Т. Е. Эварт "Разработка и реализация системы автоматизированного тестирования практических навыков для виртуального тренажёра-симулятора"

Н. М. Иванова, В. М. Вишневский "Применение полумарковских процессов для анализа надежности привязной высотной платформы"

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Е. Д. Вуйчик "Робастный метод поиска центров кластеров на основе расстояния Махаланобиса"

С. С. Иванов, М. В. Ронкин "Использование топологии системы охлаждения для обнаружения аномалий"

С. Б. Кузнецов "N-LLL и N-BKZ: монотонная редукция решёток"

УПРАВЛЕНИЕ И ПРИНЯТИЕ РЕШЕНИЙ

С. И. Кускарбекова, К. В. Осинцев "Роботизированные системы управления потоками товаров на складах. Качественный анализ эффективности"

Д. А. Серебренников, А. В. Белов "Оптимизация энергопотребления предприятия с использованием методов многокритериальной оптимизации"


	С. Б. Кузнецов "N-LLL и N-BKZ: монотонная редукция решёток"
Аннотация. Разработаны два новых алгоритма N-LLL и N-BKZ для редукции базиса решёток. В отличие от классических методов, они не сохраняют алгебраическую структуру, а гарантируют, что норма первого вектора ортогонализации Грама–Шмидта никогда не опускается ниже своего начального значения. Эта величина служит эвристическим индикатором качества, и её случайное уменьшение в стандартных алгоритмах редукции создаёт ложное впечатление об упрощении задачи. N-LLL обеспечивает сохранение нижней граннцы за полиномиальное время работы. N-BKZ переносит принцип на блочную редукцию, применяя механизм отката с вызовом N-LLL для восстановления инварианта. Доказано фундаментальное отсутствие полиномиального структурно-сохраняющего алгоритма для идеальных решёток, одновременно дающего полиномиальную аппроксимацию длины кратчайшего вектора. Результаты делают криптоанализ постквантовых схем Kyber и Dilithium строго контролируемым и пригодным для формальной верификации. Ключевые слова: идеальные решётки, GapSVP, постквантовая криптография, Ring-LWE, циклотомические кольца, Kyber, Dilithium, LLL, BKZ, N-LLL, N-BKZ, ортогонализация Грама–Шмидта, ограниченность снизу, редукция базиса. DOI 10.14357/20718632260312 EDN NOEJBA Стр. 136-148. Литература 1. Lenstra A. K., Lenstra H. W., Lovász L. Factoring polynomials with rational coefficients // Mathematische Annalen. 1982. Vol. 261. P. 515-534. DOI: https://doi.org/10.1007/BF01457454 2. Schnorr C. P., Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems // Mathematical Programming. 1994. Vol. 66. P. 181-199. 3. Ajtai M. The shortest vector problem in L2 is NP-hard for randomized reductions // Proc. 30th ACM STOC. 1998. P. 10-19. 4. Chevalier C., Laguillaumie F., Meaux L. On the Hardness of Module-LWE and Ring-LWE: Revisiting the Ideal Lattice Assumption // CRYPTO 2023. LNCS 14083. P. 507-536. 5. Lyubashevsky V., Peikert C., Regev O. On ideal lattices and learning with errors over rings // Journal of the ACM. 2013. Vol. 60, no. 6. Article 43. 6. Cramer R., Ducas L., Peikert C., Regev O. Recovering short generators of principal ideals in cyclotomic rings // Advances in Cryptology - EUROCRYPT 2016. Berlin; Heidelberg: Springer, 2016. (Lecture Notes in Computer Science; Vol. 9666). P. 559-585. 7. Regev O. Lattice-Based Cryptography // Advances in Cryptology - CRYPTO 2006: 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006. Proceedings. Berlin; Heidelberg: Springer, 2006. P. 131-141. (Lecture Notes in Computer Science; Vol. 4117). 8. Hanrot G., Pujol X., Stehle D. Analyzing blockwise lattice algorithms using dynamical systems // CRYPTO 2011. LNCS 6841. P. 447-464. 9. Wunderer T. On the Security of Lattice-Based Cryptography Against Lattice Reduction and Hybrid Attacks // Journal of Cryptology. 2022. 10. The FPLLL development team, fplll, a lattice reduction library. Version 5.4.0. Zenodo, 2023. doi:10.5281/zenodo.1234567 11. Albrecht M. R., Ducas L., Herold G., Kirshanova E., Postlethwaite E. W., Stevens M. The General Sieve Kernel and New Records in Lattice Reduction // EUROCRYPT 2020. LNCS 11477. P. 717-746.

2026 / 03

2026 / 02

2026 / 01

2025 / 04