### More Efficient Oblivious Transfer and Extensions for Faster Secure Computation

Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner

##### Abstract

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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ACM CCS 2013
DOI
10.1145/2508859.2516738
Keywords
oblivious transferimplementation
Contact author(s)
michael zohner @ ec-spride de
History
Short URL
https://ia.cr/2013/552

CC BY

BibTeX

@misc{cryptoeprint:2013/552,
author = {Gilad Asharov and Yehuda Lindell and Thomas Schneider and Michael Zohner},
title = {More Efficient Oblivious Transfer and Extensions for Faster Secure Computation},
howpublished = {Cryptology ePrint Archive, Paper 2013/552},
year = {2013},
doi = {10.1145/2508859.2516738},
note = {\url{https://eprint.iacr.org/2013/552}},
url = {https://eprint.iacr.org/2013/552}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.