Paper 2025/409

Low Communication Threshold FHE from Standard (Module-)LWE

Abstract

Threshold fully homomorphic encryption (ThFHE) is a multi-party extension of FHE; any subset of at least $T$ out of $N$ parties can decrypt the ciphertexts by combining their decryption shares. Recently, Passelègue and Stehlé (Asiacrypt 2024) presented a ThFHE scheme with polynomially short decryption shares from the ``known-norm'' variant of learning with errors (LWE) assumption, in which the norm of the secret key is leaked to the adversary. While known-norm LWE is reduced from standard LWE, its module extension, known-covariance module-LWE (MLWE), lacks a known reduction from standard MLWE. Hence, extending their ThFHE scheme to the MLWE-based construction remains an open question. In this paper, we address this open problem: We construct a ThFHE scheme with polynomially small decryption shares from standard LWE/MLWE. Our core technique, which we call noise padding, eliminates the need of known-norm variants of LWE. We distribute shares of a padding noise and use them to adjust the distribution of decryption noise so that no information about the secret key is leaked. Furthermore, our ThFHE efficiently realizes arbitrary $T$-out-of-$N$ threshold decryption via simple Shamir secret sharing instead of $\{0,1\}$-linear secret sharing. Hence, the sizes of the keys, ciphertexts and decryption shares in our scheme are compact: they are $O(1)$ w.r.t. the number of parties $N$.