Paper 2025/2143

New Post-Quantum IBE leveraging maturity, efficiency and security of standard schemes

Abstract

Many Identity-Based Encryption (IBE) schemes rely on the hardness of the Discrete Logarithm Problem, making them vulnerable to quantum attacks like Shor's algorithm. In recent years, lattice-based cryptography has emerged as a source of Post-Quantum cryptosystems, for example with Kyber, Dilithium and Falcon chosen by NIST to be standardized as ML-KEM, ML-DSA and FN-DSA. In the meantime, some IBEs have also been proposed over lattices. However, they can still be considered as interesting theoretical constructions, the community's attention having been more on the NIST competition than on optimizing IBEs, assessing their security, and protecting them against physical attacks. So, in this paper, we build a new IBE scheme from the highly studied ML-KEM, ML-DSA and ModFalcon. More precisely, we leverage the Module-NTRU trapdoor from ModFalcon to enable extraction of secret keys, we use the encryption and decryption algorithms from ML-KEM, and the modular arithmetic and Number-Theoretic Transform from ML-DSA. Therefore, being able to reuse some of their code, our scheme is easy to implement, and can benefit from existing and future and side-channel protections. In this paper, we also prove the IND-sID-CPA-security of our scheme under the Ring-LWE and Module-NTRU assumptions, and we precisely describe the choice of appropriate parameters. As a work that can be of independent interest, we also provide an efficient estimator for the decryption failure probability of a LWE-based scheme, which allows us to concretely check the negligible failure probability of our scheme, at a standard security level.