Paper 2019/1148

On the Feasibility and Impact of Standardising Sparse-secret LWE Parameter Sets for Homomorphic Encryption

Benjamin R. Curtis and Rachel Player


In November 2018, the consortium published the Homomorphic Encryption Security Standard. The Standard recommends several sets of Learning with Errors (LWE) parameters that can be selected by application developers to achieve a target security level \( \lambda \in \{128,192,256\} \). These parameter sets all involve a power-of-two dimension \( n \leq 2^{15} \), an error distribution of standard deviation \( \sigma \approx 3.19 \), and a secret whose coefficients are either chosen uniformly in \( Z_q \), chosen according to the error distribution, or chosen uniformly in \( \{ -1, 0, 1\} \). These parameter sets do not necessarily reflect implementation choices in the most commonly used homomorphic encryption libraries. For example, several libraries support dimensions that are not a power of two. Moreover, all known implementations for bootstrapping for the CKKS, BFV and BGV schemes use a sparse secret and a large ring dimension such as \( n \in \{ 2^{16}, 2^{17} \} \), and advanced applications such as logistic regression have used equally large dimensions. This motivates the community to consider widening the recommended parameter sets, and the purpose of this paper is to investigate such possible extensions. We explore the security of possible sparse-secret LWE parameter sets, taking into account hybrid attacks, which are often the most competitive in the sparse-secret regime. We present a conservative analysis of the hybrid decoding and hybrid dual attacks for parameter sets of varying sparsity, with the goal of balancing security requirements with bootstrapping efficiency. We also show how the methodology in the Standard can be easily adapted to support parameter sets with power-of-two dimension \( n \geq 2^{16} \). We conclude with a number of discussion points to motivate future improvements to the Standard.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. 7th Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC'19)
CryptanalysisLearning with ErrorsHomomorphic EncryptionParameter SelectionBootstrapping
Contact author(s)
benjamin curtis 2015 @ rhul ac uk
2019-10-07: received
Short URL
Creative Commons Attribution


      author = {Benjamin R.  Curtis and Rachel Player},
      title = {On the Feasibility and Impact of Standardising Sparse-secret LWE Parameter Sets for Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1148},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.