Abstract In this paper, we construct multi-key homomorphic and fully homomorphic encryption (resp. MKHE and MKFHE) schemes with malicious circuit privacy. Our schemes are based on learning with errors (LWE) besides appropriate circular security assumptions. In contrast, the previous maliciously circuit-private MKFHE scheme by Chongchitmate and Ostrovsky (PKC, 2017) is based on the non-standard decisional small polynomial ratio (DSPR) assumption with a super-polynomial modulus, besides ring learning with errors and circular security assumptions. We note that it was shown by Albrecht et al. (CRYPTO, 2016) that there exists a sub-exponential time attack against this type of DSPR assumption. The main building block of our maliciously circuit-private MKFHE scheme is a (plain) MKFHE scheme by Brakerski et al. (TCC, 2017), and the security of our schemes is proven under the hardness of LWE with sub-exponential modulus-to-noise ratio and circular security assumptions related to the Brakerski et al. scheme. Furthermore, based on our MKFHE schemes, we construct four-round multi-party computation (MPC) protocols with circuit privacy against a semi-honest server and malicious clients in the plain model. The protocols are obtained by combining our schemes with a maliciously sender-private oblivious transfer protocol and a circuit garbling scheme, all of which can be instantiated only assuming LWE.
Abstract In this paper, we construct multi-key homomorphic and fully homomorphic encryption (resp. MKHE and MKFHE) schemes with malicious circuit privacy. Our schemes are based on learning with errors (LWE) besides appropriate circular security assumptions. In contrast, the previous maliciously circuit-private MKFHE scheme by Chongchitmate and Ostrovsky (PKC, 2017) is based on the non-standard decisional small polynomial ratio (DSPR) assumption with a super-polynomial modulus, besides ring learning with errors and circular security assumptions. We note that it was shown by Albrecht et al. (CRYPTO, 2016) that there exists a sub-exponential time attack against this type of DSPR assumption. The main building block of our maliciously circuit-private MKFHE scheme is a (plain) MKFHE scheme by Brakerski et al. (TCC, 2017), and the security of our schemes is proven under the hardness of LWE with sub-exponential modulus-to-noise ratio and circular security assumptions related to the Brakerski et al. scheme. Furthermore, based on our MKFHE schemes, we construct four-round multi-party computation (MPC) protocols with circuit privacy against a semi-honest server and malicious clients in the plain model. The protocols are obtained by combining our schemes with a maliciously sender-private oblivious transfer protocol and a circuit garbling scheme, all of which can be instantiated only assuming LWE.
We present a framework for constructing compact FHE (fully homomorphic encryption) which is circuit-private in the malicious setting. That is, even if both maliciously formed public key and ciphertext are used, encrypted outputs only reveal the evaluation of the circuit on some well-formed input x ∗. Previous literature on FHE only considered semi-honest circuit privacy. Circuit-private FHE schemes have direct applications to computing on encrypted data. In that setting, one party (a receiver) holding an input x wishes to learn the evaluation of a circuit C held by another party (a sender). The goal is to make receiver’s work sublinear (and ideally independent) of C, using a 2-message protocol. Maliciously circuit-private FHE immediately gives rise to such a protocol which is secure against a malicious receiver.
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.
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t l n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t l n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t < n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t < n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.
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.
The Multi-Key Fully Homomorphic Encryption (MKFHE) based on the NTRU cryptosystem is an important alternative to the post-quantum cryptography due to its simple scheme form, high efficiency, and fewer ciphertexts and keys. In 2012, Lopez-Alt et al. proposed the first NTRU-type MKFHE scheme, the LTV12 scheme, using the key-switching and modulus-reduction techniques, whose security relies on two assumptions: the Ring Learning With Error (RLWE) assumption and the Decisional Small Polynomial Ratio (DSPR) assumption. However, the LTV12 and subsequent NTRU-type schemes are restricted to the family of power-of-2 cyclotomic rings, which may affect the security in the case of subfield attacks. Moreover, the key-switching technique of the LTV12 scheme requires a circular application of evaluation keys, which causes rapid growth of the error and thus affects the circuit depth. In this paper, an NTRU-type MKFHE scheme over prime cyclotomic rings without key-switching is proposed, which has the potential to resist the subfield attack and decrease the error exponentially during the homomorphic evaluating process. First, based on the RLWE and DSPR assumptions over the prime cyclotomic rings, a detailed analysis of the factors affecting the error during the homomorphic evaluations in the LTV12 scheme is provided. Next, a Low Bit Discarded & Dimension Expansion of Ciphertexts (LBD&DEC) technique is proposed, and the inherent homomorphic multiplication decryption structure of the NTRU is proposed, which can eliminate the key-switching operation in the LTV12 scheme. Finally, a leveled NTRU-type MKFHE scheme is developed using the LBD&DEC and modulus-reduction techniques. The analysis shows that the proposed scheme compared to the LTV12 scheme can decrease the magnitude of the error exponentially and minimize the dimension of ciphertexts.