Secure comparison (SC) is an essential primitive in Secure Multiparty Computation (SMC) and a fundamental building block in Privacy-Preserving Data Analytics (PPDA). Although secure comparison has been studied since the introduction of SMC in the early 80s and many protocols have been proposed, there is still room for improvement, especially providing security against malicious adversaries who form the majority among the participating parties. It is not hard to develop an SC protocol secure against malicious majority based on the current state-of-the-art SPDZ framework. SPDZ is designed to work for arbitrary polynomially-bounded functionalities; it may not provide the most efficient SMC implementation for a specific task, such as SC. In this thesis, we propose a novel and efficient compiler specifically designed to convert most existing SC protocols with semi-honest security into the ones secure against the dishonest majority (malicious majority). We analyze the security of the proposed solutions using the real-ideal paradigm. Moreover, we provide computation and communication complexity analysis. Comparing to the current state-of-the-art SC protocols Rabbit and edaBits, our design offers significant performance gain. The empirical results show that the proposed solution is at least 5 and 10 times more efficient than Rabbit in run-time and communication cost respectively.
Secure comparison (SC) is an essential primitive in Secure Multiparty Computation (SMC) and a fundamental building block in Privacy-Preserving Data Analytics (PPDA). Although secure comparison has been studied since the introduction of SMC in the early 80s and many protocols have been proposed, there is still room for improvement, especially providing security against malicious adversaries who form the majority among the participating parties. It is not hard to develop an SC protocol secure against malicious majority based on the current state-of-the-art SPDZ framework. SPDZ is designed to work for arbitrary polynomially-bounded functionalities; it may not provide the most efficient SMC implementation for a specific task, such as SC. In this thesis, we propose a novel and efficient compiler specifically designed to convert most existing SC protocols with semi-honest security into the ones secure against the dishonest majority (malicious majority). We analyze the security of the proposed solutions using the real-ideal paradigm. Moreover, we provide computation and communication complexity analysis. Comparing to the current state-of-the-art SC protocols Rabbit and edaBits, our design offers significant performance gain. The empirical results show that the proposed solution is at least 5 and 10 times more efficient than Rabbit in run-time and communication cost respectively.
Secure multiparty computation (MPC) over Z2kis more efficient than computations over fields, and studying MPC protocols under malicious security has practical application value. Malicious security with a dishonest majority over rings remains challenging. The most popular approach is SPDZ2k, however, this is a specific protocol that does not support the transformation of any existing semi-honest MPC protocols into malicious security protocols. The zero knowledge proof (ZKP)-based compiler satisfies this requirement. Existing state-of-the-art protocols have logarithmic online communication overhead in terms of the circuit size |C|, and their direct application to rings is nontrivial as they were originally designed for finite fields. In this work, we investigate the communication overhead to develop malicious security protocols. We bridge the gap between malicious security with abort and semi-honest security, by constructing a “GMW-style” verification protocol to achieve malicious security in a dishonest majority setting. This approach incurs a constant online communication overhead by enhancing the machinery of zero-knowledge fully linear interactive oracle proof (zk-FLIOP). Additionally, we extend the zk-FLIOP to work over any ring by invoking reverse multiplication friendly embeddings (RMFEs). Our results show that the online communication complexity of the verification process depends on only the security parameter, the number of parties, and the ring size. Furthermore, for small-scale circuits over Z2, we designed a distributed lookup table argument where both the total communication complexity and the computational cost are independent of the circuit size but of the input wires.
Protocols for secure multiparty computation (MPC) enable a set of mutually distrusting parties to compute an arbitrary function of their inputs while preserving basic security properties like privacy and correctness. The study of MPC was initiated in the 1980s where it was shown that any function can be securely computed, thus demonstrating the power of this notion. However, these proofs of feasibility were theoretical in nature and it is only recently that MPC protocols started to become efficient enough for use in practice. Today, we have protocols that can carry out large and complex computations in very reasonable time (and can even be very fast, depending on the computation and the setting). Despite this amazing progress, there is still a major obstacle to the adoption and use of MPC due to the huge expertise needed to design a specific MPC execution. In particular, the function to be computed needs to be represented as an appropriate Boolean or arithmetic circuit, and this requires very specific expertise. In order to overcome this, there has been considerable work on compilation of code to (typically) Boolean circuits. One work in this direction takes a different approach, and this is the SPDZ compiler (not to be confused with the SPDZ protocol) that takes high-level Python code and provides an MPC run-time environment for securely executing that code. The SPDZ compiler can deal with arithmetic and non-arithmetic operations and is extremely powerful. However, until now, the SPDZ compiler could only be used for the specific SPDZ family of protocols, making its general applicability and usefulness very limited. In this paper, we extend the SPDZ compiler so that it can work with general underlying protocols. Our SPDZ extensions were made in mind to enable the use of SPDZ for arbitrary protocols and to make it easy for others to integrate existing and new protocols. We integrated three different types of protocols, an honest-majority protocol for computing arithmetic circuits over a field (for any number of parties), a three-party honest majority protocol for computing arithmetic circuits over the ring of integers Z2n, and the multiparty BMR protocol for computing Boolean circuits. We show that a single high-level SPDZ-Python program can be executed using all of these underlying protocols (as well as the original SPDZ protocol), thereby making SPDZ a true general run-time MPC environment.In order to be able to handle both arithmetic and non-arithmetic operations, the SPDZ compiler relies on conversions from field elements to bits and back. However, these conversions do not apply to ring elements (in particular, they require element division), and we therefore introduce new bit decomposition and recomposition protocols for the ring over integers with replicated secret sharing. These conversions are of independent interest and utilize the structure of Z2n (which is much more amenable to bit decomposition than prime-order fields), and are thus much more efficient than all previous methods. We demonstrate our compiler extensions by running a complex SQL query and a decision tree evaluation over all protocols.
Secure multiparty computation (MPC) enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. Protocols for semi-honest adversaries guarantee security as long as the corrupted parties run the specified protocol and ensure that nothing is leaked in the transcript. In contrast, protocols for malicious adversaries guarantee security in the presence of arbitrary adversaries who can run any attack strategy. Security for malicious adversaries is typically what is needed in practice (and is always preferred), but comes at a significant cost. In this paper, we present the first protocol for a two-thirds honest majority that achieves security in the presence of malicious adversariesat essentially the exact same cost as the best known protocols for semi-honest adversaries. Our construction is not a general transformation and thus it is possible that better semi-honest protocols will be constructed which do not support our transformation. Nevertheless, for the current state-of-the-art for many parties (based on Shamir sharing), our protocol invokes the best semi-honest multiplication protocol exactly once per multiplication gate (plus some additional local computation that is negligible to the overall cost). Concretely, the best version of our protocol requires each party to send on average of just 2 2/3 elements per multiplication gate (when the number of multiplication gates is at least the number of parties). This is four times faster than the previous-best protocol of Barak et al. (ACM CCS 2018) for small fields, and twice as fast as the previous-best protocol of Chida et al. (CRYPTO 2018) for large fields.
Secure Multi-Party Computation (MPC) protocols allow a group of mutually distrusting users to compute a function jointly on their inputs without revealing any information beyond the output. For many years, implementations of MPC protocols have targeted security against semi-honest adversaries, i.e., attackers are assumed to execute the protocol honestly but try to learn private information after the fact. Protocols secure against stronger and more realistic malicious adversaries, who could behave arbitrarily during the protocol execution, were known to exist but were much less efficient. This thesis introduces a new paradigm to construct extremely efficient MPC protocols with malicious security. In particular, this thesis consists of three major contributions. 1. We introduce the authenticated garbling framework, and present an efficient concrete instantiation of the protocol. The resulting protocol partially closes the gap between semi-honest and malicious MPC protocols asymptotically; the implementation of the protocol represents the state-of-the-art system for malicious two-party computation. 2. We discuss how to apply authenticated garbling to the multi-party setting, where all-but-one parties can be corrupted by the adversary. The resulting protocol improves upon the best previous constant-round protocol by orders of magnitude. We also present a system that, for the first time, enables MPC executions among hundreds of parties, distributed globally. 3. We present a series of optimizations to two-party authenticated garbling by interpreting authenticated garbling in a new way. The improved malicious protocol has essentially the same concrete efficiency as the best semi-honest protocol in the preprocessing model. 4. We develop these protocols in EMP-toolkit, a practical and efficient MPC tool that can be used to build new protocols and to develop applications using our existing protocols.
Secure multiparty computation (MPC) enables privacy-preserving collaborative computation over sensitive data held by multiple mutually distrusting parties. Unfortunately, in the most natural setting where a majority of the parties are maliciously corrupt (also called the dishonest majority setting), traditional MPC protocols incur high overheads and offer weaker security guarantees than are desirable for practical applications. In this paper, we explore the possibility of circumventing these drawbacks and achieving practically efficient dishonest majority MPC protocols with strong security guarantees by assuming an additional semi-honest, non-colluding helper party HP .1We believe that this is a more realistic alternative to assuming an honest majority, since many real-world applications of MPC involving potentially large numbers of parties (such as dark pools) are typically enabled by a central governing entity that can be modeled as the HP.In the above model, we are the first to design, implement and benchmark a practically-efficient and general multi-party framework, Asterisk. Our framework requires invoking HP only a constant number of times, achieves the strong security guarantee of fairness (either all parties learn the output or none do), scales to hundreds of parties, outperforms all existing dishonest majority MPC protocols, and is, in fact, competitive with state-of-the-art honest majority MPC protocols. Our experiments show that Asterisk achieves 228 – 288× speedup in preprocessing as compared to the best dishonest majority MPC protocol. With respect to online time, Asterisk supports 100-party evaluation of a circuit with 106multiplication gates in approximately 20 seconds. We also implement and benchmark practically efficient and highly scalable dark pool instances using Asterisk. The corresponding run times showcase the effectiveness of Asterisk in enabling efficient realizations of real-world privacy-preserving applications with strong security guarantees.
Due to high complexity, comparison protocols with secret inputs have been a bottleneck in the design of privacy-preserving cryptographic protocols. Different solutions based on homomorphic encryption, garbled circuits and secret sharing techniques have been proposed over the last few years, each claiming high efficiency. Unfortunately, a fair comparison of existing protocols in terms of run-time, bandwidth requirement and round complexity has been lacking so far. In this paper, we analyze the state-of-the-art comparison protocols for a two-party setting in the semi-honest security protocol. We analyze their performances in three stages, namely initialization, pre-processing and online computation, by implementing them on a single platform. The results of our experiments provide a clear insight for the research community into the advantages and disadvantages of the various techniques .