Paper 2023/016

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

Abstract

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 (fully homomorphic) threshold scheme into one guaranteeing (selective) 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. Update 07/2024: Fixed another issue with the one-way to indistinguishable security transformation for full-homomorphic treshold encryption (Section 4.2); now only selective security (as opposed to adaptive security) is achieved; added a changelog (Section 1.3).