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

Source abstract

We present the \textbf{Defactorized Homomorphic Polynomial Public Key (D-HPPK)} Encapsulation Mechanism, a post-quantum cryptosystem based on two hardness assumptions: the \textbf{Hidden Modulus Product Problem (HMPP)} and a scheme-induced \textbf{Modular Multivariate Polynomial System (MMPS)}. The best-known attacks on both problems are exhaustive search over spaces of size 2l, directly analogous to the AES key search that defines the NIST security categories. The scheme therefore targets NIST Levels~I, III, and~V at l=128,192,256, respectively. The scheme uses a three-layer architecture of additive random masking and hidden-ring embeddings. The hidden-ring moduli S1,S2 and multipliers R1,R2 prevent evaluation of the cancellation condition in Fp, blocking the public-constraint attack; the random masking destroys the rank-2 algebraic regularity of the unmasked coefficient matrices, forcing the adversary into HMPP. Both key recovery and ephemeral-secret recovery have classical cost O(2l⋅poly⁡(L)), so the scheme's security rests on both HMPP and MMPS being hard. Under these assumptions plus two adversarial-decryption safety assumptions, we show that the base PKE's message-recovery security reduces to MMPS, and that a double-encryption consistency check yields IND-CCA2 security in the classical random oracle model, via a union bound over both attack paths and the standard random-oracle loss. A unified parameter set (n=2, m=3, ⌈log2⁡p⌉=l) ensures efficient decryption across security levels, with a single implementation that adjusts only the bit-length of p. 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 requiring SIMD or NTT acceleration. D-HPPK demonstrates that polynomial-based cryptography can deliver compact footprints, a simple algorithmic structure, and practical efficiency.