CryptoDB
Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Compared to elliptic curve cryptography, a primary drawback of latticebased schemes is the larger size of their public keys and ciphertexts. A common procedure for compressing these objects consists essentially of dropping some of their least significant bits. Albeit effective for compression, there is a limit to the number of bits to be dropped before we get a noticeable decryption failure rate (DFR), which is a security concern. To address this issue, this paper presents a family of error-correction codes that, by allowing an increased number of dropped bits while preserving a negligible DFR, can be used for both ciphertext and publickey compression in modern lattice-based schemes. To showcase the impact and practicality of our proposal, we use the highly optimized ML-KEM, a post-quantum lattice-based scheme recently standardized by NIST. We provide detailed procedures for tailoring our codes to ML-KEM’s specific noise distributions, and show how to analyze the DFR without independence assumptions on the noise coefficients. Among our results, we achieve between 4% and 8% ciphertext compression for MLKEM. Alternatively, we obtain 8% shorter public keys compared to the current standard. We also present isochronous implementations of the decoding procedure, achieving negligible performance impact in the full ML-KEM decapsulation even when considering optimized implementations for AVX2, Cortex-M4, and Cortex-A53. |
BibTeX
@article{tches-2025-35775,
title={Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations},
journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
publisher={Ruhr-Universität Bochum},
volume={2025},
pages={139-163},
url={https://tches.iacr.org/index.php/TCHES/article/view/12213},
doi={10.46586/tches.v2025.i3.139-163},
author={Thales B. Paiva and Marcos A. Simplicio Jr and Syed Mahbub Hafiz and Bahattin Yildiz and Eduardo L. Cominetti and Henrique S. Ogawa},
year=2025
}