A New Hard Problem for Post-Quantum Cryptography: Q-Problem Primitives

Mostefa Kara (), Mohammad Hammoudeh and Sultan Alamri
Additional contact information
Mostefa Kara: Interdisciplinary Research Center for Intelligent Secure Systems, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia
Mohammad Hammoudeh: Information and Computer Science Department, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia
Sultan Alamri: College of Computing and Informatics, Saudi Electronic University, Riyadh 11673, Saudi Arabia

Mathematics, 2025, vol. 13, issue 15, 1-15

Abstract: This article investigates the Q-Problem, a novel theoretical framework for post-quantum cryptography. It aims to redefine cryptographic hardness by moving away from problems with unique solutions toward problems that admit multiple indistinguishable preimages. This shift is motivated by the structural vulnerabilities that quantum algorithms may exploit in traditional formulations. To support this paradigm, we define new cryptographic primitives and security notions, including Q-Indistinguishability, Long-Term Secrecy, and a spectrum of Q-Secrecy levels. The methodology formalizes the Q-Problem as a system of expressions, called Q-expressions, that must satisfy a set of indistinguishability and reduction properties. We also propose a taxonomy of its models, including Connected/Disconnected, Totally/Partly, Fully/Partially Probabilistic, Perfect, and Ideal Q-Problem variants. These models illustrate the versatility across a range of cryptographic settings. By abstracting hardness through indistinguishability rather than solvability, Q-Problem offers a new direction for designing cryptographic protocols resilient to future quantum attacks. This foundational framework provides the foundations for long-term, composable, and structure-aware security in the quantum era.

Keywords: hard mathematical problem; Information security; perfect confidentiality; post-quantum techniques; Q-Problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/15/2410/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/15/2410/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:15:p:2410-:d:1710880

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().