Котух, Є. В.Халімов, Г. З.Коробчинський, М. В.Руденко, М. М.Любчак, В. О.Мацюк, С. М.Чащин, М. В.2025-06-122025-06-122024Горизонти досліджень в груповій криптографії в контексті розробки постквантових криптосистем / Є. В. Котух, Г. З. Халімов, М. В. Коробчинський, М. М. Руденко, В. О. Любчак, С. М. Мацюк, М. В. Чащин // Радіотехніка : Всеукр. міжвід. наук.-техн. зб. – Харьків, 2024. – Вип. 216. – С. 62–72. - DOI: 10.30837/rt.2024.1.216.05.https://openarchive.nure.ua/handle/document/31495Асиметрична криптографія покладається на принцип легкості обчислення та складності обернення односторонніх функцій. Ці функції можна легко виконати, але інвертувати їх обчислювально складно. У цьому контексті NP-повні задачі є ідеальними кандидатами для виконання ролі таких функцій у асиметричній криптографії, оскільки генерувати їх випадки легко, але знаходити рішення – складно. Проте, практичне застосування NP-повних задач має певні обмеження, зокрема через складності зі створенням задач, які були б складними у середньому. Хоча NP-повна задача може бути загалом складною, окремий її випадок може бути вирішений, що робить її непридатною для криптографії. В статті розглядаються класи NP проблем. Дано основні визначення та поняття. Проаналізовано властивості класу NP-повних задач, умови визначення належності до множини NP-повних задач та поточний стан складних для розв’язання проблем. Визначається, що клас NP-повних проблем є складним для квантових обчислень. Проаналізовано критерії належності проблеми слова в групах до NP-повних проблем. Визначено кінцеві неабелеві групи, для яких проблема слова є NP-повною. Розглянуто переваги використання неабелевих груп для криптографічного застосування. Наведено правила зміни форми, що визначають перетворення еквівалентних слів. Проблема слова в кінцевих групах є однією з NP-повних проблем. Проаналізовано останні дослідження та перспективи розробки криптографічних примітивів асиметричної криптографії з використанням складних для розв’язання проблем у кінцевих групах.ukNP-повні задачіасиметрична криптосистемалогарифмічний підписArticlehttps://doi.org/10.30837/rt.2024.1.216.05