Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2401.15534 · IEEE International Symposium on Information Theory (ISIT)

CRYSTALS-Kyber With Lattice Quantizer

Shuiyin Liu, Amin Sakzad

Published Jul 7, 2024• 7 citations
arXivHTMLPDF

Abstract

Module Learning with Errors (M-LWE) based key reconciliation mechanisms (KRM) can be viewed as quantizing an M-LWE sample according to a lattice codebook. This paper describes a generic M-LWE-based KRM framework, valid for any dimensional lattices and any modulus$q$without a dither. Our main result is an explicit upper bound on the decryption failure rate (DFR) of M-LWE-based KRM. This bound allows us to construct optimal lattice quantizers to reduce the DFR and communication cost simultaneously. Moreover, we present a KRM scheme using the same security parameters$(q, k, \eta_{1}, \eta_{2})$as in Kyber. Compared with Kyber, the communication cost is reduced by up to 36.47% and the DFR is reduced by a factor of up to 299. The security arguments remain the same as Kyber.

DOI
10.1109/isit57864.2024.10619497

Related papers

Module-LWE-Based Key Exchange Protocol Using Error Reconciliation Mechanism

Wenjuan Jia, Guanhao Xue, Baocang Wang +1 more

Lattice-based key exchange protocols have attracted tremendous attention for its post-quantum security. In this work, we construct a Module-LWE-based key exchange protocol using Peikert’s error reconciliation mechanism. Compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 96-byte, i.e., 3.2% ∼ 6.1%, under the different parameter sets, and without reducing the post-quantum security levels. Moreover, our key exchange protocol slightly reduces the probability of session key agreement failure and the time consumed by modular multiplication of numbers and ring elements by approximately 30%. Thus, the key exchange protocol in this paper is more suitable for the lightweight communication systems.

Security and Communication Networks•Feb 1, 2022•2 citations

Error correction and reconciliation techniques for lattice-based key generation protocols

Charbel Saliba

In the last decade, there has been significant progress in the development of quantum computers, with massive investments by major tech companies. It is assumed that once large-scale quantum computers are built, many commonly used public key cryptosystems will no longer be secure. To prevent quantum attacks, researchers are already working on the design of post-quantum cryptographic protocols, and the US National Institute of Standards and Technology (NIST) is holding an international competition to select new cryptographic standards.Lattice-based cryptographic constructions are promising candidates because they offer strong theoretical security guarantees and can be implemented efficiently. One of the most widely used cryptographic primitives based on lattices is the Learning With Errors (LWE) problem introduced by Regev. Later works have proposed structured variants of LWE such as Ring-LWE and Module-LWE, which allow for a more compact representation.In this thesis, we consider two lattice-based NIST candidates for Key Encapsulation Mechanisms (KEMs) and propose new error correction and reconciliation techniques in order to improve their efficiency, their security, as well as their reliability.Unlike some previous works on error correction for lattice-based protocols, we provide rigorous error probability bounds.We first consider FrodoKEM, a lattice-based cryptosystem based on LWE, and introduce a modified error correction mechanism to improve its performance. Our encoder maps the secret key block-wise into a scaled version of the 8-dimensional Gosset lattice E_8. We propose three sets of parameters for our modified implementation. The first implementation outperforms FrodoKEM in terms of plausible security; the second allows to reduce the bandwidth by halving the modulus, and the third allows to increase key sizes.The second KEM we are considering is KyberKEM, which is based on Module-LWE. We propose a reconciliation technique using the lattice E_8, and show that our scheme can outperform KyberKEM in terms of security with comparable error probability and similar bandwidth requirements. We also investigate the use of higher dimensional lattices for reconciliation.

•May 24, 2022•0 citations

Wyner-Ziv reconciliation for key exchange based on Ring-LWE

Charbel Saliba, Laura Luzzi, Cong Ling

We consider a key encapsulation mechanism (KEM) based on Module-LWE where reconciliation is performed on the 8-dimensional lattice $E_8$, which admits a fast CVP algorithm. Our scheme generates 256 bits of key and requires 3 or 4 bits of reconciliation per dimension. We show that it can outperform Kyber in terms of the modulus q with comparable error probability. We prove that our protocol is IND-CPA secure and improves the security level of Kyber by 7.3%.

arXiv:2001.04280•Jan 12, 2020•0 citations

A reconciliation approach to key generation based on Module-LWE

Charbel Saliba, Laura Luzzi, Cong Ling

