Горизонти досліджень в груповій криптографії в контексті розробки постквантових криптосистем

Abstract

Асиметрична криптографія покладається на принцип легкості обчислення та складності обернення односторонніх функцій. Ці функції можна легко виконати, але інвертувати їх обчислювально складно. У цьому контексті NP-повні задачі є ідеальними кандидатами для виконання ролі таких функцій у асиметричній криптографії, оскільки генерувати їх випадки легко, але знаходити рішення – складно. Проте, практичне застосування NP-повних задач має певні обмеження, зокрема через складності зі створенням задач, які були б складними у середньому. Хоча NP-повна задача може бути загалом складною, окремий її випадок може бути вирішений, що робить її непридатною для криптографії. В статті розглядаються класи NP проблем. Дано основні визначення та поняття. Проаналізовано властивості класу NP-повних задач, умови визначення належності до множини NP-повних задач та поточний стан складних для розв’язання проблем. Визначається, що клас NP-повних проблем є складним для квантових обчислень. Проаналізовано критерії належності проблеми слова в групах до NP-повних проблем. Визначено кінцеві неабелеві групи, для яких проблема слова є NP-повною. Розглянуто переваги використання неабелевих груп для криптографічного застосування. Наведено правила зміни форми, що визначають перетворення еквівалентних слів. Проблема слова в кінцевих групах є однією з NP-повних проблем. Проаналізовано останні дослідження та перспективи розробки криптографічних примітивів асиметричної криптографії з використанням складних для розв’язання проблем у кінцевих групах.