Compact Lattice-Coded (Multi-Recipient) Kyber without CLT Independence Assumption

This work presents a joint design of encoding and encryption procedures for public key encryptions (PKEs) and key encapsulation mechanism (KEMs) such as Kyber, without relying on the assumption of independent decoding noise components, achieving reductions in both communication overhead (CER) and decryption failure rate (DFR). Our design features two techniques: ciphertext packing and lattice packing. First, we extend the Peikert-Vaikuntanathan-Waters (PVW) method to Kyber: plaintexts are packed into a single ciphertext. This scheme is referred to as P_-Kyber. We prove that the P_-Kyber is IND-CCA secure under the M-LWE hardness assumption. We show that the decryption decoding noise entries across the plaintexts (also known as layers) are mutually independent. Second, we propose a cross-layer lattice encoding scheme for the P_-Kyber, where every cross-layer information symbols are encoded to a lattice point. This way we obtain a coded P_-Kyber, where the decoding noise entries for each lattice point are mutually independent. Therefore, the DFR analysis does not require the assumption of independence among the decryption decoding noise entries. Both DFR and CER are greatly decreased thanks to ciphertext packing and lattice packing. We demonstrate that with =24 and Leech lattice encoder, the proposed coded P_-KYBER1024 achieves DFR <2⁻²⁸¹ and CER $ = 4.6$, i.e., a decrease of CER by $90%$ compared to KYBER1024.