Research horizons in group cryptography in the context of post-quantum cryptosystems development
DOI:
https://doi.org/10.30837/rt.2024.1.216.05Keywords:
word problem, NP-complete problems, asymmetric cryptosystem, logarithmic signatureAbstract
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.
References
Liu, Yanyi, and Rafael Pass. On one-way functions from NP-complete problems // Cryptology ePrint Ar-chive (2021).
Luckow, Andre, Johannes Klepsch, and Josef Pichlmeier. Quantum computing: Towards industry reference problems // Digitale Welt 5 (2021): 38–45.
Gilles Brassard. Relativized cryptography // Proceedings of the 20th Annual Symposium on Foundations of Computer Science. 1979. pp. 383–391.
Baldo A., Boffa M., Cascioli L., Fadda E., Lanza C., & Ravera A. The polynomial robust knapsack problem // European Journal of Operational Research. 2023. 305(3). 1424–1434.
Kotukh Y., Khalimov G. Towards practical cryptoanalysis of systems based on word problems and logarithmic signatures // Proceedings of II International Conference Information security: problems and prospects, 25 Nov 2022, Baku, Azerbaijan, pp. 5558.
Khalimov G., Kotukh Y. et al. Towards advance encryption based on a Generalized Suzuki 2-groups // 2021 International Conference on Electrical, Computer, Communications and Mechatronics Engineering (ICECCME). Mauritius. 2021. pp. 1–6. doi: 10.1109/ICECCME52200.2021.9590932.
Khalimov G., Kotukh Y., Khalimova S. MST3 Cryptosystem Based on a Generalized Suzuki 2-Groups [Electronic resource]. Access mode : http://ceur-ws.org/Vol-2711/paper1.pdf
Khalimov G., Kotukh Y., Didmanidze I., Sievierinov O., Khalimova S. and Vlasov A. Towards three-parameter group encryption scheme for MST3 cryptosystem improvement // 2021 Fifth World Conference on Smart Trends in Systems Security and Sustainability (WorldS4), London, United Kingdom, 2021, pp. 204–211. doi: 10.1109/WorldS451998.2021.9514009.
Khalimov G., Kotukh Y., Didmanidze I., Khalimova S. 2021. Encryption scheme based on small Ree groups // Proceedings of the 2021 7th International Conference on Computer Technology Appli-cations (ICCTA '21). ACM, New York, NY, USA, 33–37. https://doi.org/10.1145/3477911.3477917
Khalimov G., Kotukh Y., Shonia O., Didmanidze I., Sievierinov O., Khalimova S. Encryption Scheme Based on the Automorphism Group of the Suzuki Function Field // 2020 IEEE PIC S&T, Kharkiv, Ukraine, 2020, pp. 383–387. doi: 10.1109/PICST51311.2020.9468089.
Suo J., Wang L., Yang S., Zheng W., & Zhang J. Quantum algorithms for typical hard problems: a perspective of cryptanalysis // Quantum Information Processing. 2020. 19. P. 1–26.
Vega F. (2023). On Feasibly Solving NP-complete Problems.
Causey C. J. (2023). NP-Complete Problems and Public Key Cryptography.
Todd J.A., Coxeter H.S.M. A practical method for enumerating cosets of a finite abstract group // Proc. Edinb. Math. Soc., II. Ser. 5, 26-34 (1936). Zbl 0015.10103, JFM 62.1094.02
Ball W. W. R., & Coxeter H. S. (2022). Knuth-Bendix Completion Algorithm.
Novikov P. S. Algorithmic Unsolvability of the Word Problem in Group Theory.. L. Britton, 1958 // Journal of Symbolic Logic 23 (1):50–52.
William W. Boone, Frank B. Cannonito, Roger C. Lyndon, Word Problems, Decision Problems and Burnside Problem in Group Theory. C. R. J. Clapham, 1976 // Journal of Symbolic Logic 41 (4):785–788.
Nyberg Brodda, Carl-Fredrik. The word problem and combinatorial methods for groups and semigroups. Diss. University of East Anglia, 2021.
Rybalov A. (2020, May). A generic algorithm for the word problem in semigroups and groups // Journal of Physics: Conference Series (Vol. 1546, No. 1, p. 012100). IOP Publishing.
Hooshmand M. H. Basic results on an unsolved problem about factorization of finite groups // Communications in Algebra 49.7 (2021): 2927–2933.
Alamati, Navid, et al. Cryptographic group actions and applications // Advances in Cryptology–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II 26. Springer International Publishing, 2020.
Verschaffel L., Schukajlow S., Star J., & Van Dooren W. (2020). Word problems in mathematics education: A survey. ZDM, 52, 1-16.
van Veldhuizen, Toon, and Hans Cuypers. Investigating finite simple groups. Master Thesis
Singh, Priyanka, Manju Khari, and Nikhil S. Kaundanya. Impact of group theory in cryptosystem // Functional encryption. Cham: Springer International Publishing, 2021. 19–36.
Lanel G. H., Jinasena T. M. K. K., & Welihinda, B. A. (2021). A survey of public-key cryptography over non-abelian groups.
Kahrobaei D., Flores R., & Noce, M. (2023). Group-based cryptography in the quantum era. Not. Am. Math. Soc, 70(5), 752–763.
Vasco, María Isabel González, Delaram Kahrobaei, and Eilidh McKemmie. Applications of Finite non-Abelian Simple Groups to Cryptography in the Quantum Era // arXiv preprint arXiv:2308.14725 (2023).
Wagner N.R. and Magyarik M.R. A public-key cryptosystem based on the word problem // Proc. Advances in Cryptology–CRYPTO 1984, LNCS 196, Springer-Verlag (1985), pp. 19–36.
Sconza S., & Wildi, A. (2024). Knot-based Key Exchange protocol // Cryptology ePrint Archive.
Kahrobaei D., Khan B. A non-commutative generalization of ElGamal key exchange using polycyclic groups // IEEE GLOBECOM Global Telecommunications Conference [4150920], 2006. doi: 10.1109/glocom.2006.
Hofheinz D., & Steinwandt R. (2002). A practical attack on some braid group based cryptographic primitives // Public Key Cryptography—PKC 2003: 6th International Workshop on Practice and Theory in Public Key Cryptography Miami, FL, USA, January 6–8, 2003 Proceedings 6 (pp. 187–198). Springer Berlin Heidelberg.
Petrides G. (2006). Cryptographic applications of non-commutative algebraic structures and investigations of nonlinear recursions. The University of Manchester (United Kingdom).
Eick B., & Kahrobaei D. (2004). Polycyclic groups: a new platform for cryptology? // arXiv preprint math/0411077.
Kuperberg G. (2005). A subexponential-time quantum algorithm for the dihedral hidden subgroup problem // SIAM Journal on Computing. 35(1). 170–188.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
