Paper 2025/1467

Optimized HPPK Cryptography for Post-Quantum Security

Abstract

In this paper, we present an optimized construction of the Homomorphic Polynomial Public Key (HPPK) cryptosystem, a novel framework designed to provide enhanced security and efficiency in the post-quantum era. Our work introduces a layered cryptographic design that combines modular arithmetic permutations with an innovative additive random masking technique. This approach effectively obscures the underlying factorizable structure of the public key, thereby mitigating vulnerabilities to known lattice reduction attacks and other algebraic cryptanalyses. The security of our scheme is formally grounded in the computational hardness of three new problems: the Hidden Modulus Product Problem (HMPP), the HPPK Key Recovery Problem (HKRP), and the HPPK Secret Recovery Problem (HSRP). We demonstrate through rigorous analysis that the optimal attacks on our scheme are computationally infeasible for appropriately chosen parameters. Furthermore, we show that HPPK achieves remarkably compact key, ciphertext, and signature sizes, offering a significant advantage over leading NIST post-quantum finalists such as Kyber, Dilithium, and Falcon, particularly in bandwidth-constrained environments. The HPPK cryptosystem offers a compelling and mathematically-grounded solution for next-generation cryptography, delivering both provable security and practical efficiency.

Note: This work builds upon prior foundational research on HPPK published in [KP23] and KPSL24], by enhancing security of KEM and DS schemes.