To solve the problems in the existing fully homomorphic encryption (FHE)-based secure multi-party computation (SMC) protocols such as low efficiency, the FHE scheme that supports multi-bit encryption was modified during the generation of the public key so that the users could generate their public keys independently without the common random string (CRS) matrix. Further, a multi-bit Gentry-Sahai-Waters scheme (MGSW) scheme without CRS was constructed. The modified LinkAlgo algorithm was adopted to expand the single-key ciphertext into the multi-key ciphertext and simplify the way of generating the expanded ciphertext. In this way, a multi-key FHE (MFHE) scheme was achieved based on the MGSW scheme. Finally, a three-round SMC protocol without CRS was constructed using the MFHE scheme and the decisional learning with errors (DLWE) assumption, which was secure in the semi-malicious model. Compared to the existing protocols, the protocol proposed herein can support multi-bit encryption and is found with smaller ciphertext size and lower storage overhead and generate the expanded ciphertext in a simpler way. Overall performance is better than existing protocols.
To solve the problems in the existing fully homomorphic encryption (FHE)-based secure multi-party computation (SMC) protocols such as low efficiency, the FHE scheme that supports multi-bit encryption was modified during the generation of the public key so that the users could generate their public keys independently without the common random string (CRS) matrix. Further, a multi-bit Gentry-Sahai-Waters scheme (MGSW) scheme without CRS was constructed. The modified LinkAlgo algorithm was adopted to expand the single-key ciphertext into the multi-key ciphertext and simplify the way of generating the expanded ciphertext. In this way, a multi-key FHE (MFHE) scheme was achieved based on the MGSW scheme. Finally, a three-round SMC protocol without CRS was constructed using the MFHE scheme and the decisional learning with errors (DLWE) assumption, which was secure in the semi-malicious model. Compared to the existing protocols, the protocol proposed herein can support multi-bit encryption and is found with smaller ciphertext size and lower storage overhead and generate the expanded ciphertext in a simpler way. Overall performance is better than existing protocols.
Aiming at the problems of large ciphertext size and low efficiency in the current secure multi-party computation (SMC) protocol based on fully homomorphic encryption (FHE), the paper proves that the fully homomorphic encryption scheme that supports multi-bit encryption proposed by Chen Li et al. satisfies the key homomorphism. Based on this scheme and threshold decryption, a three-round, interactive, leveled, secure multi-party computation protocol under the Common Random String (CRS) model is designed. The protocol is proved to be safe under the semi-honest model and the semi-malicious model. From the non-interactive zero-knowledge proof, it can be concluded that the protocol is also safe under the malicious model. Its security can be attributed to the Decisional Learning With Errors (DLWE) and a variant of this problem (some-are-errorless LWE). Compared with the existing secure multi-party computation protocol based on fully homomorphic encryption under the CRS model, the ciphertext size of this protocol is smaller, the efficiency is higher, the storage overhead is smaller, and the overall performance is better than the existing protocol.
Multikey fully homomorphic encryption (MFHE) allows homomorphic operations between ciphertexts encrypted under different keys. In applications for secure multiparty computation (MPC) protocols, MFHE can be more advantageous than usual fully homomorphic encryption (FHE) since users do not need to agree with a common public key before the computation when using MFHE. In EUROCRYPT 2016, Mukherjee and Wichs constructed a secure MPC protocol in only two rounds via MFHE which deals with a common random/reference string (CRS) in key generation. After then, Brakerski et al. replaced the role of CRS with the distributed setup for CRS calculation to form a four round secure MPC protocol. Thus, recent improvements in round complexity of MPC protocols have been made using MFHE. In this paper, we go further to obtain round-efficient and secure MPC protocols. The underlying MFHE schemes in previous works still involve the common value, CRS, it seems to weaken the power of using MFHE to allow users to independently generate their own keys. Therefore, we resolve the issue by constructing an MFHE scheme without CRS based on LWE assumption, and then we obtain a secure MPC protocol against semi-malicious security in three rounds. We also define a new security notion “multikey-CPA security” to prove that a multikey ciphertext cannot be decrypted unless all the secret keys are gathered and our scheme is multikey-CPA secure.
Abstract In dynamic multi-key Fully Homomorphic Encryption (MFHE) scheme, homomorphic operations on ciphertexts encrypted under different keys are allowed. Moreover, the resulting ciphertext can be further computed with ciphertexts under other keys. In 2016, Peikert and Shiehian presented a dynamic MFHE scheme that relies on using a Common Reference String (CRS) and circular security assumptions. Subsequently, various variants of dynamic MFHE schemes were proposed based on this scheme, but these variant schemes still rely on a CRS and circular security assumption. Therefore, constructing a MFHE GSW scheme relies solely on the LWE assumption and does not require a CRS remains a valuable challenge. This paper introduces a new dynamic MFHE scheme. Compared to existing solutions, our scheme does not require the circular security assumption and depends solely on the LWE assumption, which theoretically provides an enhanced level of security. Additionally, it eliminates the need for a shared CRS but instead replaces the CRS with each party independently generate random matrices. This decentralized approach enhances the ability of users to generate keys independently. The size of ciphertexts and public keys in our scheme is comparable to other existing solutions, thus maintaining efficiency in both computation and ciphertext extension.
Fully Homomorphic Encryption (FHE) is a powerful encryption system in cloud computing that allows homomorphic computations on encrypted data without decrypting them. Multi-key fully homomorphic encryption (MFHE), as an extension to FHE, allows homomorphic computations on ciphertexts encrypted under different keys. However, most MFHE schemes require a Common Random/Reference String (CRS), while the few that do not are based on the Learning With Errors (LWE) problem, which means that they can only deal with single bit plaintext. Consequently, MFHE schemes based on the Ring Learning With Errors (RLWE) problem are more desirable, as they can handle polynomial plaintext. Requiring the CRS seems to weaken the semantic definition of MFHE, where all users generate their own keys independently. In this paper, we study the RLWE-based MFHE in the CRS model and propose the first RLWE-based MFHE without a CRS. To this end, we remove the CRS by designing a relinearization algorithm without a CRS. Like previous MFHE schemes, our RLWE-based MFHE without CRS has a simple 1-round threshold decryption, which implies a 3-round secure MPC protocol in the plain model from the RLWE assumption.
We construct a general multiparty computation (MPC) protocol in the common random string (CRS) model with only two rounds of interaction, which is known to be optimal. In the honest-but-curious setting we only rely on the learning with errors (LWE) assumption, and in the fully malicious setting we additionally assume the existence of non-interactive zero knowledge arguments (NIZKs). Previously, Asharov et al. (EUROCRYPT ’12) showed how to achieve three rounds based on LWE and NIZKs, while Garg et al. (TCC ’14) showed how to achieve the optimal two rounds based on indistinguishability obfuscation, but it was unknown if two rounds were possible under simpler assumptions without obfuscation. Our approach relies on multi-key fully homomorphic encryption (MFHE), introduced by Lopez-Alt et al. (STOC ’12), which enables homomorphic computation over data encrypted under different keys. We simplify a recent construction of MFHE based on LWE by Clear and McGoldrick (ePrint ’14), and give a stand-alone exposition of that scheme. We then extend this construction to allow for a one-round distributed decryption of a multi-key ciphertext. Our entire MPC protocol consists of the following two rounds: 1. Each party individually encrypts its input under its own key and broadcasts the ciphertext. All parties can then homomorphically compute a multi-key encryption of the output. 2. Each party broadcasts a partial decryption of the output using its secret key. The partial decryptions can be combined to recover the output in plaintext. ∗Aarhus University. E-mail: pratyay85@gmail.com †Northeastern University. E-mail: danwichs@gmail.com.
Abstract. Fully homomorphic encryption (FHE) enables secure computation over the encrypted data of a single party. We explore how to extend this to multiple parties, using threshold fully homomorphic encryption (TFHE). In such scheme, the parties jointly generate a common FHE public key along with a secret key that is shared among them; they can later cooperatively decrypt ciphertexts without learning anything but the plaintext. We show how to instantiate this approach efficiently, by extending the recent FHE schemes of Brakerski, Gentry and Vaikuntanathan (CRYPTO ’11, FOCS ’11, ITCS ’12) based on the (ring) learning with errors assumption. Our main tool is to exploit the property that such schemes are additively homomorphic over their keys. Using TFHE, we construct simple multiparty computation protocols secure against fully malicious attackers, tolerating any number of corruptions, and providing security in the universal composability framework. Our protocols have the following properties: Low interaction: 3 rounds of interaction given a common random string, or 2 rounds with a public-key infrastructure. Low communication: independent of the function being computed (proportional to just input and output sizes). Cloud-assisted computation: the bulk of the computation can be efficiently outsourced to an external entity (e.g. a cloud service) so that the computation of all other parties is independent of the complexity of the evaluated function. 1