### On the Round Complexity of OT Extension

Sanjam Garg, Mohammad Mahmoody, Daniel Masny, and Izaak Meckler

##### Abstract

We show that any OT extension protocol based on one-way functions (or more generally any symmetric-key primitive) either requires an additional round compared to the base OTs or must make a non-black-box use of one-way functions. This result also holds in the semi-honest setting or in the case of certain setup models such as the common random string model. This implies that OT extension in any secure computation protocol must come at the price of an additional round of communication or the non-black-box use of symmetric key primitives. Moreover, we observe that our result is tight in the sense that positive results can indeed be obtained using non-black-box techniques or at the cost of one additional round of communication.

Note: Fixing typos.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Oblivious Transfer ExtensionSymmetric Key PrimitivesRandom Oracle ModelBlack-BoxNon-Black-Box
Contact author(s)
mahmoody @ gmail com
daniel masny @ berkeley edu
History
2018-06-03: last of 4 revisions
See all versions
Short URL
https://ia.cr/2017/1187

CC BY

BibTeX

@misc{cryptoeprint:2017/1187,
author = {Sanjam Garg and Mohammad Mahmoody and Daniel Masny and Izaak Meckler},
title = {On the Round Complexity of OT Extension},
howpublished = {Cryptology ePrint Archive, Paper 2017/1187},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/1187}},
url = {https://eprint.iacr.org/2017/1187}
}

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