Побудова методiв криптоаналiзу постквантових примiтивiв з використанням обмеженої деревної ширини

Скорочена інформація про документ
dc.contributor.advisorФесенко, Андрiй В’ячеславович
dc.contributor.authorКiстаєв, Матвiй Андрiйович
dc.date.accessioned2026-06-04T13:24:39Z
dc.date.available2026-06-04T13:24:39Z
dc.date.issued2026
dc.description.abstractСт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.
dc.description.abstractotherThe security of three out of four post-quantum cryptographic primitives standardized as a result of the NIST competition is based on the hardness of lattice problems. For the CRYSTALS-Kyber key encapsulation and Dilithium signature schemes, these are the SIS and LWE problems; for the FALCON signature scheme, they are the SVP and BDD problems. These problems are NP-hard in the general case; however, efficiently solvable special cases exist. Investigating them is crucial for cryptanalysis, as it allows for bounding the set of secure keys or valid parameters of cryptosystems. Parameterized complexity theory is very useful for isolating problem properties that affect its hardness, enabling the description of efficiently solvable special cases. One widely studied parameter is the treewidth of a graph – a measure of how close a graph is to being a tree. The aim of this work is to construct parameterizations of the SVP, BDD, SIS, and LWE problems based on the concept of graph treewidth, under which they belong to the FPT complexity class, and to develop cryptanalysis methods for post-quantum lattice-based cryptosystems using the obtained results. The object of the study is information processes in cryptographic protection systems. The subject of the study is the parameters of lattice problems and their impact on the hardness of such problems. As a result, reductions of the selected lattice problems to the BIQP integer programming problem have been constructed. Based on this, parameterizations of the SVP, BDD, LWE, and SIS problems are proposed, for which they belong to the FPT class. Furthermore, concrete approaches of cryptanalysis of schemes whose security is based on the hardness of the SVP and BDD problems have been proposed.
dc.format.extent67 с.
dc.identifier.citationКiстаєв, М. А. Побудова методiв криптоаналiзу постквантових примiтивiв з використанням обмеженої деревної ширини : магістерська дис. : 113 Прикладна математика / Кiстаєв Матвiй Андрiйович. - Київ, 2026. - 67 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/81481
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectпостквантовий криптоаналiз
dc.subjectзадачi на решiтках
dc.subjectsvp
dc.subjectbdd
dc.subjectlwe
dc.subjectsis
dc.subjectзведення до iqp
dc.subjectдеревна ширина
dc.subjectfpt
dc.subjectpost-quantum cryptanalysis
dc.subjectlattice problems
dc.subjectreduction to iqp
dc.subjecttreewidth
dc.subject.udc510.52
dc.titleПобудова методiв криптоаналiзу постквантових примiтивiв з використанням обмеженої деревної ширини
dc.title.alternativeCryptanalysis of Post-Quantum Primitives Using Bounded Treewidth
dc.typeMaster Thesis

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Kistaiev_magistr.pdf
Розмір:
698.96 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (ММЗІ)
Магістерські роботи