More efficient oblivious transfer and extensions for faster secure computation

By Gilad Asharov, Yehuda Lindell, Thomas Schneider, Michael Zohner. 2013

456 citations recorded by the source corpus.

Protocols for secure computation enable parties to compute a joint function on their private inputs without revealing anything but the result. A foundation for secure computation is oblivious transfer (OT), which traditionally requires expensive public key cryptography. A more efficient way to perform many OTs is to extend a small number of base OTs using OT extensions based on symmetric cryptography. In this work we present optimizations and efficient implementations of OT and OT extensions in the semi-honest model. We propose a novel OT protocol with security in the standard model and improve OT extensions with respect to communication complexity, computation complexity, and scalability. We also provide specific optimizations of OT extensions that are tailored to the secure computation protocols of Yao and Goldreich-Micali-Wigderson and reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations. By applying our implementation to current secure computation frameworks, we can securely compute a Levenshtein distance circuit with 1.29 billion AND gates at a rate of 1.2 million AND gates per second. Moreover, we demonstrate the importance of correctly implementing OT within secure computation protocols by presenting an attack on the FastGC framework.

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

QUOTIENT: Two-Party Secure Neural Network Training and Prediction (2019, methodology): “EMP is written in C++ and offers efficient implementations of OT and COT extension [3].”
Privacy-Preserving Distributed Linear Regression on High-Dimensional Data (2017, methodology): “Further, it features efficient implementations of OT extension, including variants such as correlated OT [1].”
Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications (2018, positive): “In brief, we summarize our main contributions as follows: • We introduce Chameleon, a novel mixed SFE framework based on ABY [37] which brings benefits upon efficiency, scalability, and practicality by integrating sequential GCs, fixed-point arithmetic, as well as STP-based protocols for precomputin”
Efficient Batched Oblivious PRF with Applications to Private Set Intersection (2016, methodology): “As do PSSZ, we use matrix transposition code from [1] and several other optimizations.”
CrypTFlow2: Practical 2-Party Secure Inference (2020, methodology): “Moreover, simpler (2 1 ) -OTl has a communication of λ + 2l bits [5, 41].”
SecureML: A System for Scalable Privacy-Preserving Machine Learning (2017, methodology): “It implements the OT extension of [11], and applies free XOR [30] and fixed-key AES garbling [12] optimizations for garbled circuits.”
Secure and Efficient Federated Transfer Learning (2019, methodology): “An efficient way to perform many OTs is to extend a small number of expensive baseOTs (based on asymmetric cryptographic operations) using OTExtension (based on much faster symmetric cryptographic primitives) in a constant number of rounds [15].”
XONN: XNOR-based Oblivious Deep Neural Network Inference (2019, methodology): “However, the OT Extension [16, 17, 18] technique enables performing OT using more efficient symmetric-key encryption in conjunction with a fixed number of base OTs that need public-key encryption.”
Scalable Private Set Union from Symmetric-Key Techniques (2019, background): “[2] proposed several IKNP optimizations (some overlapping with [35]) and provided optimized implementation of OT extension.”
ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation (2020, methodology): “For the setup phase, we use correlated OTs (cOT) [5] which incur a communication of `+κ bits per cOT on `-bit strings, where κ is the computational security parameter.”
Cheetah: Lean and Fast Secure Two-Party Deep Neural Network Inference (2022, methodology): “When sender messages are random or correlated in a way, general OT can be replaced with random OT ( ROT ) or correlated OT ( COT ) which are more efﬁcient in communication [3].”
ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation (2015, methodology): “For Arithmetic sharing (§III-A4) we generate multiplication triples via Paillier with packing [62], [66] or DGK with full decryption [22], [32], for Boolean sharing (§III-B) we use the multiplexer of [54] and OT extension [1], [41], and for Yao sharing (§III-C) we use fixed-key AES garbling [7].”
MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer (2016, methodology): “Protocols based on GMW [2, 21] and TinyOT [10, 30, 34] use OT extensions for efficient MPC on binary circuits, and fast garbled circuit protocols use OT extensions in the input stage of the protocol [31].”
SoK: General Purpose Compilers for Secure Multi-Party Computation (2019, background): “Boolean-circuit GMW-based protocols use OTextension [78] to pre-compute ROT correlations, which are then consumed in the online phase of the protocol.”
Faster Secure Two-Party Computation in the Single-Execution Setting (2017, methodology): “[3], matrix transposition takes a significant amount of the time during the execution of OT extension.”
Fast Garbling of Circuits Under Standard Assumptions (2015, methodology): “In contrast, the last scheme is the most efﬁcient as it uses fast ﬁxed-key encryption and the half-gates approach to achieve two ciphertexts per AND gates and none for XOR gates. experiments, optimize OT extension [2] is used).”
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.”