Методы построения унимодулярной матрицы U в постквантовой схеме цифровой подписи «Облепиха»: сравнительный анализ и требования к стойкости

С. 118–122.

Буутай П. Н., Кунинец А. А., Леевик А. Г., Малыгина Е. С., Мельничук Е. М.

Рассматривается задача генерации секретного ключа --- унимодулярной матрицы $U \in GL_n(\mathbb{Z})$ --- в постквантовой схеме цифровой подписи «Облепиха». Проведён сравнительный анализ подходов к формированию $U$: блочно-диагональная структура, тензорное произведение, приведение к нормальной форме Эрмита (HNF-метод), метод случайного блуждания в группе $GL_n(\mathbb{Z})$ и алгоритмы, описанные в работах Блэнкса и Миллера. Показано, что структурная уязвимость $U$ (несвязность графа зависимости или иерархическая разреженность) позволяет восстановить изоморфизм с помощью спектральной кластеризации и алгоритмов редукции решёток. Проанализированы ограничения метода случайного блуждания, связанные с отсутствием строгого доказательства стойкости. Обоснован выбор HNF-метода как оптимального компромисса между теоретической стойкостью, вычислительной сложностью и практической реализуемостью. Результаты анализа положены в основу рекомендаций построения матрицы $U$ в алгоритме выработки ключей схемы «Облепиха».

Ключевые слова: постквантовая криптография, задача об изоморфизме решеток, унимодулярная матрица, цифровая подпись

В книге

XXV Международная конференция «Сибирская научная школа-семинар "Компьютерная безопасность и криптография" — SIBECRYPT'26» имени Г. П. Агибалова

Вып. 19. , Томск: Издательский дом ТГУ, 2026.