[IKNP03] Extending Oblivious Transfers Efficiently

Authors: Yuval Ishai, Joe Kilian, Kobbi Nissim, Eyal Petrank | Venue: CRYPTO 2003 | Source

Abstract

We consider the problem of extending oblivious transfers: given a small number of oblivious transfers “for free,” can one implement a large number of oblivious transfers at a low cost? We present an efficient protocol for extending oblivious transfers in the random oracle model. Our protocol requires only $k$ base OTs (where $k$ is the security parameter) and $O(n)$ calls to a pseudorandom generator to produce $n$ oblivious transfers, achieving security against semi-honest adversaries. We further show how to eliminate the random oracle by replacing it with a new primitive called correlation-robust hash functions, which can be instantiated from any pseudorandom generator. The result demonstrates that oblivious transfer can be extended at the cost of only $O(k)$ public-key operations and $O(n)$ symmetric-key operations, making large-scale OT practical for secure computation.

BibTeX

Copy

@Inproceedings{C:IKNP03,
  author = {Yuval Ishai and Joe Kilian and Kobbi Nissim and Erez Petrank},
  title = {Extending Oblivious Transfers Efficiently},
  pages = {145--161},
  editor = {Dan Boneh},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2003},
  volume = {2729},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~17--21},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2003},
  doi = {10.1007/978-3-540-45146-4_9},
}