  This paper describes a constant-time lattice encoder for the National
Institute of Standards and Technology (NIST) recommended post-quantum
encryption algorithm: Kyber. The first main contribution of this paper is to
refine the analysis of Kyber decoding noise and prove that Kyber decoding noise
can be bounded by a sphere. This result shows that the Kyber encoding problem
is essentially a sphere packing in a hypercube. The original Kyber encoder uses
the integer lattice for sphere packing purposes, which is far from optimal. Our
second main contribution is to construct optimal lattice codes to ensure denser
packing and a lower decryption failure rate (DFR). Given the same ciphertext
size as the original Kyber, the proposed lattice encoder enjoys a larger
decoding radius, and is able to encode much more information bits. This way we
achieve a decrease of the communication cost by up to 32.6%, and a reduction of
the DFR by a factor of up to 2^{85}. Given the same plaintext size as the
original Kyber, 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.
