D-HPPK KEM: A Defactorized Homomorphic Polynomial Public Key Encapsulation Mechanism for IND-CCA2 Security

Source abstract

We present the Defactorized Homomorphic Polynomial Public Key (D-HPPK) Encapsulation Mechanism, a post-quantum cryptosystem whose security reduces to searching over the ephemeral secret x in Fp. Classical secret recovery requires Θ(2l) field-element trials, with O(L2) bit operations per trial, yielding l+2log2L bits of classical security and l/2+log2L bits of quantum security. The scheme uses a three-layer architecture of additive random masking and hidden ring embeddings. Masking destroys exploitable factorisation structure, while hidden moduli S1,S2 and multipliers R1,R2 (all coprime to p) prevent adversaries from evaluating the cancellation condition in Fp. Key recovery requires O(p3) operations and is not the bottleneck. Under the Hidden Modulus Product Problem and uniform decryption assumptions, we prove the base PKE satisfies message-recovery security; a double-encryption consistency check yields IND-CCA2 security in the random oracle model. A unified parameter set (n=2,m=3,log2p=λ) ensures efficient, uniquely invertible decryption at NIST security levels. At Level V (λ=256), D-HPPK achieves a 1234-byte public key and 392-byte CCA2 ciphertext — 21% smaller public keys and 87% smaller ciphertexts than Kyber-1024 — with 8× faster encapsulation and 4× faster decapsulation in reference implementations, all without requiring SIMD or NTT acceleration. A single implementation scales across levels. D-HPPK demonstrates that polynomial-based cryptography can deliver rigorous security, compact footprints, and practical efficiency.