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

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.