Post-Quantum Public-Key Cryptoschemes on Finite Algebras
Keywords:
post-quantum cryptography, multivariate cryptography, finite algebra, non-commutative algebra, vector finite field, nonlinear mappingsAbstract
One direction in the development of practical post-quantum public-key cryptographic algorithms is the use of finite algebras as their algebraic carrier. Two approaches in this direction are considered: 1) construction of electronic digital signature algorithms with a hidden group on non-commutative associative algebras and 2) construction of multidimensional cryptography algorithms using the exponential operation in a vector finite field (in a commutative algebra, which is a finite field) to specify a nonlinear mapping with a secret trapdoor. The first approach involves the development of two types of cryptoschemes: those based on the computational difficulty of a) the hidden discrete logarithm problem and b) solving a large system of quadratic equations. For the second type, problems arise in ensuring complete randomization of the digital signature and specifying non-commutative associative algebras of large dimension. Ways to solve these problems are discussed. The importance of studying the structure of finite non-commutative algebras from the point of view of decomposition into a set of commutative subalgebras is shown. Another direction is aimed at a significant (10 or more times) reduction in the size of the public key in multivariate-cryptography algorithms and is associated with the problem of developing formalized, parameterizable, unified methods for specifying vector finite fields of large dimensions (from 5 to 130) with a sufficiently large number of potentially implementable types and modifications each type (up to 2500 or more). Variants of such methods and topologies of nonlinear mappings on finite vector fields of various dimensions are proposed. It is shown that the use of mappings that specify the exponential operation in vector finite fields potentially eliminates the main drawback of known multivariate-cryptography algorithms, which is associated with the large size of the public key.
References
2. Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on quantum computer. SIAM Journal of Computing. 1997. vol. 26. pp. 1484–1509.
3. Post-Quantum Cryptography. Proceedings of the 13th International Conference, PQCrypto 2022. Lecture Notes in Computer Science. 2022. vol. 13512.
4. Johansson T., Smith-Tone D. Post-Quantum Cryptography. Proceedings of the 14th International Conference, PQCrypto 2023. Lecture Notes in Computer Science. 2023. vol. 14154.
5. Alagic G, Cooper D., Dang Q., Dang T., Kelsey J., Lichtinger J., Liu Y., Miller C., Moody D., Peralta R., Perlner R., Robinson A., Smith-Tone D., Apon D. Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology. 2022. Available at: https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934458 (accessed: обращения: 25.02.2024).
6. Han J., Zhuang J. DLP in semigroups: algorithms and lower bounds. J. Math. Cryptol. 2022. vol. 16. no. 1. pp. 278–288.
7. Battarbee C., Kahrobaei D., Perret L., Shahandashti S.F. SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures. Post-Quantum Cryptography. PQCrypto 2023. Lecture Notes in Computer Science. 2023. vol. 14154. pp. 113–138. DOI: 10.1007/978-3-031-40003-2_5.
8. Vysotskaya V.V., Chizhov I.V. The security of the code-based signature scheme based on the Stern identification protocol. Applied Discrete Mathematics. 2022. № 57. С. 67−90. DOI: 10.17223/20710410/57/5.
9. Kosolapov Y.V., Turchenko O.Y. On the construction of a semantically secure modification of the McEliece cryptosystem. Applied Discrete Mathematics. 2019. № 45. С. 33−43. DOI: 10.17223/20710410/45/4.
10. Gartner J. NTWE: A Natural Combination of NTRU and LWE. Post-Quantum Cryptography. PQCrypto 2023. Lecture Notes in Computer Science, 2023. vol. 14154. pp. 321–353. DOI: 10.1007/978-3-031-40003-2_12.
11. Lysakov I.V. Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method. Mathematical Aspects of Cryptography. 2023. vol. 14. no. 2. pp. 111–122. DOI: 10.4213/mvk441.
12. Hamlin B., Song F. Quantum Security of Hash Functions and Property-Preservation of Iterated Hashing. Post-Quantum Cryptography. PQCrypto 2019 / Lecture Notes in Computer Science. 2019. vol. 11505. pp. 329–349. DOI: 10.1007/978-3-030-25510-7_18.
13. Agibalov G.P. ElGamal cryptosystems on Boolean functions. Applied Discrete Mathematics. 2018. № 42. С. 57−65. DOI: 10.17223/20710410/42/4.
14. Ding J., Petzoldt A., Schmidt D.S. Multivariate Cryptography. Multivariate Public Key Cryptosystems. Advances in Information Security. 2020. vol. 80. DOI: 10.1007/978-1-0716-0987-3_2.
15. Debnath S., Kundu N., Mishra D., Choudhury T. Post-quantum digital signature scheme based on multivariate cubic problem. Journal of Information Security and Applications. 2020. vol. 53. DOI: 10.1016/j.jisa.2020.102512.
16. Ding J., Petzoldt A., Schmidt D.S. Oil and Vinegar. Multivariate Public Key Cryptosystems. Advances in Information Security. 2020. vol. 80. pp. 89–151. Springer, New York. DOI: 10.1007/978-1-0716-0987-3_5.
17. Cartor R., Cartor M., Lewis M., Smith-Tone D. IPRainbow. Post-Quantum Cryptography. PQCrypto 2022. Lecture Notes in Computer Science. 2022. vol. 13512. pp. 170–184. DOI: 10.1007/978-3-031-17234-2_9.
18. Beullens W. MAYO: practical post-quantum signatures from oil-and-vinegar maps. Proceedings of the International Conference on Selected Areas in Cryptography (SAC 2021). Lecture Notes in Computer Science. 2022. vol. 13203. pp. 355–376.
19. Moldovyan A.A., Moldovyan D.N., Moldovyan N.A. A new approach to the development of multivariate cryptography algorithms. Voprosy kiberbezopasnosti – Cibersecurity questtions. 2023. no. 2(54). pp. 52–64. DOI: 10.21681/2311-3456-2023-2-52-6.
20. Moldovyan A.A., Moldovyan N.A. Vector finite fields of characteristic two as algebraic support of multivariate cryptography. Computer Science Journal of Moldova. 2024. no. 1(94). pp. 46–60. DOI: 10.56415/csjm.v32.04.
21. Duong M.T., Moldovyan D.N., Do B.V., Nguyen M.H. Post-quantum signature algorithms on non-commutative algebras, using difficulty of solving systems of quadratic equations. Computer Standards and Interfaces. 2023, vol. 86. no. 103740. DOI: 10.1016/j.csi.2023.103740.
22. Moldovyan D.N. A practical digital signature scheme based on the hidden logarithm problem. Computer Science Journal of Moldova. 2021. vol. 29, no. 2(86). pp. 206–226.
23. Moldovyan N.A., Moldovyanu P.A. Vector Form of the Finite Fields GF(pm). Bulletin of Academy of Sciences of Moldova. Mathematics. 2009. no. 3(61). pp. 57–63.
24. Ding J., Petzoldt A., Schmidt D.S. Solving Polynomial Systems. In: Multivariate Public Key Cryptosystems. Advances in Information Security. Springer. New York. 2020. vol. 80. pp. 185–248. DOI: 10.1007/978-1-0716-0987-3_8.
25. Ding J., Petzoldt A. Current State of Multivariate Cryptography. IEEE Security and Privacy. 2017. vol. 15. no. 4. pp. 28–36.
26. Qiao S., Han W., Li Y., Jiao L. Construction of Extended Multivariate Public Key Cryptosystems. International Journal of Network Security. 2016. vol. 18. no. 1. pp. 60–67.
27. Rainbow Signature. One of three NIST Post-quantum Signature Finalists [on line] 2021. Available at: https://www.pqcrainbow.org/ (accessed: 25.02.2024).
Published
How to Cite
Section
Copyright (c) Николай Андреевич Молдовян, Александр Андреевич Молдовян, Дмитрий Николаевич Молдовян
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms: 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. 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. 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).