The security analysis of the key exchange protocol based on the matrix power function defined over a family of non-commuting groups

Aleksejus Mihalkovich; Jokubas Zitkevicius; Eligijus Sakalauskas; Aleksejus Mihalkovich; Jokubas Zitkevicius; Eligijus Sakalauskas

doi:10.3934/math.20241312

AIMS Mathematics

2024, Volume 9, Issue 10: 26961-26982. doi: 10.3934/math.20241312

Previous Article Next Article

Research article

The security analysis of the key exchange protocol based on the matrix power function defined over a family of non-commuting groups

Department of Applied Mathematics, Kaunas University of Technology, Studentu str. 50, Kaunas, LT-51368, Lithuania

Received: 12 June 2024 Revised: 23 August 2024 Accepted: 28 August 2024 Published: 18 September 2024
MSC : 20F05, 62R99, 68W30, 94A60

In this paper, we revisited the previously proposed key exchange protocol based on the matrix power function. We prove that the entries of the public key matrices of both parties of the protocol are uniform. Using this result we defined a security game for our protocol and show that the malicious attacker cannot gain any significant advantage in winning this game by applying faithful representation or the linearization approaches. Moreover, we showed that the shared key is computationally indistinguishable from the imitation key if the security parameters are properly chosen.
- matrix power function,
- security analysis,
- non-commuting cryptography,
- uniform distribution,
- statistical analysis
Citation: Aleksejus Mihalkovich, Jokubas Zitkevicius, Eligijus Sakalauskas. The security analysis of the key exchange protocol based on the matrix power function defined over a family of non-commuting groups[J]. AIMS Mathematics, 2024, 9(10): 26961-26982. doi: 10.3934/math.20241312

Related Papers:

Abstract

In this paper, we revisited the previously proposed key exchange protocol based on the matrix power function. We prove that the entries of the public key matrices of both parties of the protocol are uniform. Using this result we defined a security game for our protocol and show that the malicious attacker cannot gain any significant advantage in winning this game by applying faithful representation or the linearization approaches. Moreover, we showed that the shared key is computationally indistinguishable from the imitation key if the security parameters are properly chosen.

References

