Complexity bounds for NP-hard problems in cryptography
Monika Patilmonahire10@gmail.comDepartment of Artificial Intelligence and Data ScienceIndira College of Engineering & ManagementPune, Maharashtra, 410506, IndiaView full profile → , *D. Sathis KumarCorresponding authordean_sp@adityauniversity.inSchool of PharmacyAditya UniversitySurampalem, Kakinada District, Andhra Pradesh, 533437, IndiaView full profile → , Gagan Tiwarigagan.tiwari@niu.edu.inDepartment of Computer SciencesNoida International UniversityGreater Noida, Uttar Pradesh, 203201, IndiaView full profile → , Vinod S. Sapkalvinodsapkal@pvppcoe.ac.inDepartment of Information TechnologyVasantdada Patil Pratishthan’s College of Engineering & Visual ArtsSion, Mumbai, Maharashtra, 400022, IndiaView full profile → , Jyotsna Suryavanshijyotsna.suryavanshi@vit.eduDepartment of Engineering Science and HumanitiesVishwakarma Institute of TechnologyPune, Maharashtra, 411037, IndiaView full profile → , Sanjiv Kumar Shuklasanjeev@rungta.orgDepartment of Computer Science and EngineeringRungta College of Engineering and TechnologyRungta International Skills UniversityBhilai, Chhattisgarh, 490024, 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-3069
- Pages:
- 4509–4520
Abstract
The complexity bounds of NP-hard problems are one of the main topics in modern cryptography, where the security of a scheme is frequently based on the intractability of the computations. This paper explores the theoretical and practical consequences of NP-hardness in cryptographic designs, such as lattice-based designs, hash functions, and secure multiparty designs. We examine reduction methods in cryptographic proofs to put hardness hypotheses and investigate precise algorithms that have exponential-time complexity characterizing worst-case security parameters. Moreover, the heuristic and approximation methods are compared to the effectiveness of solving real-life cases without to jeopardize the security. Both experimental and analytical results indicate that there are trade-offs between the computational feasibility and cryptographic strength. The results prove that although the precise solutions cannot be offered in large cases, the structured approximations and heuristics can offer the way to implement them that will be efficient, which supports the soundness and utility of NP-hardness in secure system design.
Keywords
Subject Classifications
References
[1] J. Abela, E. Cachia, and C. Layfield, “From P ≟ NP to practice: Description complexity and certificate-first algorithm discovery for hard problems,” Mathematics, vol. 14, no. 1, Art. no. 41 (2026), doi: 10.3390/math14010041.
[2] C. Caleiro and S. Marcelino, “Decidability preservation and complexity bounds for combined logics,” Mathematics, vol. 10, no. 19, Art. no. 3481 (2022), doi: 10.3390/math10193481.
[3] G. Lancia and P. Serafini, “Computational complexity and ILP models for pattern problems in the logical analysis of data,” Algorithms, vol. 14, no. 8, Art. no. 235 (2021), doi: 10.3390/a14080235.
[4] D. Ambrosino and C. Cerrone, “The cost-balanced path problem: A mathematical formulation and complexity analysis,” Mathematics, vol. 10, no. 5, Art. no. 804 (2022), doi: 10.3390/math10050804.
[5] A. A. Juan, M. Rabe, M. Ammouriova, J. Panadero, D. Peidro, and D. Riera, “Solving NP-hard challenges in logistics and transportation under general uncertainty scenarios using fuzzy simheuristics,” Algorithms, vol. 16, no. 12, Art. no. 570 (2023), doi: 10.3390/a16120570.
[6] R. Wang, B. Yuan, M. Yuan, and Y. Li, “NTRU-MCF: A chaos-enhanced multidimensional lattice signature scheme for post-quantum cryptography,” Sensors, vol. 25, no. 11, Art. no. 3423 (2025), doi: 10.3390/s25113423.
[7] U. Maleš, D. Ramljak, T. Jakšić Krüger, T. Davidović, D. Ostojić, and A. Haridas, “Controlling the difficulty of combinatorial optimization problems for fair proof-of-useful-work-based blockchain consensus protocol,” Symmetry, vol. 15, no. 1, Art. no. 140 (2023), doi: 10.3390/sym15010140.
[8] B. C. Tea, M. R. K. Ariffin, A. H. A. Ghafar, S. H. Sapar, and M. A. M. Johari, “An efficient identification scheme based on bivariate function hard problem,” Symmetry, vol. 14, no. 9, Art. no. 1784 (2022), doi: 10.3390/sym14091784.
[9] R. S. Kale, J. Hase, S. Deshmukh, S. N. Ajani, P. K. Agrawal, and C. S. Khandelwal, “Ensuring data confidentiality and integrity in edge computing environments: A security and privacy perspective,” J. Discrete Math. Sci. Cryptogr., vol. 27, no. 2-A, pp. 421–430 (2024), doi: 10.47974/JDMSC-1898.
[10] M. Richter, M. Bertram, J. Seidensticker, and A. Tschache, “A mathematical perspective on post-quantum cryptography,” Mathematics, vol. 10, no. 15, Art. no. 2579 (2022), doi: 10.3390/math10152579.
[11] P. Khobragade, P. K. Dhankar, P. K. Adakane, M. Dhone, S. A. Thakur, and P. Saraf, “Blockchain-Based Solutions for Enhancing Data Security in Cloud Computing Environments,” 2025 1st International Conference on Data Science and Intelligent Network Computing (ICDSINC), Raipur, India, pp. 599-604 (2025), doi: 10.1109/ICDSINC66221.2025.11448121.
[12] P. C. Golar, P. D. Shobhane, S. I. Baltabaevich, P. Karemore, S. Kedar, and P. Dubey, “Designing AI-driven information security protocols using discrete mathematical models,” J. Discrete Math. Sci. Cryptogr., vol. 29, no. 2-B, pp. 789–796 (2026), doi: 10.47974/JDMSC-2525.
[13] R. C. Poonia, T. Singh, C. K. Rajashri, D. Mondal, and S. M. Patil, “Optimizing communication system security through comprehensive testing and intelligent network configurations,” J. Inf. Optim. Sci., vol. 47, no. 5-A, pp. 1709–1717 (2026), doi: 10.47974/JIOS-2261.
