Paper 2023/016

Simple Threshold (Fully Homomorphic) Encryption From LWE With Polynomial Modulus

Katharina Boudgoust, Aarhus University
Peter Scholl, Aarhus University

The learning with errors (LWE) assumption is a powerful tool for building encryption schemes with useful properties, such as plausible resistance to quantum computers, or support for homomorphic computations. Despite this, essentially the only method of achieving threshold decryption in schemes based on LWE requires a modulus that is superpolynomial in the security parameter, leading to a large overhead in ciphertext sizes and computation time. In this work, we propose a (fully homomorphic) encryption scheme that supports a simple $t$-out-of-$n$ threshold decryption protocol while allowing for a polynomial modulus. The main idea is to use the Rényi divergence (as opposed to the statistical distance as in previous works) as a measure of distribution closeness. This comes with some technical obstacles, due to the difficulty of using the Rényi divergence in decisional security notions such as standard semantic security. We overcome this by constructing a threshold scheme with a weaker notion of one-way security and then showing how to transform any one-way threshold scheme into one guaranteeing indistinguishability-based security.

Note: Update 06/2023: Strengthened the security notions for threshold fully homomorphic encryption schemes (Section 3), and hence updated security proof of our construction (Section 5). Further, updated concrete security (Section 6) by providing statistical attack. Update 09/2023: Revised version, mainly revised proof of one-way to indistinguishable security transformation for full-homomorphic treshold encryption (Section 4.2); now circuit privacy is needed.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
homomorphic encryptionthreshold cryptographylearning with errorsrenyi divergence
Contact author(s)
katharina boudgoust @ cs au dk
peter scholl @ cs au dk
2023-09-21: last of 2 revisions
2023-01-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Katharina Boudgoust and Peter Scholl},
      title = {Simple Threshold (Fully Homomorphic) Encryption From LWE With Polynomial Modulus},
      howpublished = {Cryptology ePrint Archive, Paper 2023/016},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.