Paper 2001/073

Efficient oblivious transfer schemes

Wen-Guey Tzeng

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.