We consider a key encapsulation mechanism (KEM) based on Module-LWE where reconciliation is performed on the 8-dimensional lattice$E_{8}$, which admits a fast CVP algorithm. Our scheme generates 256 bits of key and requires 3 or 4 bits of reconciliation per dimension. We show that it can outperform Kyber in terms of the modulus$q$with comparable error probability and similar requirements in terms of bandwidth. We prove that our protocol is IND-CPA secure and improves the security level of Kyber by 7.3%.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•8 citations

Probabilistic modeling of decryption-failure bounds in CRYSTALS-Kyber under the post-quantum threat model

Cemil Emre Yavas, Lei Chen, Christopher Kadlec

Abstract We present a probabilistic modeling framework for quantifying decryption-failure probability (DFP) in CRYSTALS–Kyber , the lattice-based key encapsulation mechanism standardized by National Institute of Standards and Technology as module-lattice-based key-encapsulation mechanism. Our method combines exact tail computation of Kyber’s centered-binomial noise distribution using FFT-based convolution with principled comparisons to classical concentration inequalities such as Hoeffding and Bernstein. This hybrid analytical-computational approach yields implementation-independent upper bounds on DFP that are exponentially small in the security parameter. Specifically, we compute two-sided tails for aggregated noise variables, translate those into per-ciphertext failure probabilities through a transparent union bound, and determine the minimal reconciliation margins required to ensure DFP ⩽ 2 − λ for λ ∈ { 128 , 192 , 256 } . Across Kyber-like parameter regimes, Bernstein-type inequalities consistently overestimate risk compared to the exact probabilistic tails, which are several orders of magnitude smaller. The resulting gap highlights the conservatism of inequality-based analyses and clarifies the quantitative safety margins inherent to Kyber’s design. These findings contribute to the broader effort of modeling reliability in post-quantum cryptographic primitives using probabilistic and computational methodologies.

Machine Learning Science and Technology•Jan 29, 2026•0 citations

A Latticed-Based Public Key Encryption with KDM Security from R-LWE

Yan Fang Wu, Zheng Huang, Qiao Yan Wen

Since the introduction of the ring learning with errors (R-LWE) by Lyubashevsky, Peikert and Regev, many efficient and secure applications were founded in cryptography. In this paper, we mainly present an efficient public-key encryption scheme based on the R-LWE assumption. It is very simple to describe and analyze. As well as it can achieve security against certain key-dependent message (KDM) attacks. Namely, this efficient encryption scheme can securely encrypt its own secret key. The security of this scheme follows from the already proven hardness of the R-LWE problem since the R-LWE assumption is reducible to worst-case problems on the ideal lattice. Besides, the scheme enjoys a high level efficiency and low cost since the operations of the scheme are very simple and fast. The cost of both the encryption and decryption is only polylog(n) bit per message symbol.

