Frozen Core Isolation and Quantum-Resistant Cryptographic Commitments from Planted k-SAT

Abstract

We prove that for planted k-SAT instances with k >= 7 at clause density alpha/alpha_s >= 0.21, a positive fraction of variables are frozen directly in the planted model---without requiring transfer from the random model via quiet planting. The expected number of "support clauses" per variable (clauses in which that variable is the unique satisfying literal) exceeds 1 at remarkably low density: alpha/alpha_s ~ 0.20 for k = 7, compared to the random-model freezing threshold at alpha_f/alpha_s ~ 0.90. We prove that the resulting frozen-core structure implies topological disconnection of the solution subgraph across cluster boundaries, with a cycle-robustness argument showing that short cycles in the factor graph cannot quench the supercritical repair cascade. As an immediate corollary, the Hilbert space spanned by satisfying assignments decomposes into orthogonal sectors preserved by any unitary generated by the adjacency matrix---blocking quantum walks, QAOA at all depths, and quantum annealing. We construct a post-quantum commitment scheme whose binding property reduces to the hardness of solving planted k-SAT, provide formal proofs of completeness, soundness, and zero-knowledge, and derive a digital signature scheme with existential unforgeability via the Fiat-Shamir transform. We present a six-vector quantum attack analysis with proved barriers against five algorithmic families. We give concrete parameter recommendations at NIST security levels 1, 3, and 5, and position the scheme within the landscape of SAT-based and CSP-based cryptographic constructions. We prove that the Grover query complexity for breaking the binding property is Omega(2^{fn/2}); empirical cryptanalysis of Glucose and MiniSat CDCL solvers on our exact distribution yields a classical attack cost of 2^{0.234n} operations, enabling concrete parameter selection at NIST security levels 1, 3, and 5. Empirical validation across 100 random seeds at n = 16 confirms complete cluster isolation at every instance tested.