Cryptographic Algorithms for the Secure Delegation of Multiparty Computation

In today's world, we store our data and perform expensive computations remotely on powerful servers (a.k.a."the cloud") rather than on our local devices. In this dissertation we study the question of achieving cryptographic security in the setting where multiple (mutually distrusting) clients wish to delegate the computation of a joint function on their inputs to an untrusted cloud, while keeping these inputs private. We introduce two frameworks for modeling such protocols.;The first, called cloud-assisted multiparty computation (cloud-assisted MPC), builds on the standard notion of MPC to incorporate the concept of delegation. In particular, since the cloud is expected to perform the computation of the function, our definition requires the communication complexity of the protocol, as well as the computation time of all clients to be (essentially) independent of the complexity of the function.;The second, called on-the-fly MPC, builds on the notion of cloud-assisted MPC and further requires that the clients be involved only when (initially) uploading their input to the cloud, and in a final phase when outputs are revealed. In particular, this allows the server to choose functions (and subsets of data on which to evaluate the functions) on-the-fly, and evaluate these functions without requiring any interaction with the clients. The only interaction required takes place in the final phase after the computation has been completed, when the clients must retroactively approve both the chosen functions, and the subsets of data upon which these functions were evaluated.;We construct cloud-assisted and on-the-fly MPC protocols using fully homomorphic encryption (FHE). However, FHE is only suitable for computations that involve a single user, since it requires inputs to be encrypted under the same key. We extend it to the multiparty setting in two ways.;We introduce the notion of threshold FHE: fully homomorphic encryption that allows the clients to jointly generate a common public key (whose corresponding secret key is shared among them), as well as decrypt a ciphertext under this public key without learning anything but the plaintext. Using threshold FHE, we show how to construct an efficient cloud-assisted MPC protocol. We construct threshold FHE using (a modification of) the Brakerski-Vaikuntanathan (ring-based) FHE scheme; however our ideas extend to many other lattice-based FHE schemes in the literature.;We introduce the notion of multikey FHE: fully homomorphic encryption that allows the cloud to perform homomorphic evaluation on ciphertexts encrypted under different and independent keys. We show a construction of on-the-fly MPC using multikey FHE, and construct a multikey FHE scheme based on NTRU encryption. We highlight that it was previously not known how to make NTRU fully homomorphic, even for a single key. Therefore, we view the construction of (multikey) FHE from NTRU encryption as a main contribution of independent interest.