Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer

By Yehuda Lindell, Benny Pinkas. 2011

291 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

Citations in the corpus

Privacy-Preserving Distributed Linear Regression on High-Dimensional Data (2017, background): “The general approach for constructing two-party computation based on garbled circuits that provides security against malicious adversaries employs the so-called cut-and-choose technique [51,47].”
DeepSecure: Scalable Provably-Secure Deep Learning (2017, methodology): “Our solution can be readily modified to support malicious models by following the methodologies presented in [18–21].”
XONN: XNOR-based Oblivious Deep Neural Network Inference (2019, background): “One of the main distinctions between X ONN and the state-of-the-art solutions is that X ONN can be automatically adapted to the malicious security using cut-and-choose techniques [29, 35, 37].”
Obliv-C: A Language for Extensible Data-Oblivious Computation (2015, methodology): “Although there are even stronger protocols that provide complete privacy against malicious adversaries [8, 14, 17, 19, 24, 25, 28], they all require substantially more expensive techniques.”
Fast Cut-and-Choose-Based Protocols for Malicious and Covert Adversaries (2013, methodology): “There are a number of different solutions to these problems that have been presented in [20,21,29,25,9].”
A New Approach to Practical Active-Secure Two-Party Computation (2012, methodology): “On the other hand, there is a growing interest in understanding the practical overhead of secure computation, and several works have perfected and implemented protocols based on Yao’s garbled circuits [28,3,26,23,30,31,16,27,25,1,17], protocols based on homomorphic encryption [21,10,22,4] and protoc”
Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? (2012, background): “, [21,28,30,37]) are available for converting protocols secure in the semi-honest setting to protocols secure under stronger notions of security (although the best known techniques still impose substantial cost).”
More Efficient Constant-Round Multi-Party Computation from BMR and SHE (2016, background): “Extraordinary efficiency has been achieved for both passive adversaries [4,1] and active adversaries [19,20,27,18,16,22,23].”
Faster Secure Two-Party Computation in the Single-Execution Setting (2017, background): “Their construction required 680 garbled circuits for statistical security 2−40, but this has been improved in a sequence of works [34,26,17,24,7,11,1] to the point where currently only 40 circuits are required.”
Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution (2012, background): “Several approaches have been proposed for achieving security against malicious adversaries [11, 22, 25, 33, 35, 27, 24, 32], some of which have been implemented [28, 34, 35, 32].”
Faster Secure Two-Party Computation Using Garbled Circuits (2011, background): “There exist generic ways of modifying the garbled-circuit approach to give covert security [1] or full security against malicious adversaries [19,20,25,30].”
TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits (2015, unknown): “, [48], [50].”
Foundations of garbled circuits (2012, methodology): “…PRF SS10 [53] worry-free encryption prv Φ size asym encryption, signature A11 [2] KDM encryption prv Φ size KDM encryption (wrt to projections) KMR11 [31] server-aided SFE (malicious) aut + obv Φ circ coin-tossing protocol, commitment LP11 [42] 2-party SFE (malicious) prv Φ circ OT, commitment Fig.”
Privacy-preserving matrix factorization (2013, background): “A malicious CSP can create an incorrect circuit, which can be handled with standard techniques for verifying garbled circuits [43, 40].”
Two Halves Make a Whole - Reducing Data Transfer in Garbled Circuits Using Half Gates (2015, background): “Many optimizations in 2PC have focused on reducing the size of the garbled circuits themselves [19,20,27] and reducing the number of circuits required (in the case of malicious security) [6,15,22,24,29].”