Cryptographic protocols based on graph isomorphism hardness
*Prabhat SharmaCorresponding authorprabhat.sharma.orp@chitkara.edu.inCentre for Research Impact and OutcomeChitkara UniversityRajpura, Punjab, 140417, IndiaView full profile → , M. Radhika Manimradhika@outlook.comDepartment of Computer Science & EngineeringPragati Engineering CollegeSurampalem, Kakinada District, Andhra Pradesh, 533437, IndiaView full profile → , Mahesh M. Zadezademahesh1983@gmail.comDepartment of Electronics & Telecommunication EngineeringS. K. N. Sinhgad College of EngineeringPandharpur, Maharashtra, 413304, IndiaView full profile → , I. Durga Bhavanidurgabhavanisupriya@gmail.comDepartment of Computer ScienceAditya Degree & PG Colleges (Autonomous)Kakinada, Andhra Pradesh, 533003, IndiaView full profile → , R. Snehaasnehaa.avmt032@avit.ac.inDepartment of Humanities and Sciences (Mathematics Division)Aarupadai Veedu Institute of TechnologyVinayaka Mission’s Research Foundation (Deemed to be University)Paiyanoor, Chennai, Tamil Nadu, 603104, IndiaView full profile → , Kasturi Rohinikasturirohini2024@protonmail.comCentre for Multidisciplinary ResearchAnurag UniversityHyderabad, Telangana, 500088, 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-3028
- Pages:
- 4021–4032
Abstract
Graph isomorphism (GI) has turned out to be an attractive basis of the construction of secure cryptographic protocols because it has a special set of computational hardness properties, not in the classical NP-complete classes. This article introduces a new cryptographic system that utilizes the graph isomorphism hardness where pairs of graphs of the same structure are used to conduct secure communication through the use of permutation-based mappings. The protocol proposed presents a strong public- private key architecture in which isomorphic graph transformations are encryption primitives. The security properties and resistance to structural inference attacks are modeled by creating a mathematical formulation. The encryption algorithm uses randomized permutations to hide the correspondences between the vertex with confidentiality and unpredictability. The efficiency and the possible quantum resistance of the proposed approach is compared to the NP-complete and post-quantum cryptographic assumptions, which helps to draw the comparative analysis.
Keywords
Subject Classifications
References
[1] D. Olifer, N. Goranin, A. Cenys, A. Kaceniauskas, and J. Janulevicius, “Defining the Minimum Security Baseline in a Multiple Security Standards Environment by Graph Theory Techniques,” Applied Sciences, vol. 9, no. 4, Art. no. 681 (2019), doi: 10.3390/app9040681.
[2] M. Zhao, H. Wang, and B. Yao, “Graphic Groups, Graph Homomorphisms, and Graphic Group Lattices in Asymmetric Topology Cryptography,” Entropy, vol. 25, no. 5, Art. no. 720 (2023), doi: 10.3390/e25050720.
[3] B. Schoenmakers and T. Segers, “Secure Groups for Threshold Cryptography and Number-Theoretic Multiparty Computation,” Cryptography, vol. 7, no. 4, Art. no. 56 (2023), doi: 10.3390/cryptography7040056.
[4] E. Corona-Bermúdez, J. C. Chimal-Eguía, and G. Téllez-Castillo, “Cryptographic Services Based on Elementary and Chaotic Cellular Automata,” Electronics, vol. 11, no. 4, Art. no. 613 (2022), doi: 10.3390/electronics11040613.
[5] P. K. Deshmukh, S. K. Verma, P. D. Jadhav, S. I. Baltabaevich, V. Vijaykumar, and A. Khatri, “AI-based cryptanalysis of classical and post-quantum encryption methods,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 29, no. 2-B, pp. 759–767 (2026), doi: 10.47974/JDMSC-2522.
[6] F. Alonso, B. Samaniego, G. Farias, and S. Dormido-Canto, “Analysis of Cryptographic Algorithms to Improve Cybersecurity in the Industrial Electrical Sector,” Applied Sciences, vol. 14, no. 7, Art. no. 2964 (2024), doi: 10.3390/app14072964.
[7] D. H. F. Ansari and R. Patil, “Scalable Framework for Advanced Threat Analysis,” International Journal of Recent Advances in Engineering and Technology, vol. 14, no. 3s, pp. 147–151 (2025), doi: 10.65521/intjournalrecadvengtech.v14i3s.1683.
[8] A. V. Potnurwar, V. K. Bongirwar, S. Ajani, N. Shelke, M. Dhone, and N. Parati, “Deep learning-based rule-based feature selection for intrusion detection in industrial Internet of Things networks,” International Journal of Intelligent Systems and Applications in Engineering, vol. 11, no. 10s, pp. 23–35 (2023).
[9] J. Selvaraj, W.-C. Lai, B. P. Kavin, C. Kavitha, and G. H. Seng, “Cryptographic Encryption and Optimization for Internet of Things Based Medical Image Security,” Electronics, vol. 12, no. 7, Art. no. 1636 (2023), doi: 10.3390/electronics12071636.
[10] 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.
[11] B. Y. Chong and I. Salam, “Investigating Deep Learning Approaches on the Security Analysis of Cryptographic Algorithms,” Cryptography, vol. 5, no. 4, Art. no. 30 (2021), doi: 10.3390/cryptography5040030.
[12] M. Kihara and S. Iriyama, “Security Verification of an Authentication Algorithm Based on Verifiable Encryption,” Information, vol. 14, no. 2, Art. no. 126 (2023), doi: 10.3390/info14020126.
[13] A. Guru, B. K. Mohanta, H. Mohapatra, F. Al-Turjman, C. Altrjman, and A. Yadav, “A Survey on Consensus Protocols and Attacks on Blockchain Technology,” Applied Sciences, vol. 13, no. 4, Art. no. 2604 (2023), doi: 10.3390/app13042604.
