Research horizons in group cryptography in the context of post-quantum cryptosystems development - Kotukh, Y.; Khalimov, G.; Korobchynskyi, M.; Rudenko, M.; Liubchak, V.; Matsyuk, S.; Chashchyn, M. (Radiotekhnika, 2024)
Asymmetric cryptography relies on the principle of ease of calculation and complexity of one-sided functions’ inversion. These functions can be easily implemented, but inverting them is computationally difficult. In this context, NP-complete problems are ideal candidates for the role of such functions in asymmetric cryptography, since generating their cases is easy, but finding solutions is difficult. However, the practical application of NP-complete problems has certain limitations, in particular due to difficulties in creating problems that would be complex on average. Although an NP-complete problem may be hard in general, a particular case of it may be solvable, making it unsuitable for cryptography. The article considers classes of NP problems. Basic definitions and concepts are given. The properties of the class of NP-complete problems, the conditions for determining belonging to the set of NP-complete problems, and the current state of difficult to solve problems are analyzed. It turns out that the class of NP-complete problems is hard for quantum computing. The criteria for belonging of the word problem in groups to NP-complete problems are analyzed. Finite non-Abelian groups are defined for which the word problem is NP-complete. The advantages of using non-Abelian groups for cryptographic applications are considered. The rules of change of form, which determine the transformation of equivalent words, are given. The word problem in finite groups is one of the NP-complete problems. The latest research and prospects for the development of cryptographic primitives of asymmetric cryptography using difficult-to-solve problems in finite groups are analyzed.