International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Blazing Fast OT for Three-Round UC OT Extension

Ran Canetti
Pratik Sarkar
Xiao Wang
DOI: 10.1007/978-3-030-45388-6_11
Search ePrint
Search Google
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.
Video from PKC 2020
  title={Blazing Fast OT for Three-Round UC OT Extension},
  booktitle={Public-Key Cryptography – PKC 2020},
  series={Public-Key Cryptography – PKC 2020},
  author={Ran Canetti and Pratik Sarkar and Xiao Wang},