Abstract Cloud computing has data leakage from all parties, security protection of private data, and existing solutions do not provide a trade-off between security and overhead. With distributed data communication due to data barriers, information interaction security and data computation security have become challenges for secure computing. Combining cloud computing with secure multiparty computation can provide a higher level of data protection while maintaining the benefits of cloud computing. In this case, data can be stored in the cloud and computed through SMPC protocols, thus protecting the privacy and security of the data. However, multiple rounds of information interaction are often required, increasing the communication overhead, and the security strength is limited by the hardness assumption. In this paper, we work to achieve an optimal setting of the number of rounds in secure multi-party computation on the cloud to achieve a sublinear communication overhead and improve the security concept. A 2-round SMPC protocol is constructed in the framework of Universally Composable (UC). A 2-round SMPC protocol is constructed that uses multilinear maps based on the Learning from Errors (LWE) assumption. The participant encodes the input and sends it via broadcast to reduce the interaction, homomorphic computational encoding information for secure access to computational data and secure the SMPC protocol through UC security. This paper extends the participants to multiple parties, reduces the communication rounds to 2, the protocol achieves sublinear communication overhead in poly polynomial time, smaller setup size to poly(k), and static security is achieved.
Abstract Cloud computing has data leakage from all parties, security protection of private data, and existing solutions do not provide a trade-off between security and overhead. With distributed data communication due to data barriers, information interaction security and data computation security have become challenges for secure computing. Combining cloud computing with secure multiparty computation can provide a higher level of data protection while maintaining the benefits of cloud computing. In this case, data can be stored in the cloud and computed through SMPC protocols, thus protecting the privacy and security of the data. However, multiple rounds of information interaction are often required, increasing the communication overhead, and the security strength is limited by the hardness assumption. In this paper, we work to achieve an optimal setting of the number of rounds in secure multi-party computation on the cloud to achieve a sublinear communication overhead and improve the security concept. A 2-round SMPC protocol is constructed in the framework of Universally Composable (UC). A 2-round SMPC protocol is constructed that uses multilinear maps based on the Learning from Errors (LWE) assumption. The participant encodes the input and sends it via broadcast to reduce the interaction, homomorphic computational encoding information for secure access to computational data and secure the SMPC protocol through UC security. This paper extends the participants to multiple parties, reduces the communication rounds to 2, the protocol achieves sublinear communication overhead in poly polynomial time, smaller setup size to poly(k), and static security is achieved.
Many distributed interaction scenarios exist in big data networks, which require joint computation in different environments. In the traditional secure multiparty computation(SMPC), there exist constant rounds or even more rounds of interaction, which greatly increases the communication overhead. In this paper, we address the problem of optimizing the complexity of rounds by constructing a secure computation protocol that achieves semi-honest static security based on a polynomial puzzle assumption. The multiparty interactive computation is performed using multilinear maps operation, and the obtained results are transmitted over the broadcast channel. The security analysis shows that the protocol achieves static security.
We construct protocols for secure multiparty computation with the help of a computationally powerful party, namely the “cloud”. Our protocols are simultaneously ecient in a number of metrics: • Rounds: our protocols run in 4 rounds in the semi-honest setting, and 5 rounds in the malicious setting. • Communication: the number of bits exchanged in an execution of the protocol is independent of the complexity of function f being computed, and depends only on the length of the inputs and outputs. • Computation: the computational complexity of all parties is independent of the complexity of the function f, whereas that of the cloud is linear in the size of the circuit computing f. In the semi-honest case, our protocol relies on the “ring learning with errors” (RLWE) assumption, whereas in the malicious case, security is shown under the Ring LWE assumption as well as the existence of simulation-extractable NIZK proof systems and succinct non-interactive arguments. In the malicious setting, we also relax the communication and computation requirements above, and only require that they be “small” ‐ polylogarithmic in the computation size and linear in the size of the joint size of the inputs. Our constructions leverage the key homomorphic property of the recent fully homomorphic encryption scheme of Brakerski and Vaikuntanathan (CRYPTO 2011, FOCS 2011). Namely, these schemes allow combining encryptions of messages under dierent keys to produce an encryption (of the sum of the messages) under the sum of the keys. We also design an ecient, non-interactive threshold decryption protocol for these fully homomorphic encryption schemes.
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) enables distrustful parties to jointly perform computations while guaranteeing both the privacy of their inputs and the correctness of the computation.
This thesis explores two aspects of secure multi-party computation: adaptive security and round efficiency. Adaptive security is concerned with an adversary that adaptively determines who and when to corrupt during the course of the computation. Even though this is a very natural and realistic assumption about the adversary, most of the MPC literature addresses security only against a static adversary — an adversary that chooses (and fixes) which parties to corrupt before the protocol starts executing. A protocol is called round-efficient if it runs in a small number of rounds. Constructing such protocols is important since efficiency of a protocol is greatly influenced by its round complexity.
The security in this thesis is formulated in the universal composability (UC) framework introduced by Canetti [Can01]. Protocols secure in the UC framework remain secure even when executed concurrently with other arbitrary protocols running in some larger network, and can be used as subroutines of larger protocols in a modular fashion. This property is important considering that nowadays many protocols are executed concurrently with others in the Internet.
With the focus on adaptive security and round efficiency, we obtain the following results:
(1) We show that with access to an ideal commitment functionality, there exists a protocol that UC realizes any well-formed multi-party functionality against a malicious, adaptive adversary that may corrupt any number of parties, with black-box access to any protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary.
(2) We show that there exists a protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary, with black-box access to a cryptographic primitive called a trapdoor simulatable cryptosystem, which is a natural relaxation of a simulatable cryptosystem introduced by Damgard and Nielsen [3N00].
We also show that the primitive can be constructed based on hardness of factoring.
(3) We present a single-message protocol that UC realizes two-party computing with encrypted data (a variant of secure two-party computation), based on the DDH assumption and non- interactive zero-knowledge arguments. The protocol achieves security against a malicious, static adversary.
(4) We present two round-efficient protocols that UC realize multi-party computing with encrypted data (a variant of secure multi-party computation), based on the DDH assumption and non-interactive zero-knowledge arguments. The first (resp. second) protocol requires one round (resp. two rounds) with appropriate preprocessing, which is independent of the exact circuit and actual inputs of the specific instance problem to solve — only the bound on the circuit size is known. Although the first protocol is more round-efficient, the preprocessing of the second is sometimes better under some efficiency considerations. Both protocols achieve security against a malicious, static adversary that may corrupt up to all but one parties.
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
Secure Multiparty Computation (MPC) allows a set of parties, each having its own private data, to compute a function of their joint data such that the parties only learn the output of this function and everything else about their data is hidden. MPC is a fundamental cryptographic abstraction that captures many other natural cryptographic primitives as special cases. It also has a wide range of practical applications such as conducting secure electronic auctions, delegating sensitive computation to untrusted cloud service providers, secure computation on genomic data and training machine learning models on private data.A long-standing open problem in this area is to construct MPC protocols that have {\\it optimal} (two-round) round complexity under the {\\it weakest} possible cryptographic hardness assumptions.We {\\it completely resolve} this problem by showing lower bounds and matching upper bounds on the hardness assumptions required for constructing round-optimal MPC. Specifically, we obtain the following results.\\begin{itemize}\\item \\textbf{Black-Box Separation.} We show that there exists no construction of two-round semi-honest MPC protocol for general functions that makes black-box use of a two-round oblivious transfer. As a corollary, a similar separation holds when starting with any 2-party functionality other than oblivious transfer. \\item \\textbf{Non-Black-Box Construction.} We show that the above negative result can be bypassed by making non-black-box use of a two-round oblivious transfer. Specifically, starting from a semi-honest (resp. malicious) secure two-round oblivious transfer protocol, we construct a two-round MPC protocol against semi-honest (resp. malicious) adversaries. \\end{itemize}Since any two-round MPC protocol for general functionalities implies a two-round oblivious transfer as a special case, the above two results show that non-black-box use of oblivious transfer is {\\it necessary and sufficient} to construct round-optimal MPC protocols.