You are looking at a specific version 20160607:202954 of this paper. See the latest version.

Paper 2016/602

More Efficient Oblivious Transfer Extensions

Gilad Asharov and Yehuda Lindell and Thomas Schneider and Michael Zohner

Abstract

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large scale oblivious transfer protocols is becoming more evident. Oblivious transfer extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (CRYPTO 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (CRYPTO 2012) presented an efficient OT extension protocol for the setting of malicious adversaries, that is secure in a random oracle model. In this work we improve OT extensions with respect to communication complexity, computation complexity, and scalability in the semi-honest, covert, and malicious model. Furthermore, we show how to modify our maliciously secure OT extension protocol to achieve security with respect to a version of correlation robustness instead of the random oracle. We also provide specific optimizations of OT extensions that are tailored to the use of OT in various secure computation protocols such as Yao’s garbled circuits and the protocol of Goldreich-Micali-Wigderson, which reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations.

Note: This work combines and extends our previous works on OT extension published at ACM CCS 2013 (http://eprint.iacr.org/2013/552) and EUROCRYPT 2015 (http://eprint.iacr.org/2015/061). We have made the following improvements over these versions: - Detailed proof of the malicious OT extension and parameter estimation (§5.2). - Extended special purpose OT functionalities and formal proofs of security (§6). - Extended experiments, in particular comparison with the passively secure 1-out-of-N OT extension of Kolesnikov and Kumaresan (CRYPTO 2013) (§7.4), using parallelism for actively secure OT extension (§7.4), and the k-min entropy correlation (§7.5).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Journal of Cryptology
Keywords
oblivious transferimplementation
Contact author(s)
michael zohner @ crisp-da de
History
2017-12-05: revised
2016-06-07: received
See all versions
Short URL
https://ia.cr/2016/602
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.