Lattice Codes for CRYSTALS-Kyber

This paper describes a constant-time lattice encoder for the NIST-recommended post-quantum encryption algorithm: Kyber. We first refine the analysis of Kyber decoding noise and prove that Kyber decoding noise can be bounded by a sphere. This shows the Kyber encoding problem is essentially a sphere packing in a hypercube. Lattice codes are then constructed to ensure denser packing and a lower decryption failure rate (DFR). For a fixed ciphertext size, the proposed lattice encoder reduces the communication cost by up to 32.6%, and decreases the DFR by a factor of up to 2^{85}. For a fixed plaintext size, e.g., 256 bits, we propose a bit-interleaved coded modulation (BICM) approach, which combines a BCH code and the proposed lattice encoder. The proposed BICM scheme significantly reduces the DFR of Kyber, thus enabling further compression of the ciphertext. Compared with the original Kyber encoder, the communication cost is reduced by 24.49%, while the DFR is decreased by a factor of 2^{39}. The proposed encoding scheme is a constant-time algorithm, thus resistant against the timing side-channel attacks.