A New Approach to Practical Active-Secure Two-Party Computation

By Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, Sai Sheshank Burra. 2012

469 citations recorded by the source corpus.

We propose a new approach to practical two-party computation secure against an active adversary. All prior practical protocols were based on Yao's garbled circuits. We use an OT-based approach and get efficiency via OT extension in the random oracle model. To get a practical protocol we introduce a number of novel techniques for relating the outputs and inputs of OTs in a larger construction. We also report on an implementation of this approach, that shows that our protocol is more efficient than any previous one: For big enough circuits, we can evaluate more than 20000 Boolean gates per second. As an example, evaluating one oblivious AES encryption $$\sim 34000$$ gates takes 64i¾?seconds, but when repeating the task 27i¾?times it only takes less than 3i¾?seconds per instance.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

Citations in the corpus

Privacy-Preserving Distributed Linear Regression on High-Dimensional Data (2017, background): “Generally, MPC techniques represent the implemented functionality either as arithmetic circuits (e.g., SPDZ [15], TinyOT [58]) or as Boolean circuits (e.g., Yao’s protocol [70], GMW [31]).”
More efficient oblivious transfer and extensions for faster secure computation (2013, unknown): “Note that these implementation optimizations are of general nature and can be applied to our, but also to other OT extension protocols with security against stronger active/malicious adversaries, e.g., [28, 43].”
Implementing AES via an Actively/Covertly Secure Dishonest-Majority MPC Protocol (2012, methodology): “In [25] the authors present a two party protocol, but instead of their protocol being based on Yao circuits they instead base it on OT extension in the Random Oracle Model, and a form of “secret sharing with MACs” (similar to the SPDZ protocol which we examine below).”
Scalable Private Set Intersection Based on OT Extension (2018, methodology): “…of our OT-based PSI protocol is an efﬁcient OPRF (cf. § 2.1) instantiation using recent OT extension techniques, in particular the random OT functionality [Nielsen et al. 2012; Asharov et al. 2013] and the N 1 -OT of [Kolesnikov and Kumaresan 2013], which are essentially used to implement an OPRF.”
Billion-Gate Secure Computation with Malicious Adversaries (2012, background): “Our results are in the standard model (i.e., no common reference strings or PKIs) and, in contrast to prior work, we do not use the random oracle model which has well-established theoretical shortcomings.”
Obliv-C: A Language for Extensible Data-Oblivious Computation (2015, methodology): “There are many generic protocols for secure computation, which can perform arbitrary computation on encrypted data [8, 18, 24, 34].”
New Primitives for Actively-Secure MPC over Rings with Applications to Private Machine Learning (2019, methodology): “However, binary triples [ x ] 2 , [ y ] 2 , [ z ] 2 can be generated much more efﬁciently by exploiting TinyOT-style protocols [7], [36], [25], which generate triples with XOR-shared MACs and shares, as we now show.”
Efficient, Oblivious Data Structures for MPC (2014, methodology): “Note that this could be easily improved using multiple cores, since the offline phase is trivially parallelizable, and also the GF(2) times could be cut further by using the offline phase from TinyOT [24].”
Efficient Batched Oblivious PRF with Applications to Private Set Intersection (2016, background): “[24] propose an approach to malicious two-party secure computation, which relates outputs and inputs of OTs in a larger construction.”
High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority (2017, methodology): “The second problem is solved in [19,9,5] by using homomorphic MACs on all of the values.”
Fast and Secure Three-party Computation: The Garbled Circuit Approach (2015, methodology): “Fast implementation of malicious 2PC and MPC in the dishonest majority setting include cut-and-choose solutions based on garbled circuits [LPS08, KS12, FN13, AMPR14], OT-based solutions [NNOB12, LOS14], and implementations in the pre-processing models [DKL + 12, DKL + 13].”
Faster Secure Two-Party Computation in the Single-Execution Setting (2017, methodology): “, [12,31,9]), here we focus on protocols using the cut-and-choose paradigm that is currently the most efficient approach in the single-execution setting when pre-processing is not used.”