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

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ègue and Stehlé (Asiacrypt 2024) proposed a ThFHE scheme in which a semi-trusted server rounds the input ciphertexts to produce polynomially short ciphertexts and send them to the parties, thereby making the rest of the decryption process efficient. Although the input ciphertexts are still super-polynomial size, the communication cost of sending them to the server (from, e.g., the parties) can be reduced to polynomially small via the transciphering technique; as a result, a totally 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 size of sending input ciphertexts to the parties to be polynomially small 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.