Paper 2023/016

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

Katharina Boudgoust, Aarhus University

Peter Scholl, Aarhus University

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 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.