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

We present the Defactorized Homomorphic Polynomial Public Key (D-HPPK) Encapsulation Mechanism, a post-quantum KEM whose security rests on exhaustive-search problems with efficient verification for both attack paths. We adopt the NIST search-based convention, under which a primitive is assigned security level l when the adversary’s best-known attack requires exhaustive search over 2l candidates with efficient verification, exactly as AES-128, AES-192, and AES-256 are assigned NIST Levels I, III, and V. For D-HPPK, both attack paths—long-term key recovery and ephemeral-secret recovery—are exhaustive searches over spaces of size 2l with polynomial-time verification. The long-term key-recovery path reduces to the Hidden Modulus Product Problem (HMPP), and the ephemeral-secret recovery path reduces to the scheme-induced Message Recovery Problem (MRP). The scheme uses a three-layer architecture of additive random masking and hidden-ring embeddings. The hidden-ring moduli and multipliers block the public-constraint attack; the random masking destroys the rank-2 algebraic regularity of the unmasked coefficient matrices, forcing the adversary into HMPP. Both attack paths have best-known classical cost O(2l·poly(L)). The IND-CCA2 proof uses a double-encryption consistency check with a five-class rejection set, together with a small number of explicitly stated hardness assumptions; the adaptive form of the decryption-collision property is derived through Structured D-HMPP. A unified parameter set (n=2,m=3,l=⌈log2p⌉) supports a single implementation across security levels. At Level V (l=256), D-HPPK achieves a 1234-byte public key and a 392-byte CCA2 ciphertext—21% smaller public keys and 75% smaller ciphertexts than ML-KEM-1024—without SIMD or NTT acceleration.