Quantum-Resistant One-Way Puzzles from Program Obfuscation and Kolmogorov Complexity: A Minimal-Assumption Framework
Maher Asaad Baker, Fuad Al-Qrize · 2025
We introduce a novel construction of quantum-resistant one-way puzzles based on the uncomputability of Kolmogorov complexity and the obfuscation of pseudorandom generators. The security of our scheme relies on the minimal assumption that quantum polynomial-time (QPT) adversaries cannot efficiently approximate the Kolmogorov complexity 𝑲(𝒔) of strings sampled from specific distributions. We define a new cryptographic primitive-Kolmogorov puzzles-and formally prove that inversion implies a nontrivial compression of random strings, contradicting the Incompressibility Lemma. To support this, we provide a theoretical security reduction and simulation-based evidence. Compression algorithms (e.g., gzip) serve as heuristic estimators of 𝑲(𝒔), and Grover-based quantum circuits implemented in Qiskit validate the infeasibility of brute-force inversion. While our obfuscation uses lightweight heuristics, the reduction remains valid under any black-box obfuscator. This work offers a complexity-theoretic approach to post-quantum cryptography without algebraic assumptions, aligning with NIST's call for diverse post-quantum primitives.