International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Katharina Boudgoust , Aarhus University, Denmark
Peter Scholl , Aarhus University, Denmark
Search ePrint
Search Google
Conference: ASIACRYPT 2023
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 indistinguishability-based security.
  title={Simple Threshold (Fully Homomorphic) Encryption From LWE With Polynomial Modulus},
  author={Katharina Boudgoust and Peter Scholl},