The simplest protocol for oblivious transfer

T. Chou, C. Orlandi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

19 Citations (Scopus)

Abstract

Oblivious Transfer (OT) is the fundamental building block 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 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.
Original languageEnglish
Title of host publicationProgress in Cryptology - LATINCRYPT 2015 : 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015
EditorsK. Lauter, F. Rodríguez-Henríquez
PublisherSpringer
Pages40-58
ISBN (Electronic)978-3-319-22174-8
ISBN (Print)978-3-319-22173-1
DOIs
Publication statusPublished - 2015
Event4th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT 2015), August 23-26, 2015, Guadalajara, Mexico - Hotel De Mendoza, Guadalajara, Mexico
Duration: 23 Aug 201526 Aug 2015

Publication series

NameLecture Notes in Computer Science
Volume9230
ISSN (Print)0302-9743

Conference

Conference4th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT 2015), August 23-26, 2015, Guadalajara, Mexico
Abbreviated titleLATINCRYPT 2015
CountryMexico
CityGuadalajara
Period23/08/1526/08/15

Fingerprint

Communication

Cite this

Chou, T., & Orlandi, C. (2015). The simplest protocol for oblivious transfer. In K. Lauter, & F. Rodríguez-Henríquez (Eds.), Progress in Cryptology - LATINCRYPT 2015 : 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015 (pp. 40-58). (Lecture Notes in Computer Science; Vol. 9230). Springer. https://doi.org/10.1007/978-3-319-22174-8_3
Chou, T. ; Orlandi, C. / The simplest protocol for oblivious transfer. Progress in Cryptology - LATINCRYPT 2015 : 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015. editor / K. Lauter ; F. Rodríguez-Henríquez. Springer, 2015. pp. 40-58 (Lecture Notes in Computer Science).
@inproceedings{8ca5375495ab49129dc68074353edee9,
title = "The simplest protocol for oblivious transfer",
abstract = "Oblivious Transfer (OT) is the fundamental building block 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 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.",
author = "T. Chou and C. Orlandi",
year = "2015",
doi = "10.1007/978-3-319-22174-8_3",
language = "English",
isbn = "978-3-319-22173-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "40--58",
editor = "K. Lauter and F. Rodr{\'i}guez-Henr{\'i}quez",
booktitle = "Progress in Cryptology - LATINCRYPT 2015 : 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015",
address = "Germany",

}

Chou, T & Orlandi, C 2015, The simplest protocol for oblivious transfer. in K Lauter & F Rodríguez-Henríquez (eds), Progress in Cryptology - LATINCRYPT 2015 : 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015. Lecture Notes in Computer Science, vol. 9230, Springer, pp. 40-58, 4th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT 2015), August 23-26, 2015, Guadalajara, Mexico, Guadalajara, Mexico, 23/08/15. https://doi.org/10.1007/978-3-319-22174-8_3

The simplest protocol for oblivious transfer. / Chou, T.; Orlandi, C.

Progress in Cryptology - LATINCRYPT 2015 : 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015. ed. / K. Lauter; F. Rodríguez-Henríquez. Springer, 2015. p. 40-58 (Lecture Notes in Computer Science; Vol. 9230).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - The simplest protocol for oblivious transfer

AU - Chou, T.

AU - Orlandi, C.

PY - 2015

Y1 - 2015

N2 - Oblivious Transfer (OT) is the fundamental building block 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 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.

AB - Oblivious Transfer (OT) is the fundamental building block 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 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.

U2 - 10.1007/978-3-319-22174-8_3

DO - 10.1007/978-3-319-22174-8_3

M3 - Conference contribution

SN - 978-3-319-22173-1

T3 - Lecture Notes in Computer Science

SP - 40

EP - 58

BT - Progress in Cryptology - LATINCRYPT 2015 : 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015

A2 - Lauter, K.

A2 - Rodríguez-Henríquez, F.

PB - Springer

ER -

Chou T, Orlandi C. The simplest protocol for oblivious transfer. In Lauter K, Rodríguez-Henríquez F, editors, Progress in Cryptology - LATINCRYPT 2015 : 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015. Springer. 2015. p. 40-58. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-22174-8_3