Actively Secure OT Extension with Optimal Overhead

Marcel Keller; Emmanuela Orsini; Peter Scholl

Paper 2015/546

Actively Secure OT Extension with Optimal Overhead

Marcel Keller

, University of Bristol

Emmanuela Orsini

, University of Bristol

Peter Scholl

, University of Bristol

Abstract

We describe an actively secure OT extension protocol in the random oracle model with efficiency very close to the passively secure IKNP protocol of Ishai et al. (Crypto 2003). For computational security parameter $κ$ , our protocol requires $κ$ base OTs, and is the first practical, actively secure protocol to match the cost of the passive IKNP extension in this regard. The added communication cost is only additive in , independent of the number of OTs being created, while the computation cost is essentially two finite field operations per extended OT. We present implementation results that show our protocol takes no more than 5% more time than the passively secure IKNP extension, in both LAN and WAN environments, and thus is essentially optimal with respect to the passive protocol. *Update, 2022:* Roy (Crypto 2022) showed that Lemma 1, which the core of our proof relies on, is incorrect, so our protocol does not currently have a security proof. Roy also presented a protocol with an alternative consistency check and complete security proof, which also fixes issues with instantiating the hash function raised earlier by Guo et al. (IEEE S&P 2020) and Masny and Rindal (ACM CCS 2019). In Section 4, we show how to fix our protocol using the techniques by Roy.

Note: Fix abstract line breaks

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in CRYPTO 2015
DOI: 10.1007/978-3-662-47989-6_35
Keywords: oblivious transfer extensions
Contact author(s): mks keller @ gmail com
emmanuela orsini @ esat kuleuven be
peter scholl @ cs au dk
History: 2022-09-16: last of 2 revisions; 2015-06-08: received; See all versions
Short URL: https://ia.cr/2015/546
License: CC BY

BibTeX

@misc{cryptoeprint:2015/546,
      author = {Marcel Keller and Emmanuela Orsini and Peter Scholl},
      title = {Actively Secure {OT} Extension with Optimal Overhead},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/546},
      year = {2015},
      doi = {10.1007/978-3-662-47989-6_35},
      url = {https://eprint.iacr.org/2015/546}
}