Paper 2024/1979

On the Security of LWE-based KEMs under Various Distributions: A Case Study of Kyber

Abstract

Evaluating the security of LWE-based KEMs involves two crucial metrics: the hardness of the underlying LWE problem and resistance to decryption failure attacks, both significantly influenced by the secret key and error distributions. To mitigate the complexity and timing vulnerabilities of Gaussian sampling, modern LWE-based schemes often adopt either the uniform or centered binomial distribution (CBD). This work focuses on Kyber to evaluate its security under both distributions. Compared with the CBD, the uniform distribution over the same range enhances the LWE hardness but also increases the decryption failure probability, amplifying the risk of decryption failure attacks. We introduce a majority-voting-based key recovery method, and carry out a practical decryption failure attack on Kyber512 in this scenario with a complexity of $2^{37}$. Building on this analysis, we propose uKyber, a variant of Kyber that employs the uniform distribution and parameter adjustments under the asymmetric module-LWE assumption. Compared with Kyber, uKyber maintains comparable hardness and decryption failure probability while reducing ciphertext sizes. Furthermore, we propose a multi-value sampling technique to enhance the efficiency of rejection sampling under the uniform distribution. These properties make uKyber a practical and efficient alternative to Kyber for a wide range of cryptographic applications.