Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Oblivious Transfer, UC Security, Elliptic Curves, Efficient Implementation

Original Publication (with minor differences): LATINCRYPT 2015

Date: received 22 Mar 2015, last revised 29 May 2018

Contact author: blueprint at crypto tw

Available format(s): PDF | BibTeX Citation

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

Version: 20180529:135402 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]