Побудова методiв криптоаналiзу постквантових примiтивiв з використанням обмеженої деревної ширини
Вантажиться...
Дата
2026
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Стiйкiсть трьох iз чотирьох стандартизованих в результатi конкурсу NIST постквантових криптопримiтивiв ґрунтується на складностi задач на решiтках. Для пiдпису та iнкапсуляцiї ключа CRYSTALS Kyber та Dilithium – це задачi SIS та LWE, для пiдпису FALCON – задачi SVP та BDD. Цi задачi є NP-складними в загальному випадку, однак для них iснують ефективно розв’язнi частковi випадки. Їх дослiдження важливе для криптоаналiзу, оскiльки дозволяє обмежувати множину стiйких ключiв або допустимих параметрiв криптосистем. Параметризована теорiя складностi застосовується для виокремлення властивостей задачi, якi впливають на її складнiсть, що дозволяє описати ефективно розв’язнi частковi випадки. Одним з широко дослiджених параметрiв є деревна ширина графа – мiра близькостi графа до того, щоб бути деревом. Метою роботи є побудова параметризацiй задач SVP, BDD, SIS та LWE на основi поняття деревної ширини графа, для яких вони належать класу складностi FPT, та розробка методiв криптоаналiзу постквантових криптосистем на решiтках на основi отриманих результатiв. Об’єктом дослiдження є iнформацiйнi процеси в системах криптографiчного захисту. Предметом дослiдження є параметри задач на решiтках та їх вплив на складнiсть таких задач. У результатi побудовано зведення обраних задач на решiтках до задачi цiлочисельного програмування BIQP. На основi цього запропоновано параметризацiї задач SVP, BDD, LWE та SIS, для яких вони належать класу FPT. Запропоновано конкретнi пiдходи до криптоаналiзу алгоритмiв, стiйкiсть яких ґрунтується на складностi задач SVP та BDD.
Опис
Ключові слова
постквантовий криптоаналiз, задачi на решiтках, svp, bdd, lwe, sis, зведення до iqp, деревна ширина, fpt, post-quantum cryptanalysis, lattice problems, reduction to iqp, treewidth
Бібліографічний опис
Кiстаєв, М. А. Побудова методiв криптоаналiзу постквантових примiтивiв з використанням обмеженої деревної ширини : магістерська дис. : 113 Прикладна математика / Кiстаєв Матвiй Андрiйович. - Київ, 2026. - 67 с.