[1]	W. Diffie, M. Hellman, New directions in cryptography, IEEE T. Inform. Theory, 22 (1976), 644–654. http://dx.doi.org/10.1109/TIT.1976.1055638 doi: 10.1109/TIT.1976.1055638
[2]	D. Boneh, V. Shoup, A graduate course in applied cryptography, 0.6 Eds., 2023, unpublished work. Available from: https://toc.cryptobook.us/book.pdf.
[3]	E. Bresson, Y. Lakhnech, L. Mazaré, B. Warinschi, A generalization of DDH with applications to protocol analysis and computational soundness, In: Advances in cryptology-CRYPTO 2007, Berlin: Springer, 2007,482–499. http://dx.doi.org/10.1007/978-3-540-74143-5_27
[4]	R. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120–126. http://dx.doi.org/10.1145/359340.359342 doi: 10.1145/359340.359342
[5]	P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev., 41 (1999), 303–332. http://dx.doi.org/10.1137/S0036144598347011 doi: 10.1137/S0036144598347011
[6]	Submission requirements and evaluation criteria for the post-quantum cryptography standardization process, NIST Computer Security Resource Center, 2016. Available from: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.
[7]	Post-quantum cryptography, selected algorithms 2022, NIST Computer Security Resource Center, 2022. Available from: https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022.
[8]	Post-quantum cryptography, round 4 submissions, NIST Computer Security Resource Center, 2022. Available from: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions.
[9]	K. Ko, S. Lee, J. Cheon, J. Han, J. Kang, C. Park, New public-key cryptosystem using braid groups, In: Advances in cryptology-CRYPTO 2000, Berlin: Springer, 2000,166–183. http://dx.doi.org/10.1007/3-540-44598-6_10
[10]	V. Shpilrain, A. Ushakov, The conjugacy search problem in public key cryptography: unnecessary and insufficient, AAECC, 17 (2006), 285–289. http://dx.doi.org/10.1007/s00200-006-0009-6 doi: 10.1007/s00200-006-0009-6
[11]	E. Sakalauskas, N. Listopadskis, P. Tvarijonas, Key agreement protocol (KAP) based on matrix power function, Proceedings of Sixth International Conference on Information Research and Applications, 2008, 92–96.
[12]	A. Mihalkovich, E. Sakalauskas, Asymmetric cipher based on MPF and its security parameters evaluation, Lietuvos Matematikos Rinkinys, 53 (2012), 72–77. http://dx.doi.org/10.15388/LMR.A.2012.13 doi: 10.15388/LMR.A.2012.13
[13]	J. Liu, H. Zhang, J. Jia, A linear algebra attack on the non-commuting cryptography class based on matrix power function, In: Information security and cryptology, Cham: Springer, 2017,343–354. http://dx.doi.org/10.1007/978-3-319-54705-3_21
[14]	E. Sakalauskas, A. Mihalkovich, Improved asymmetric cipher based on matrix power function resistant to linear algebra attack, Informatica, 28 (2017), 517–524. http://dx.doi.org/10.15388/Informatica.2017.142 doi: 10.15388/Informatica.2017.142
[15]	A. Mihalkovich, M. Levinskas, Investigation of matrix power asymmetric cipher resistant to linear algebra attack, In: Information and software technologies, Cham: Springer, 2019,197–208. http://dx.doi.org/10.1007/978-3-030-30275-7_16
[16]	A. Mihalkovich, E. Sakalauskas, K. Luksys, Key exchange protocol defined over a non-commuting group based on an NP-complete decisional problem, Symmetry, 12 (2020), 1389. http://dx.doi.org/10.3390/sym12091389 doi: 10.3390/sym12091389
[17]	A. Mihalkovich, K. Luksys, E. Sakalauskas, Sigma identification protocol construction based on MPF defined over non-commuting platform group, Mathematics, 10 (2022), 2649. http://dx.doi.org/10.3390/math10152649 doi: 10.3390/math10152649
[18]	M. Durcheva, TrES: tropical encryption scheme based on double key exchange, European Journal of Information Technologies and Computer Science, 2 (2022), 11–17. http://dx.doi.org/10.24018/compute.2022.2.4.70 doi: 10.24018/compute.2022.2.4.70
[19]	X. Jiang, H. Huang, G. Pan, Cryptanalysis of tropical encryption scheme based on double key exchange, Journal of Cyber Security and Mobility, 12 (2023), 205–220. http://dx.doi.org/10.13052/jcsm2245-1439.1224 doi: 10.13052/jcsm2245-1439.1224
[20]	Modular maximal-cyclic group, Groupprops, 2023, Available from: https://groupprops.subwiki.org/wiki/Modular_maximal-cyclic_group.
[21]	H. Grundman, T. Smith, Automatic realizability of Galois groups of order 16, Proc. Amer. Math. Soc., 124 (1996), 2631–2640. http://dx.doi.org/10.1090/S0002-9939-96-03345-X doi: 10.1090/S0002-9939-96-03345-X
[22]	H. Grundman, T. Smith, Realizability and automatic realizability of Galois groups of order 32, Open Math., 8 (2010), 244–260. https://doi.org/10.2478/s11533-009-0072-x doi: 10.2478/s11533-009-0072-x
[23]	H. Grundman, T. Smith, Galois realizability of groups of order 64, Centr. Eur. J. Math., 8 (2010), 846–854. http://dx.doi.org/10.2478/s11533-010-0052-1 doi: 10.2478/s11533-010-0052-1
[24]	A. Mihalkovich, E. Sakalauskas, M. Levinskas, Key exchange protocol based on the matrix power function defined over $\mathbb{M}_16$, In: Intelligent computing, Cham: Springer, 2022,511–531. http://dx.doi.org/10.1007/978-3-031-10467-1_32
[25]	Faithful irreducible representation of M16, Groupprops, 2023, Available from: https://groupprops.subwiki.org/wiki/Faithful_irreducible_representation_of_M16.
[26]	J. Faugère, A. Joux, Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases, In: Advances in cryptology-CRYPTO 2003, Berlin: Springer, 2003, 44–60. http://dx.doi.org/10.1007/978-3-540-45146-4_3
[27]	A. Kipnis, J. Patarin, L. Goubin, Unbalanced oil and vinegar signature schemes, Advances in Cryptology-EUROCRYPT'99, Berlin: Springer, 1999,206–222. http://dx.doi.org/10.1007/3-540-48910-X_15
[28]	R. Benadjila, T. Feneuil, M. Rivain, MQ on my mind: post-quantum signatures from the non-structured multivariate quadratic problem, Proceedings of IEEE 9th European Symposium on Security and Privacy, 2024,468–485. http://dx.doi.org/10.1109/EuroSP60621.2024.00032
[29]	A. Mihalkovich, J. Zitkevicius, On the decisional problem based on matrix power function defined over non-commutative group, Mathematical Models in Engineering, 10 (2024), 1–9. http://dx.doi.org/10.21595/mme.2024.24071 doi: 10.21595/mme.2024.24071

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)