HMM: A Decryption-Failure-Free Hybrid KEM from Module-LWE and MQ Problems

Reference No.	2026a023
Type/Category	Grant for Young Researchers and Students- Short-term Visiting Researcher
Title of Research Project	HMM: A Decryption-Failure-Free Hybrid KEM from Module-LWE and MQ Problems
Principal Investigator	Takuya Moriwaki（The University of Electro-Communications, Cluster II, Security Information Program Title: Undergraduate Student・University student）
Research Period	August 10,2026. - August 17,2026.
Keyword(s) of Research Fields	Post-Quantum Cryptography, Lattice-based Cryptography, Multivariate Public-Key Cryptography, Module-LWE Problem, MQ Problem, Fujisaki-Okamoto Transform
Abstract for Research Report	In today’s information society, migration to post-quantum cryptography (PQC) has become an urgent issue. Although NIST has standardized schemes such as CRYSTALS-Kyber, the existence of decryption failures in lattice-based cryptography still raises practical concerns, including increased implementation complexity and potential vulnerability to side-channel attacks. To address this issue, the applicant has already proposed a decryption-failure-free hybrid cryptographic scheme called HMM, which combines the Module-LWE problem and the MQ problem. The objective of this collaborative research is to address two remaining challenges of HMM: a rigorous security evaluation of its MQ-related structure and optimization of its implementation performance. Specifically, this project will focus on: (i) parameter adjustment based on algorithmic optimization to reduce computational cost; (ii) refinement of the security evaluation, especially the clarification of attack models and hardness estimation for the MQ-type structure arising from public-key generation; and (iii) establishment of a high-speed implementation strategy using techniques such as the Number Theoretic Transform (NTT). Since the public key of HMM has an MQ-related structure, evaluation methods developed solely for conventional lattice-based cryptography are not sufficient, and resistance against algebraic attacks must be carefully assessed. Therefore, this research will conduct a security analysis based on algebraic cryptanalytic methods and examine the validity of the corresponding evaluation procedures. More concretely, the design concerning the reduction of the modulus qqq will be reconsidered within the range that preserves both decryption correctness and security, in order to improve computational and communication efficiency. In addition, assuming algebraic attacks such as Gröbner basis methods and the XL method, we will analyze the structure of the polynomial systems appearing in HMM and verify the appropriateness of existing estimation procedures. Based on these results, we will further reselect the modulus qqq for key-size reduction and establish a fast implementation method using NTT. The expected outcomes of this research are: (1) establishment of a concrete and reliable security evaluation against algebraic attacks; (2) derivation of an optimal parameter set that balances security and efficiency while suppressing computational cost; and (3) development of a high-speed implementation of HMM. Through these efforts, we expect to demonstrate the reliability of HMM and contribute to the practical realization of post-quantum cryptography.
Organizing Committee Members (Workshop) Participants (Short-term Joint Usage)	Takuya Moriwaki（The University of Electro-Communications, Cluster II, Security Information Program Title: Undergraduate Student・University student） Yuntao Wang（Graduate School of Informatics and Engineering, Department of Informatics, Information Security Engineering Program, The University of Electro-Communications・Associate Professor）