Paper 2024/1243

Tailoring two-dimensional codes for structured lattice-based KEMs and applications to Kyber

Abstract

Kyber is a post-quantum lattice-based key encapsulation mechanism (KEM) selected by NIST for standardization as ML-KEM. The scheme is designed to ensure that the unintentional errors accumulated during decryption do not prevent the receiver to correctly recover the encapsulated key. This is done by using a simple error-correction code independently applied to each bit of the message, for which it is possible to show that the decryption failure rate (DFR) is negligible. Although there have been other proposals of more complex error-correction codes for Kyber, these have important limitations. Some proposals use independence assumptions on the noise distribution that do not hold. Others require significant changes in Kyber's core parameters, which make them unpractical. In this work, we propose a family of 2-dimensional codes that can, in principle, be applied to any lattice-based scheme. Even though our 2D codes have a rather simple construction, they can be tailored for the specific noise distribution observed for different Kyber parameters, and reduce Kyber's DFR by factors of $2^{4.8}$, $2^{5.4}$, and $2^{9.9}$, for security levels 1, 3, and 5, respectively, without requiring independence assumptions. Alternatively, the proposed codes allow for up to $6\%$ ciphertext compression in Kyber Level 5 while maintaining the DFR lower than $2^{-160}$, which is the target value defined in Kyber's specification. Furthermore, we provide an efficient isochronous implementation of the encoding and decoding procedures for our 2D codes. Compared with Kyber's reference implementation, the performance impact of the 2D codes in the decapsulation time is negligible (namely, between $0.08\%$ to $0.18\%$, depending on the security level).