Paper 2019/1469

The Influence of LWE/RLWE Parameters on the Stochastic Dependence of Decryption Failures

Georg Maringer, Tim Fritzmann, and Johanna Sepúlveda


Learning with Errors (LWE) and Ring-LWE (RLWE) problems allow the construction of efficient key exchange and public-key encryption schemes. However, while improving the security through the use of error distributions with large standard deviations, the decryption failure rate increases as well. Currently, the independence of individual coefficient failures is assumed to estimate the overall decryption failure rate of many LWE/RLWE schemes. However, previous work has shown that this assumption is not correct. This assumption leads to wrong estimates of the decryption failure probability and consequently of the security level of the LWE/RLWE cryptosystem. An exploration of the influence of the LWE/RLWE parameters on the stochastic dependence among the coefficients is still missing. In this paper, we propose a method to analyze the stochastic dependence between decryption failures in LWE/RLWE cryptosystems. We present two main contributions. First, we use statistical methods to analyze the influence of fixing the norm of the error distribution on the stochastic dependence among decryption failures. The results have shown that fixing the norm of the error distribution indeed reduces the stochastic dependence of decryption failures. Therefore, the independence assumption gives a very close approximation to the true behavior of the cryptosystem. Second, we analyze and explore the influence of the LWE/RLWE parameters on the stochastic dependence. This exploration gives designers of LWE/RLWE based schemes the opportunity to compare different schemes with respect to the inaccuracy made by using the independence assumption. This work shows that the stochastic dependence depends on three LWE/RLWE parameters in different ways: i) it increases with higher lattice dimensions ($n$) and higher standard deviations of the error distribution ($\sqrt{k/2}$); and ii) it decreases with higher modulus ($q$).

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Lattice-based CryptographyStochastic DependenceCorrelationDecryption Failure Rate
Contact author(s)
tim fritzmann @ tum de
georg maringer @ tum de
2019-12-23: received
Short URL
Creative Commons Attribution


      author = {Georg Maringer and Tim Fritzmann and Johanna Sepúlveda},
      title = {The Influence of LWE/RLWE Parameters on the Stochastic Dependence of Decryption Failures},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1469},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.