Threshold FHE with Efficient Asynchronous Decryption

Abstract

We present a Threshold Fully Homomorphic Encryption scheme enabling multiple parties, allowing any threshold of these parties to collaboratively decrypt a ciphertext without revealing their individual secret keys.

We identify three primary challenges with existing solutions: unrealistic network assumptions about party availability, super-linear overhead on FHE parameters, and computational demands from heavyweight Zero-Knowledge Proofs during decryption.

Our proposed scheme addresses these issues with: operation within an asynchronous communication model, a linear 3/4N + t additive overhead on the ciphertext modulus size, and an O(1) overhead option using non-Post Quantum additively homomorphic encryption. We introduce preprocessing techniques allowing parties to batch and preprocess necessary proofs offline.

The work builds on ring-based FHE schemes, specifically BGV, with applicability to BFV, CKKS, and TFHE schemes.