Blazing Fast OT for Three-Round UC OT Extension

Ran Canetti, Pratik Sarkar*, Xiao Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationPublic-Key Cryptography – PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
EditorsAggelos Kiayias, Markulf Kohlweiss, Petros Wallden, Vassilis Zikas
PublisherSpringer
Pages299-327
Number of pages29
ISBN (Print)9783030453879
DOIs
StatePublished - 2020
Event23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, PKC 2020 - Edinburgh, United Kingdom
Duration: May 4 2020May 7 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12111 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, PKC 2020
Country/TerritoryUnited Kingdom
CityEdinburgh
Period5/4/205/7/20

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Blazing Fast OT for Three-Round UC OT Extension'. Together they form a unique fingerprint.

Cite this