<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1640_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">$32.6\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>32.6</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation>, and a reduction of the DFR by a factor of up to <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1640_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{85}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>85</mn> </msup> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1640_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">$24.49\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>24.49</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation>, while the DFR is decreased by a factor of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1640_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$2^{39}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mn>39</mn> </msup> </math></EquationSource> </InlineEquation>. The proposed encoding scheme is a constant-time algorithm, thus resistant against the timing side-channel attacks.</p>

Lattice codes for CRYSTALS-Kyber

期刊论文
发表日期：

2025年5月1日

查看全文

Shuiyin Liu,
Amin Sakzad

摘要

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\%$ $32.6 %$ , and a reduction of the DFR by a factor of up to $2^{85}$ $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\%$ $24.49 %$ , while the DFR is decreased by a factor of $2^{39}$ $2^{39}$ . The proposed encoding scheme is a constant-time algorithm, thus resistant against the timing side-channel attacks.