Algebraic attacks on multivariate public key cryptosystems
Mandeep Kaurmandeep.kaur@bennett.edu.inIndiaView full profile → , Gaganjot Kaurgaganjot28784@gmail.comDepartment of Computer Science and EngineeringRaj Kumar Goel Institute of TechnologyGhaziabad, Uttar Pradesh, 201017, IndiaView full profile → , D. Sathis Kumardean_sp@adityauniversity.inSurampalemView full profile → , *Samir N. AjaniCorresponding authorsamir.ajani@gmail.comSchool of Computer Science and EngineeringRamdeobaba University (RBU)Nagpur, Maharashtra, 440013, IndiaView full profile → , Ramesh Dhulipudirameshdhulipudi@outlook.comDepartment of CSE (Artificial Intelligence)Pragati Engineering CollegeKakinada District, Andhra Pradesh, 533437, IndiaView full profile → , Rahul A. Padgilwarrahul.padgilwar1@vit.eduDepartment of Engineering Science and HumanitiesVishwakarma Institute of TechnologyPune, Maharashtra, 411037, IndiaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Apr 2026
- Published Online:
- 31 Oct 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-3038
- Pages:
- 4133–4143
Abstract
One promising post-quantum security candidate is Multivariate Public Key Cryptosystems (MPKCs); they are susceptible to algebraic attacks. In this paper, I will discuss the vulnerability of MPKCs to higher-order algebraic cryptanalysis, which transforms nonlinear systems of polynomies into structured ideals on finite fields. The aim is to assess the efficiency of the attacks through the method of computation of Gröbner basis, linearization and re-linearization. The algorithm is a combination of Buchberger and F4/F5 algorithms, and is supported by experimental study of benchmark MQ instances. The comparative evaluation reports a key recovery success rate of 94.2% for the proposed algebraic attack, compared with 62.5% for classical brute-force and 79.8% for hybrid cryptanalysis. The corresponding computation times are 128, 356, and 214 seconds, respectively, representing reductions of 64.04% and 40.19% relative to the two baselines. These preliminary results indicate improved attack efficiency under the evaluated conditions; however, further benchmark specification and statistical validation are required to establish reproducibility. The findings highlight the vulnerabilities in the structure of specific parameter settings and the safe design suggestions. The paper contributes a new and meticulous evaluation framework to the existing knowledge base on the notion of algebraic resilience in post-quantum cryptography.
Keywords
Subject Classifications
References
[1] G. Teşeleanu, “Partial exposure attacks against a family of RSA-like cryptosystems,” Cryptography, vol. 9, no. 1, Art. no. 2 (2025), doi: 10.3390/cryptography9010002.
[2] P. Zajac, “Algebraic cryptanalysis with MRHS equations,” Cryptography, vol. 7, no. 2, Art. no. 19 (2023), doi: 10.3390/cryptography7020019.
[3] M. Rahmani, A. Nitaj, and M. Ziane, “Partial exposure attacks on a new RSA variant,” Cryptography, vol. 8, no. 4, Art. no. 44 (2024), doi: 10.3390/cryptography8040044.
[4] N. A. S. Abdul Jamal, M. R. Kamel Ariffin, S. H. Sapar, and K. Abdullah, “New identified strategies to forge multivariate signature schemes,” Symmetry, vol. 14, no. 11, Art. no. 2368 (2022), doi: 10.3390/sym14112368.
[5] M. Rahmani, A. Nitaj, A. Tadmori, and M. Ziane, “An improved attack on the RSA variant based on cubic Pell equation,” Cryptography, vol. 9, no. 2, Art. no. 40 (2025), doi: 10.3390/cryptography9020040.
[6] R. Banchhor, S. N. Patil, G. Kaur, S. Makhmudov, P. Khobragade, and I. Yusubov, “Graph neural networks for modelling financial market dependencies,” in Proc. 2026 Int. Conf. Emerging Smart Computing and Informatics (ESCI), Pune, India, pp. 1–6 (2026), doi: 10.1109/ESCI68015.2026.11493308.
[7] E. Petropoulos, “Deep learning and optimization approaches in efficient resource management in 6G communication networks using a hybrid quantum duplet-convolutional neural network model: A review,” IJACECT, vol. 14, no. 2, pp. 152–157 (Dec. 2025).
[8] A. Overmars and S. Venkatraman, “Mathematical attack of RSA by extending the sum of squares of primes to factorize a semi-prime,” Mathematical and Computational Applications, vol. 25, no. 4, Art. no. 63 (2020), doi: 10.3390/mca25040063.
[9] W. Sripanya, W. Rungrottheera, and P. Hyunsin, “Fourier series analysis and computation based on function characteristics,” Journal of Interdisciplinary Mathematics, vol. 28, no. 6, pp. 2109–2120 (2025), doi: 10.47974/JIM-2352.
[10] A. Moldovyan, D. Moldovyan, N. Moldovyan, and A. Kurysheva, “A method for specifying complete signature randomization and an algebraic algorithm based on it,” Mathematics, vol. 12, no. 13, Art. no. 1970 (2024), doi: 10.3390/math12131970.
[11] M. Durcheva, “Cryptography based on (idempotent) semirings: Abandoning tropicality,” Encyclopedia, vol. 5, no. 1, Art. no. 26 (2025), doi: 10.3390/encyclopedia5010026.
[12] A. Vishnoi, P. Madan, R. Sharma, L. Sapra, P. Narooka, and D. Panwar, “An IoT security framework for tamper-proof data transmission using homomorphic transform-based blockchain,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 29, no. 3, pp. 1461–1471 (2026), doi: 10.47974/JDMSC-2605.
[13] H. Huang, “Cryptosystems based on tropical congruent transformation of symmetric matrices,” Symmetry, vol. 14, no. 11, Art. no. 2378 (2022), doi: 10.3390/sym14112378.
[14] R. C. Poonia, R. Almakki, A. K. J. Saudagar, A. Altameem, and M. Albathan, “An optimization approach for real-time object detection in IoT devices through edge computing and deep learning,” Journal of Information and Optimization Sciences, vol. 45, no. 5, pp. 1465–1475 (2024), doi: 10.47974/JIOS-1768.
