Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations
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, ther...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2025-06-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/12213 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849467306456907776 |
|---|---|
| author | Thales B. Paiva Marcos A. Simplicio Jr Syed Mahbub Hafiz Bahattin Yildiz Eduardo L. Cominetti Henrique S. Ogawa |
| author_facet | Thales B. Paiva Marcos A. Simplicio Jr Syed Mahbub Hafiz Bahattin Yildiz Eduardo L. Cominetti Henrique S. Ogawa |
| author_sort | Thales B. Paiva |
| collection | DOAJ |
| description |
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.
|
| format | Article |
| id | doaj-art-b4e21ecd0c024e02b36e53d41053e69e |
| institution | Kabale University |
| issn | 2569-2925 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj-art-b4e21ecd0c024e02b36e53d41053e69e2025-08-20T03:26:16ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252025-06-012025310.46586/tches.v2025.i3.139-163Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiationsThales B. Paiva0Marcos A. Simplicio Jr1Syed Mahbub Hafiz2Bahattin Yildiz3Eduardo L. Cominetti4Henrique S. Ogawa5Future Security Team, LG Electronics, Santa Clara, USAFuture Security Team, LG Electronics, Santa Clara, USA; Universidade de São Paulo, São Paulo, BrazilFuture Security Team, LG Electronics, Santa Clara, USAFuture Security Team, LG Electronics, Santa Clara, USAFuture Security Team, LG Electronics, Santa Clara, USAFuture Security Team, LG Electronics, Santa Clara, USA 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. https://tches.iacr.org/index.php/TCHES/article/view/12213PQCML-KEMError correction codesCiphertext compression |
| spellingShingle | Thales B. Paiva Marcos A. Simplicio Jr Syed Mahbub Hafiz Bahattin Yildiz Eduardo L. Cominetti Henrique S. Ogawa Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations Transactions on Cryptographic Hardware and Embedded Systems PQC ML-KEM Error correction codes Ciphertext compression |
| title | Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations |
| title_full | Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations |
| title_fullStr | Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations |
| title_full_unstemmed | Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations |
| title_short | Tailorable codes for lattice-based KEMs with applications to compact ML-KEM instantiations |
| title_sort | tailorable codes for lattice based kems with applications to compact ml kem instantiations |
| topic | PQC ML-KEM Error correction codes Ciphertext compression |
| url | https://tches.iacr.org/index.php/TCHES/article/view/12213 |
| work_keys_str_mv | AT thalesbpaiva tailorablecodesforlatticebasedkemswithapplicationstocompactmlkeminstantiations AT marcosasimpliciojr tailorablecodesforlatticebasedkemswithapplicationstocompactmlkeminstantiations AT syedmahbubhafiz tailorablecodesforlatticebasedkemswithapplicationstocompactmlkeminstantiations AT bahattinyildiz tailorablecodesforlatticebasedkemswithapplicationstocompactmlkeminstantiations AT eduardolcominetti tailorablecodesforlatticebasedkemswithapplicationstocompactmlkeminstantiations AT henriquesogawa tailorablecodesforlatticebasedkemswithapplicationstocompactmlkeminstantiations |