Публікація: Горизонти досліджень в груповій криптографії в контексті розробки постквантових криптосистем
Завантаження...
Дата
2024
Назва журналу
ISSN журналу
Назва тома
Видавництво
ХНУРЕ
Анотація
Асиметрична криптографія покладається на принцип легкості обчислення та складності обернення односторонніх функцій. Ці функції можна легко виконати, але інвертувати їх обчислювально складно. У цьому контексті NP-повні задачі є ідеальними кандидатами для виконання ролі таких функцій у асиметричній криптографії, оскільки генерувати їх випадки легко, але знаходити рішення – складно. Проте, практичне застосування NP-повних задач має певні обмеження, зокрема через складності зі створенням задач, які були б складними у середньому. Хоча NP-повна задача може бути загалом складною, окремий її випадок може бути вирішений, що робить її непридатною для криптографії. В статті розглядаються класи NP проблем. Дано основні визначення та поняття. Проаналізовано властивості класу NP-повних задач, умови визначення належності до множини NP-повних задач та поточний стан складних для розв’язання проблем. Визначається, що клас NP-повних проблем є складним для квантових обчислень. Проаналізовано критерії належності проблеми слова в групах до NP-повних проблем. Визначено кінцеві неабелеві групи, для яких проблема слова є NP-повною. Розглянуто переваги використання неабелевих груп для криптографічного застосування. Наведено правила зміни форми, що визначають перетворення еквівалентних слів. Проблема слова в кінцевих групах є однією з NP-повних проблем. Проаналізовано останні дослідження та перспективи розробки криптографічних примітивів асиметричної криптографії з використанням складних для розв’язання проблем у кінцевих групах.
Опис
Ключові слова
NP-повні задачі, асиметрична криптосистема, логарифмічний підпис
Бібліографічний опис
Горизонти досліджень в груповій криптографії в контексті розробки постквантових криптосистем / Є. В. Котух, Г. З. Халімов, М. В. Коробчинський, М. М. Руденко, В. О. Любчак, С. М. Мацюк, М. В. Чащин // Радіотехніка : Всеукр. міжвід. наук.-техн. зб. – Харьків, 2024. – Вип. 216. – С. 62–72. - DOI: 10.30837/rt.2024.1.216.05.