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^-281 and CER =4.6, i.e., a decrease of CER by 90% compared to KYBER1024. If minimizing CPU runtime is the priority, our C implementation shows that the E8 encoder provides the best trade-off among runtime, CER, and DFR. Additionally, for a fixed plaintext size matching that of standard Kyber (256 bits), we introduce a truncated variant of P_ℓ-Kyber that deterministically removes ciphertext components carrying surplus information bits. Using ℓ=8 and E8 lattice encoder, we show that the proposed truncated coded P_ℓ-KYBER1024 achieves a 10.2% reduction in CER and improves DFR by a factor of 2³⁰ relative to KYBER1024. Finally, we demonstrate that constructing a multi-recipient PKE and a multi-recipient KEM (mKEM) using the proposed truncated coded P_ℓ-KYBER1024 results in a 20% reduction in bandwidth consumption compared to the existing schemes.