Finite Non-Commutative Associative Algebras as Carriers of Hidden Discrete Logarithm Problem

Статья рассматривает новые конечные алгебры, представляющие интерес в качестве носителей задачи дискретного логарифмирования в скрытой группе. В частности, предложены новые 4-мерные и 6-мерные конечные некоммутативные алгебры с ассоциативной операцией умножения и описаны их свойства. Также предложен общий метод
задания конечных некоммутативных ассоциативных алгебр произвольной четной размерности mge 2. Некоторые из рассмотренных алгебр содержат глобальную двухстороннюю единицу, а другие не содержат такой единицы. В последнем случае элементы алгебры обратимы локально относительно некоторой локальной двухсторонней единицы, действующей в рамках некоторого подмножества элементов алгебры. Для алгебр последнего типа выведены формулы, описывающие множества правосторонних, левосторонних и двухсторонних локальных единиц. Также представлены алгебры, содержащие большое множество глобальных левосторонних (правосторонних) единиц при отсутствии в них глобальной двухсторонней единицы. Поскольку известные формы задания крытой задачи дискретного логарифмирования используют обратимость элементов алгебры относительно глобальной двухсторонней единицы, были предложены новые формы задания этой вычислительно трудной задачи. Результаты статьи могут быть использованы для разработки криптографических алгоритмов и протоколов с открытым ключом, включая постквантовые криптосхемы. Впервые предложена схема цифровой подписи, основанная на скрытой задаче дискретного логарифмирования.

Ключевые слова

конечная ассоциативная алгебра; некоммутативная алгебра; глобальная единица; левосторонняя единица; локальная единица; локальная обратимость; задача дискретного логарифмирования; криптосхема с открытым ключом; цифровая подпись; постквантовая криптография.

Литература

1. Sirwan, A. New Algorithm for Wireless Network Communication Security / A. Sirwan, N. Majeed // International Journal on Cryptography and Information Security. - 2016. - Т. 6, № 3. - С. 1-8.
2. Feng, Yiteng. A New Public Remote Integrity Checking Scheme with User and Data Privacy / Yiteng Feng, Guomin Yang, Joseph K.Liu // International Journal of Applied Cryptography. - 2017. - Т. 3, № 3. - С. 196-209.
3. Chiou, S.Y. Novel Digital Signature Schemes Based on Factoring and Discrete Logarithms / S.Y. Chiou // International Journal of Security and Its Applications. - 2016. - Т. 10, № 3. - С. 295-310.
4. Yan, S.Y. Quantum Computational Number Theory / S.Y. Yan. - New York: Springer, 2015.
5. Yan, S.Y. Quantum Attacks on Public-Key Cryptosystems / S.Y. Yan. - New York: Springer, 2014.
6. Proceedings of the 7th International Workshop on Post-Quantum Cryptography, PQCrypto 2016. Fukuoka, Japan, February 24-26, 2016. - Springer, 2016.
7. Post-Quantum Cryptography. 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings. - Springer, 2018.
8. Hiranvanichakorn, P. Provably Authenticated Group Key Agreement Based on Braid Groups. The Dynamic Case / P. Hiranvanichakorn // International Journal of Network Security. - 2017. - Т. 19, № 4. - С. 517-527.
9. Verma, G.K. Probable Security Proof of a Blind Signature Scheme over Braid Groups / G.K. Verma // International Journal of Network Security. - 2011. - Т. 12, № 2. - С. 118-120.
10. Myasnikov, A. A Practical Attack on a Braid Group Based Cryptographic Protocol / A. Myasnikov, V. Shpilrain, A. Ushakov // Advances in Cryptology - CRYPTO'05. Springer, 2005. - Т. 3621. - С. 86-96.
11. Moldovyan, D.N. A New Hard Problem over Non-Commutative Finite Groups for Cryptographic Protocols / D.N. Moldovyan, N.A. Moldovyan // 5th Int. Conference on Mathematical Methods, Models, and Architectures for Computer Network Security, MMM-ANCS 2010 Proceedings. - Springer, 2010. - Т. 6258. - С. 183-194.
12. Sakalauskas, E. Key Agreement Protocol (KAP) Using Conjugacy and Discrete Logarithm Problems in Group Representation Level / E. Sakalauskas, P. Tvarijonas, A. Raulynaitis // Informatica. - 2007. - Т. 18, № 1. - C. 115-124.
13. Moldovyan, D.N. Non-Commutative Finite Groups as Primitive of Public-Key Cryptoschemes / D.N. Moldovyan // Quasigroups and Related Systems. - 2010. - Т. 18, № 2. - С. 165-176.
14. Moldovyan, D.N. Cryptoschemes over Hidden Conjugacy Search Problem and Attacks Using Homomorphisms / D.N. Moldovyan, N.A. Moldovyan // Quasigroups Related Systems. - 2010. - Т. 18, № 2. - C. 177-186.
15. Kuzmin, A.S. Cryptographic Algorithms on Groups and Algebras / A.S. Kuzmin, V.T. Markov, A.A. Mikhalev, A.V. Mikhalev, A.A. Nechaev // Journal of Mathematical Sciences. - 2017. - V. 223, № 5. - С. 629-641.
16. Moldovyan, A.A. Non-Commutative Finite Associative Algebras of 2-Dimension Vectors / A.A. Moldovyan, N.A. Moldovyan, V.A. Shcherbacov // Computer Science Journal of Moldova. - 2017. - Т. 25, № 3. - С. 344-356.
17. Moldovyan, D.N. Non-Commutative Finite Associative Algebras of 3-Dimensional Vectors / D.N. Moldovyan, N.A. Moldovyan, V.A. Shcherbacov // Quasigroups and Related Systems. - 2018. - Т. 26, № 1. - С. 109-120.
18. Moldovyan, N.A. Vector Form of the Finite Fields GF(p^m) / N.A. Moldovyan, P.A. Moldovyanu // Bulletinul Academiei de Stiinte a Republicii Moldova. Matematica. - 2009. - № 3. - С. 57-63.
19. Schnorr, C.P. Efficient Signature Generation by Smart Cards / C.P. Schnorr // Journal of Cryptology. - 1991. - V. 4. - P. 161-174.