# Verifiable Threshold Multi-Party Fully Homomorphic Encryption from Share Resharing
## 1 Introduction
### Related Work  
[PERSON] and [PERSON] [22] considered a setting where parties obtain secret shares via pseudo-random secret sharing techniques, and provided a threshold variant of a CPA-secure encryption scheme based on [PERSON]'s work [23]. This led to a non-interactive key generation process; however, it is non-compact, as it necessitates a unique key for each possible subset of corrupted participants. [PERSON] et al. [24] proposed a threshold CCA-secure public key encryption (PKE) scheme based on the Learning with Errors (LWE) problem [23], which incorporates lossy trapdoor functions. However, in this scheme, the size of the ciphertext and public key is at least linear with respect to the number of servers. Therefore, due to this factor's expansion, the aforementioned two schemes are impractical for multiple parties. [PERSON] et al. [6] were the first to propose a multi-key fully homomorphic encryption (MKFHE) scheme based on the NTRU algorithm, after which MKFHE research entered a phase of rapid development. In LWE-based MKFHE schemes [7; 9; 10; 11], each participating party encrypts its input using an FHE scheme and broadcasts the ciphertext to the others. Subsequently, each participant homomorphically evaluates the received ciphertexts from other parties and engages in a round of distributed decryption protocol. If a trusted authority thresholdizes the encryption keys during the Setup phase and distributes them to the parties, the keys can then be additively shared. However, these schemes all require a ciphertext extension step, which significantly increases the ciphertext size and makes the computational cost of homomorphic evaluation expensive. Among these, [PERSON] et al. [8], in their pioneering work on LWE-based multi-party homomorphic encryption, demonstrated the construction of a three-round MPC protocol using a common reference string. They achieved semi-malicious security based on the LWE problem, and further achieved full malicious security through NIZK. However, they did not specifically detail the secret share scheme employed to achieve the t-out-of-N access structure. Additionally, in practice, directly reconstructing the secret key shares is undesirable, because it reveals the shares of the failed parties to the other parties. [PERSON] et al. [19] proposed a t-out-of-N universal thresholdizer based on the LWE problem, enabling threshold versions of arbitrary multi-party signature schemes. This scheme uses a TMFHE scheme constructed with secret sharing techniques to encrypt the keys of the underlying signature scheme, and uses threshold decryption to recover the signature. However, in more robust asynchronous settings, participants cannot determine which other parties are online when generating decryption shares, leading to increased complexity and performance overhead. [PERSON] et al. [25] applied this method [19] to the signature scheme by [PERSON] et al. [26], and demonstrated how to handle adaptive corruption. [PERSON] et al. [27] proposed a multi-party homomorphic encryption scheme based on the RLWE problem, which achieves linear communication complexity and non-interactive circuit evaluation through multi-party protocols such as key switching, relinearization, and public key switching. However, the scheme only provides passive security under the semi-honest model. Similarly, [PERSON] et al. [21] constructed a TMFHE scheme based on the Ring-LWE problem, using share resharing techniques, which has a t-out-of-N access structure. They proposed reconstructing the secret key shares in the threshold decryption protocol without needing a trusted dealer to distribute the share. Therefore, their scheme is simpler and more compact, with good performance, but its security can only be effective against static passive semi-honest adversaries. [PERSON] et al. [28] provided a compact threshold cryptosystem with commitment and zero-knowledge proof protocols.