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 achieves UC-security against active and adaptive corruptions in the random oracle model.
Due to its simplicity, the protocol is extremely efficient and it allows to perform m 1-out-of-n OTs using only:
- Computation: (n+1)m+2 exponentiations (mn for the receiver, mn+2 for the sender) and - Communication: 32(m+1) bytes (for the 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 3 Jun 2015 Contact author: blueprint at crypto tw Available format(s): PDF | BibTeX Citation Note: Improved notation and extension to 1-out-of-m OT. Version: 20150604:055811 (All versions of this report) Short URL: ia.cr/2015/267 Discussion forum: Show discussion | Start new discussion