A crucial issue, that mostly affects the performance of actively secure computation of RAM programs, is the task of reading/writing from/to memory in a private and authenticated manner. Previous works in the active security and multiparty settings are based purely on the SPDZ (reactive) protocol, hence, memory accesses are treated just like any input to the computation. However, a garbled-circuit-based construction (such as BMR), which benefits from a lower round complexity, must resolve the issue of converting memory data bits to their corresponding wire keys and vice versa.
A crucial issue, that mostly affects the performance of actively secure computation of RAM programs, is the task of reading/writing from/to memory in a private and authenticated manner. Previous works in the active security and multiparty settings are based purely on the SPDZ (reactive) protocol, hence, memory accesses are treated just like any input to the computation. However, a garbled-circuit-based construction (such as BMR), which benefits from a lower round complexity, must resolve the issue of converting memory data bits to their corresponding wire keys and vice versa.
In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has advanced in leaps and bounds, with speedups of some orders of magnitude, making it fast enough to be of use in practice. In contrast, progress on the case of multiparty computation (with more than two parties) has been much slower, with very little work being done. Currently, the only implemented efficient multiparty protocol has many rounds of communication (linear in the depth of the circuit being computed) and thus is not suited for Internet-like settings where latency is not very low. In this paper, we construct highly efficient constant-round protocols for the setting of multiparty computation for semi-honest adversaries. Our protocols work by constructing a multiparty garbled circuit, as proposed in BMR (Beaver et al., STOC 1990). Our first protocol uses oblivious transfer and constitutes the first concretely-efficient constant-round multiparty protocol for the case of no honest majority. Our second protocol uses BGW, and is significantly more efficient than the FairplayMP protocol (Ben-David et al., CCS 2008) that also uses BGW.
Cloud platforms offer innovative solutions for data processing, and privacy concerns arising from this can be addressed through secure multi-party computation (MPC). MPC in the random access machine (RAM) model leverages Oblivious RAM (ORAM) to conceal memory access patterns, rendering it more suitable for data storage and aggregation in cloud environments, where cloud servers can infer user privacy based on observed access patterns. However, most existing RAM-based MPC protocols only ensure semi-honest security; the few actively secure alternatives have limitations in efficiency or input leakage. To address this gap, this paper proposes an efficient active-secure RAM-based MPC protocol without input leakage. Specifically, we first present a new actively secure, reactive MPC protocol with communication of 2(n−1) bits per gate. As the building blocks, we design the (i) multi-party distributed BitGC garbling scheme and (ii) multi-party somewhat homomorphic encryption (SWHE) scheme with distributed decryption. In particular, we then build a RAM-based MPC protocol on top of the above new building blocks with Circuit ORAM and present the check mechanism to achieve secure memory accesses. The implementation shows that our protocol outperforms the prior actively secure RAM-based MPC without leakage by one to two orders of magnitude in both LAN and WAN networks. Compared with the state-of-the-art actively secure RAM-based 2PC with one bit leakage, ours is slightly less efficient in most cases (not all), but supports the multi-party setting and offers a superior alternative for highly confidential environments.
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 2-party computation (2PC) is becoming practical for some applications. However, most ap-proaches are limited by the fact that the desired functionality must be represented as a boolean circuit. In response, random-access machines (RAM programs) have recently been investigated as a promising alternative representation. In this work, we present the first practical protocols for evaluating RAM programs with security against malicious adversaries. A useful efficiency measure is to divide the cost of malicious-secure evalu-ation of f by the cost of semi-honest-secure evaluation of f. Our RAM protocols achieve ratios matching the state of the art for circuit-based 2PC. For statistical security 2−s, our protocol without preprocessing achieves a ratio of s; our online-offline protocol has a pre-processing phase and achieves online ratio ∼ 2s / log T, where T is the total execution time of the RAM program. To summarize, our solutions show that the “extra overhead ” of obtaining malicious security for RAM programs (beyond what is needed for circuits) is minimal and does not grow with the running time of the program. 1
Multiparty computation protocols (MPC) are said to be secure against covert adversaries if the honest parties are guaranteed to detect any misbehavior by the malicious parties with a constant probability. Protocols that, upon detecting a cheating attempt, additionally allow the honest parties to compute certificates, which enable third parties to be convinced of the malicious behavior of the accused parties, are called publicly verifiable. In this work, we make several contributions to the domain of MPC with security against covert adversaries. We identify a subtle flaw in a protocol of Goyal, Mohassel, and Smith (Eurocrypt 2008), meaning that their protocol does not allow to identify a cheating party, and show how to fix their original construction to obtain security against covert adversaries. We present generic compilers that transform arbitrary passively secure preprocessing protocols, i.e. protocols where the parties have no private inputs, into protocols that are secure against covert adversaries and publicly verifiable. Using our compiler, we construct the first efficient variants of the BMR and the SPDZ protocols that are secure and publicly verifiable against a covert adversary that corrupts all but one party, and also construct variants with covert security and identifiable abort. We observe that an existing impossibility result by Ishai, Ostrovsky, and Seyalioglu (TCC 2012) can be used to show that there exist certain functionalities that cannot be realized by parties, that have oracle-access to broadcast and arbitrary two-party functionalities, with information-theoretic security against a covert adversary.
Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives. In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the Oblivious Transfer hybrid model.