SAPOW-KEM: Post-Quantum Proof-of-Work Key Encapsulation Mechanism for DDoS-Resilient Authentication

We present SAPOW-KEM, a new Key Encapsulation Mechanism that tightly integrates a proof-of-work (PoW) primitive with public-key encapsulation to provide a costed, verifiable client work factor while preserving strong cryptographic guarantees. SAPOW-KEM uses Module-LWE for the encapsulation primitive and a Module-SIS–based PoW; the PoW output is folded into the encapsulation randomness (via a deterministic function ($r = G(m \parallel z_{pow}))$), making the PoW an intrinsic part of the security reduction rather than an external add-on. Key contributions include a formal IND-CCA2 security proof carried out in the Quantum Random Oracle Model (QROM), an analysis that accounts for entropy loss from oracle queries, and concrete parameter guidance for achieving 128-bit security. On the engineering side, we provide a constant-time reference implementation, an adaptive difficulty controller (exponential moving average), test vectors, and performance measurements. We also discuss operational considerations for deployment (re-keying and query limits), potential constraints on low-resource devices, and avenues for hardware resistance testing.