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 \ (z₏₎ₖ Rq^m₏₎ₖ\) satisfying ₏₎ₖ\, z₏₎ₖ = t q, \|z₏₎ₖ\|₂ = 512, \ together with a challenge-linked difficulty filter requiring \ (d\) leading zero bits in \ (H₃₈₅₅ (z₏₎ₖ) \) ; 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 (z₏₎ₖ) ), \ 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 ^IND-CCA2_ₒ₀₏₎ₖ (A) \;\; Adv₌₋ₖ₄ \;+\; 4\, Q₅₎2^{ₘ/2} \;+\; qD \;+\; qD ₅₀₈₋^ (1). \ For \ (Q₅₎ 2^33\) and \ (ₘ = 256\), the dominant term is \ (2^-93\), 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\), \_\![H₃₈₅₅ (0x06\, \|\, \, \|\, Encode (z) ) passes = 2^-d. \] Server throughput against all attack classes exceeds \ (10⁶\) requests per second.