In this paper we propose an efficient (string)
OT
n
1
scheme for any
n ≥ 2. We build our
OT
n
1
scheme from fundamental cryptographic techniques directly. It achieves optimal efficiency in terms of 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 2
n modular exponentiations. The distinct feature of our scheme is that the system-wide parameters are independent of
n and
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 secrecy of the un-chosen secrets is based
on hardness of the decisional Diffie-Hellman problem.
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 Naor and Pinkas’s scheme does in many aspects. For example, our scheme is secure against collusion of the receiver R and t-1 servers and it need not restrict R to contact at most t servers, which is difficult to enforce.
For applications, we present a method of transforming any singledatabase PIR protocol into a symmetric PIR protocol with only
one extra unit of communication cost.