International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Efficient oblivious transfer schemes

Wen-Guey Tzeng
Search ePrint
Search Google
Abstract: In this paper we propose a very efficient (string) $OT_n^1$ scheme for any $n\geq 2$. We build our $OT_n^1$ scheme from fundamental cryptographic techniques directly. It achieves optimal efficiency in the number of rounds and the total number of exchanged messages for the case that the receiver's choice is unconditionally secure. The computation time of our $OT_n^1$ scheme is very efficient, too. The receiver need compute 2 modular exponentiations only no matter how large $n$ is, and the sender need compute $2n$ modular exponentiations. Furthermore, the system-wide parameters need not change during the lifetime of the system and are {\em universally usable}. That is, all possible receivers and senders use the same parameters and need no trapdoors specific to each of them. For our $OT_n^1$ scheme, the privacy of the receiver's choice is unconditionally secure and the privacy of the un-chosen secrets is at least as strong as the hardness of the decisional Diffie-Hellman problem. \par We extend our $OT_n^1$ scheme to distributed oblivious transfer schemes. Our distributed $OT_n^1$ scheme takes full advantage of the research results of secret sharing and is conceptually simple. It achieves better security than Noar and Pinkas's scheme does in many aspects. For example, our scheme is secure against collusion of $R$ and $t$-$1$ servers and it need not restrict $R$ to contact at most $t$ servers, which is difficult to enforce. \par For applications, we present a method of transforming any single-database PIR protocol into a symmetric PIR protocol with only one extra unit of communication cost.
  title={Efficient oblivious transfer schemes},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / oblivious transfer},
  note={manuscript 11558 received 23 Aug 2001},
  author={Wen-Guey Tzeng},