Advanced engineering forum•Sep 1, 2012•0 citations
Module Learning with Errors (M-LWE) based key reconciliation mechanisms (KRM) can be viewed as quantizing an M-LWE sample according to a lattice codebook. This paper describes a generic M-LWE-based KRM framework, valid for any dimensional lattices and any modulusqqqwithout a dither. Our main result is an explicit upper bound on the decryption failure rate (DFR) of M-LWE-based KRM. This bound allows us to construct optimal lattice quantizers to reduce the DFR and communication cost simultaneously. Moreover, we present a KRM scheme using the same security parameters(q,k,η1,η2)(q, k, \eta_{1}, \eta_{2})(q,k,η1​,η2​)as in Kyber. Compared with Kyber, the communication cost is reduced by up to 36.47% and the DFR is reduced by a factor of up to 299. The security arguments remain the same as Kyber.
Lattice-based key exchange protocols have attracted tremendous attention for its post-quantum security. In this work, we construct a Module-LWE-based key exchange protocol using Peikert’s error reconciliation mechanism. Compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 96-byte, i.e., 3.2% ∼ 6.1%, under the different parameter sets, and without reducing the post-quantum security levels. Moreover, our key exchange protocol slightly reduces the probability of session key agreement failure and the time consumed by modular multiplication of numbers and ring elements by approximately 30%. Thus, the key exchange protocol in this paper is more suitable for the lightweight communication systems.
In the last decade, there has been significant progress in the development of quantum computers, with massive investments by major tech companies. It is assumed that once large-scale quantum computers are built, many commonly used public key cryptosystems will no longer be secure. To prevent quantum attacks, researchers are already working on the design of post-quantum cryptographic protocols, and the US National Institute of Standards and Technology (NIST) is holding an international competition to select new cryptographic standards.Lattice-based cryptographic constructions are promising candidates because they offer strong theoretical security guarantees and can be implemented efficiently. One of the most widely used cryptographic primitives based on lattices is the Learning With Errors (LWE) problem introduced by Regev. Later works have proposed structured variants of LWE such as Ring-LWE and Module-LWE, which allow for a more compact representation.In this thesis, we consider two lattice-based NIST candidates for Key Encapsulation Mechanisms (KEMs) and propose new error correction and reconciliation techniques in order to improve their efficiency, their security, as well as their reliability.Unlike some previous works on error correction for lattice-based protocols, we provide rigorous error probability bounds.We first consider FrodoKEM, a lattice-based cryptosystem based on LWE, and introduce a modified error correction mechanism to improve its performance. Our encoder maps the secret key block-wise into a scaled version of the 8-dimensional Gosset lattice E_8. We propose three sets of parameters for our modified implementation. The first implementation outperforms FrodoKEM in terms of plausible security; the second allows to reduce the bandwidth by halving the modulus, and the third allows to increase key sizes.The second KEM we are considering is KyberKEM, which is based on Module-LWE. We propose a reconciliation technique using the lattice E_8, and show that our scheme can outperform KyberKEM in terms of security with comparable error probability and similar bandwidth requirements. We also investigate the use of higher dimensional lattices for reconciliation.
We consider a key encapsulation mechanism (KEM) based on Module-LWE where reconciliation is performed on the 8-dimensional lattice E8E_8E8​, which admits a fast CVP algorithm. Our scheme generates 256 bits of key and requires 3 or 4 bits of reconciliation per dimension. We show that it can outperform Kyber in terms of the modulus q with comparable error probability. We prove that our protocol is IND-CPA secure and improves the security level of Kyber by 7.3%.
We consider a key encapsulation mechanism (KEM) based on Module-LWE where reconciliation is performed on the 8-dimensional latticeE8E_{8}E8​, which admits a fast CVP algorithm. Our scheme generates 256 bits of key and requires 3 or 4 bits of reconciliation per dimension. We show that it can outperform Kyber in terms of the modulusqqqwith comparable error probability and similar requirements in terms of bandwidth. We prove that our protocol is IND-CPA secure and improves the security level of Kyber by 7.3%.
Abstract We present a probabilistic modeling framework for quantifying decryption-failure probability (DFP) in CRYSTALS–Kyber , the lattice-based key encapsulation mechanism standardized by National Institute of Standards and Technology as module-lattice-based key-encapsulation mechanism. Our method combines exact tail computation of Kyber’s centered-binomial noise distribution using FFT-based convolution with principled comparisons to classical concentration inequalities such as Hoeffding and Bernstein. This hybrid analytical-computational approach yields implementation-independent upper bounds on DFP that are exponentially small in the security parameter. Specifically, we compute two-sided tails for aggregated noise variables, translate those into per-ciphertext failure probabilities through a transparent union bound, and determine the minimal reconciliation margins required to ensure DFP ⩽ 2 − λ for λ ∈ { 128 , 192 , 256 } . Across Kyber-like parameter regimes, Bernstein-type inequalities consistently overestimate risk compared to the exact probabilistic tails, which are several orders of magnitude smaller. The resulting gap highlights the conservatism of inequality-based analyses and clarifies the quantitative safety margins inherent to Kyber’s design. These findings contribute to the broader effort of modeling reliability in post-quantum cryptographic primitives using probabilistic and computational methodologies.
Since the introduction of the ring learning with errors (R-LWE) by Lyubashevsky, Peikert and Regev, many efficient and secure applications were founded in cryptography. In this paper, we mainly present an efficient public-key encryption scheme based on the R-LWE assumption. It is very simple to describe and analyze. As well as it can achieve security against certain key-dependent message (KDM) attacks. Namely, this efficient encryption scheme can securely encrypt its own secret key. The security of this scheme follows from the already proven hardness of the R-LWE problem since the R-LWE assumption is reducible to worst-case problems on the ideal lattice. Besides, the scheme enjoys a high level efficiency and low cost since the operations of the scheme are very simple and fast. The cost of both the encryption and decryption is only polylog(n) bit per message symbol.