Paper 2026/957

Threshold FHE with Short Decryption Shares without a Semi-trusted Server

Tsuyoshi Takagi, University of Tokyo

Abstract

Threshold fully homomorphic encryption (ThFHE) enables decryption by collecting decryption shares from any T-out-of-N parties. A major drawback of previous ThFHE schemes is that they require a super-polynomial modulus (or are subject to other limitations), resulting in long ciphertexts, keys, and decryption shares. Passel`egue and Stehl´e (Asiacrypt 2024) proposed a ThFHE scheme in which a semi-trusted server rounds the input ciphertexts to produce polynomially short ciphertexts and sends them to the parties, thereby making the rest of the decryption process efficient. Although the input ciphertexts are still super-polynomially large, the communication cost of sending them from the parties to the server can be reduced to polynomial size via the transciphering technique; as a result, an entirely low-communication ThFHE is achieved. However, if even a single party colludes with the server (contrary to the assumption), the secret key can be efficiently recovered. Such a risky scenario would be unsuitable for practical deployment. In this paper, we tackle this issue. We propose two serverless ThFHE schemes with polynomially short decryption shares. The core idea is to let the parties directly round the decryption shares, rather than rely on the semi-trusted server to round the ciphertexts. We can also achieve low-communication ThFHE by reducing the communication required to send input ciphertexts to the parties to polynomial size via transciphering. Our first scheme, based on binary coefficient linear secret sharing ({0,1}-LSS), strictly improves upon Boneh et al. (CRYPTO 2018), achieving short decryption shares without any trade-offs. Our second scheme, based on Shamir secret sharing, adapts the technique of Okada and Takagi (Asiacrypt 2025) to eliminate the $O(N^{4.3})$ overhead in share size of our first scheme, further reducing communication costs.