Abstract This paper introduces two new forms of the hidden discrete logarithm problem defined over a finite non- commutative associative algebras containing a large set of global single-sided units. The proposed forms are promising for development on their base practical post-quantum public key-agreement schemes and are characterized in performing two different masking operations over the output value of the base exponentiation operation that is executed in framework of the public key computation. The masking operations represent homomorphisms and each of them is mutually commutative with the exponentiation operation. Parameters of the masking operations are used as private key elements. A 6-dimensional algebra containing a set of p3 global left-sided units is used as algebraic support of one of the hidden logarithm problem form and a 4- dimensional algebra with p2 global right-sided units is used to implement the other form of the said problem. The result of this paper is the proposed two methods for strengthened masking of the exponentiation operation and two new post-quantum public key-agreement cryptoschemes. Mathematics subject classification: 94A60, 16Z05, 14G50, 11T71, 16S50.

References

[1] Attema T., “First NIST Standardization Conference- April 11-13, 2018,” http://prometheuscrypt.gforge.inria.fr/2018-04- 18.pqc2018.html, Last Visited, 2021.

[2] Avanzi R., Bos J., Ducas L., Kiltz K., Lepoint T., Lyubashevsky V., Schanck J., Schwabe P., Seiler G., and Stehlé D., “CRYSTALS-Kyber. Algorithm Specifications and Supporting Documentation,” https://cryptojedi.org/papers/kybernist- 20171130.pdf, Last Visited, 2021.

[3] Chen C., “NTRU: Second Round Update,” https://ntru.org/talks/20190823_nist_round2.pdf, Last Visited, 2021.

[4] D’Anvers J., Karmakar A., Roy S., and Vercauteren F., “Saber: Module-LWR Based (11) ()RX B X A ()iiB X A B X A ttA B R Y ''( ) ( )t x t t t xY R B N A R B N A N 'R x t '1 1 1( , , )x t R '2 2 2( , , )x t R 1 1 112t x tZ B Y A 2 2 221t x tZ B Y A L R 378 The International Arab Journal of Information Technology, Vol. 18, No. 3, May 2021 Key Exchange, CPA-Secure Encryption and CCA-Secure KEM,” http://pure- oai.bham.ac.uk/ws/files/70656269/Saber._Module _LWR.pdf, Last Visited, 2021.

[5] Jalali A., Azarderakhsh R., Kermani M., and Jao D., “Supersingular Isogeny Key Encapsulation.” https://sike.org/files/SIDH-spec.pdf, Last Visited, 2021.

[6] Kosolapov Y. and Turchenko O., “On the Construction of A Semantically Secure Modification of The Mceliece Cryptosystem,” Prikl. Diskr. Mat., no. 45, pp. 33-43, 2019.

[7] Kuzmin A., Markov V., Mikhalev A., Mikhalev A., and Nechaev A., “Cryptographic Algorithms on Groups and Algebras,” Journal of Mathematical Sciences, vol. 223, no. 5, pp. 629- 641, 2017.

[8] Langer T. and Steinwandt R., “Post-Quantum Cryptography,” in Proceedings of 9th International Conference on Post-Quantum Cryptography, Fort Lauderdale, 2018.

[9] Li Y., Deng R., and Wang X., “The Equivalence of McEliece’s and Niederreiter’s Publickey Cryptosystems,” IEEE Transactions on Information, vol. 40, no. 1, pp. 271-273, 1994.

[10] Lu Y., Zhang Q., and Li J., “A Certificate-Based AKA Protocol Secure Against Public Key Replacement Attacks,” The International Arab Journal of Information Technology, vol. 16, no. 4, pp. 754-765, 2019.

[11] Moldovyan A. and Moldovyan N., “Post- Quantum Signature Algorithms Based on The Hidden Discrete Logarithm Problem,” Computer Science Journal of Moldova, vol. 26, no. 3, pp. 301-313, 2018.

[12] Moldovyan D., “Non-Commutative Finite Groups as Primitive of Public-Key Cryptoschemes,” Quasigroups and Related Systems, vol. 18, no. 2, pp. 165-176, 2010.

[13] Moldovyan D., “Post-Quantum Public Key- Agreement Scheme Based on A New form of The Hidden Logarithm Problem,” Computer Science Journal of Moldova, vol. 27, no. 1, pp. 56-72, 2019.

[14] Moldovyan D. and Moldovyan N., “Cryptosche mes over Hidden Conjugacy Search Problem and Attacks Using Homomorphisms,” Quasigroups and Related Systems, vol. 18, no. 2, pp. 177-186, 2010.

[15] Moldovyan D. and Moldovyan N., “A New Hard Problem over Non-Commutative Finite Groups for Cryptographic Protocols,” in Proceedings of 5th Intentional Conference on Mathematical Methods, Models, and Architectures for Computer Network Security, St.Petersburg, pp. 183-194, 2010.

[16] Moldovyan N. and Moldovyan A., “Finite Non- Commutative Associative Algebras for Setting the Hidden Discrete Logarithm Problem and Post- Quantum Cryptoschemes on its Base,” Bulletin of Academy of Sciences of Moldova Mathematics, no. 1, pp. 71-78, 2019.

[17] Moldovyan N., “Unified Method for Defining Finite Associative Algebras of Arbitrary Even Dimensions,” Quasigroups and Related Systems, vol. 26, no. 2, pp. 263-270, 2018.

[18] Moldovyan N. and Moldovyan A., “Finite Non- commutative Associative Algebras as Carriers of Hidden Discrete Logarithm Problem,” Bulletin of the South Ural State University. Ser. Mathematical Modelling, Programming and Computer Software, vol. 12, no. 1, pp. 66-81, 2019.

[19] Post-Quantum Cryptography. Round 3 Submissions. Round 3 Finalists: Public-key Encryption and Key-establishment Algorithms. https://csrc.nist.gov/projects/post-quantum- cryptography/round-3-submissions, Last Visited, 2021.

[20] Yan S., Quantum Attacks on Public-Key Cryptosystems, Springer, 2014.

[21] Yan S., Quantum Computational Number Theory, Springer, 2015. Algebraic Supports and New Forms of the Hidden Discrete Logarithm Problem for ... 379 Dmitriy Moldovyan A research fellow of the Laboratory of Cybersecurity and Post-quantum Cryptosystems (LCPC) of St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences (SPIIRAS) at St. Petersburg Federal Research Center of the Russian Academy of Sciences (SPC RAS) and a associate professor with the Saint-Petersburg Electro-technical University “LETI”. His research interests include computer security, digital signature algorithms, and post-quantum public-key cryptoschemes. He is author or co-author of 7 inventions and 65 scientific articles, books, and reports. He received his Ph.D. from SPIIRAS (2012). Nashwan Al-Majmar, An associate professor with department of Computer Sciences and Information Technology, Ibb University, Yemen. He received his B.S. degree in Computer Systems Engineering and Informatics, in 2003, the M.S. degree in Computer Systems Engineering and Informatics, in 2006 from Saint-Petersburg Electro-technical University “LETI”, Saint-Petersburg, Russia, and the Ph.D. degree in Methods and Systems of Information Protection and Security from Saint-Petersburg State University of Information Technologies, Mechanics and Optics, Saint-Petersburg, Russia, in 2010. His research interests include "information security", "AI" and "software development". Alexander Moldovyan, A chief researcher of the LCPC of SPIIRAS at SPC RAS and a professor with the Saint-Petersburg Electro-technical University “LETI”. His research interests include information security and cryptographic protocols. He has authored or co-authored more than 60 inventions and 220 scientific articles, books, and reports. He received his Ph.D. from the “LETI” University (1996).