Paper 2015/267

The Simplest Protocol for Oblivious Transfer

Tung Chou and Claudio Orlandi

Abstract

Oblivious Transfer (OT) is one of the fundamental building blocks of cryptographic protocols. In this paper we describe the simplest and most efficient protocol for $1$-out-of-$n$ OT to date, which is obtained by tweaking the Diffie-Hellman key-exchange protocol. The protocol allows to perform $m$ $1$-out-of-$n$ OTs using only $2+3m$ full exponentiations ($2m$ for the receiver, $2+m$ for the sender) and, sending only $m+1$ group elements and $2mn$ ciphertexts. We also report on an implementation of the protocol using elliptic curves, and on a number of mechanisms we employ to ensure that our software is secure against active attacks too. Experimental results show that our protocol (thanks to both algorithmic and implementation optimizations) is at least one order of magnitude faster than previous work.

Note: Improved notation and extension to 1-out-of-m OT.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.LATINCRYPT 2015
Keywords
Oblivious TransferUC SecurityElliptic CurvesEfficient Implementation
Contact author(s)
blueprint @ crypto tw
History
2018-05-29: last of 4 revisions
2015-03-23: received
See all versions
Short URL
https://ia.cr/2015/267
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/267,
      author = {Tung Chou and Claudio Orlandi},
      title = {The Simplest Protocol for Oblivious Transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2015/267},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/267}},
      url = {https://eprint.iacr.org/2015/267}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.