Paper 2020/110

Blazing Fast OT for Three-Round UC OT Extension

Ran Canetti, Pratik Sarkar, and Xiao Wang

Abstract

Oblivious Transfer (OT) is an important building block for multi-party computation (MPC). Since OT requires expensive public-key operations, efficiency-conscious MPC protocols use an OT extension (OTE) mechanism [Beaver 96, Ishai et al. 03] to provide the functionality of many independent OT instances with the same sender and receiver, using only symmetric-key operations plus few instances of some base OT protocol. Consequently there is significant interest in constructing OTE friendly protocols, namely protocols that, when used as base-OT for OTE, result in extended OT that are both round-efficient and cost-efficient. We present the most efficient OTE-friendly protocol to date. Specifically: - Our base protocol incurs only 3 exponentiations per instance. - Our base protocol results in a 3 round extended OT protocol. - The extended protocol is UC secure in the Observable Random Oracle Model (ROM) under the CDH assumption. For comparison, the state of the art for base OTs that result in 3-round OTE are proven only in the programmable ROM, and require 4 exponentiations under Interactive DDH or 6 exponentiations under DDH [Masney-Rindal 19]. We also implement our protocol and benchmark it against the Simplest OT protocol [Chou and Orlandi, Latincrypt 2015], which is the most efficient and widely used OT protocol but not known to suffice for OTE. The computation cost is roughly the same in both cases. Interestingly, our base OT is also 3 rounds. However, we slightly modify the extension mechanism (which normally adds a round) so as to preserve the number of rounds in our case.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in PKC 2020
Keywords
Oblivious TransferOT ExtensionGlobal Random Oracle Model
Contact author(s)
pratik93 @ bu edu
canetti @ bu edu
wangxiao @ cs northwestern edu
History
2020-02-04: last of 2 revisions
2020-02-04: received
See all versions
Short URL
https://ia.cr/2020/110
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/110,
      author = {Ran Canetti and Pratik Sarkar and Xiao Wang},
      title = {Blazing Fast {OT} for Three-Round {UC} {OT} Extension},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/110},
      year = {2020},
      url = {https://eprint.iacr.org/2020/110}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.