SAPOW-KEM: A Lattice-Based Proof-of-Work Key Encapsulation Mechanism.

SAPOW-KEM is a post-quantum Key Encapsulation Mechanism (KEM) that natively embeds a lattice-based proof-of-work (PoW) puzzle inside the Fujisaki–Okamoto encapsulation path. Unlike prior approaches that treat PoW as an external layer with no cryptographic binding to the key exchange, SAPOW-KEM folds the puzzle solution directly into the derivation of the KEM encapsulation coins, eliminating cross-session, cross-key, and cross-difficulty replay attacks by construction. Construction. Three components are combined: (1) the Module-LWE KEM core underlying ML-KEM-768 (FIPS 203), with modulus \(q = 3329\), degree \(n = 256\), rank \(k = 3\); (2) a bounded inhomogeneous Module-SIS puzzle requiring the client to find \(zpow ∈ R_q^{mpow}\) satisfying \[Apow\,zpow = t {q}, \|zpow\|_2 ≤ β = 512,\] together with a challenge-linked difficulty filter requiring \(d\) leading zero bits in \(Hdiff(zpow)\); and (3) the \(FO⊥\) implicit-rejection transform of Hofheinz–Hövelmanns–Kiltz. Full-context binding. The encapsulation coin seed is derived as \[ρ ← G\!(0x01 \,\|\, Encode(pk) \,\|\, Encode(t) \,\|\, ν \,\|\, Encode(d) \,\|\, m \,\|\, Encode(zpow)),\] binding the PoW solution irreversibly to the session, key, and difficulty level. Security result. Under the DFMS'22 QROM framework the IND-CCA2 advantage satisfies \[Adv^{{IND-CCA2}}_{ΠSAPOW}(A) \;≤\; AdvMLWE \;+\; {4\,QFO}{2_m/2} \;+\; q_D · γ \;+\; q_D · δfail⁽¹⁾.\] For \(QFO ≤ 2³³\) and \(_m = 256\), the dominant term is \(2⁻⁹³\), giving an effective security level of approximately 93 bits. The PoW layer introduces no additional term into this bound. The underlying Module-LWE and Module-SIS problems independently reach the 128-bit post-quantum level; the gap to 93 bits reflects known looseness of FO-style reductions in the QROM. DDoS resistance. The seven-step verification pipeline defers all secret-key operations to the last step. Amortization resistance follows from the challenge-linked filter: for any fresh nonce \(ν\) and any previously computed short vector \(z\), \[ν\![Hdiff(0x06\,\|\,ν\,\|\,Encode(z)) passes] = 2⁻ᵈ.\] Server throughput against all attack classes exceeds \(10^6\) requests per second.