Oblivious Transfer

Efficient oblivious transfer protocols
This work contains two major results:
A protocol with low amortized complexity for 1-out-of-N oblivious transfer and a bandwidth/computation tradeoff for 1-out-2 OT. In particular the amortized cost of executing 1-out-of-N OT consists of a single modular exponentiation (independently of N) and the cost of an amortized 1-out-of-2 OT is reduced to below the barrier of one modular exponentiation per transfer.
A two round 1-out-N OT protocol which requires a fixed number of exponentiations on the chooser's side and O(N) exponentiations on the sender's side. The analysis of the construction relies of the Decisional Diffie-Hellman Assumption. This is the first two-round OT protocol whose security analysis does not rely on random oracles.
M. Naor and B. Pinkas, Efficient Oblivious Transfer Protocols, Proceedings of SODA 2001 (SIAM Symposium on Discrete Algorithms), January 7-9 2001, Washington DC.

Distributed oblivious transfer
This work describes distributed protocols for oblivious transfer, in which the role of the sender is distributed between several servers, and a chooser (receiver) must contact a threshold of these servers in order to run the oblivious transfer protocol. These distributed oblivious transfer protocols provide information theoretic security, and do not require the parties to compute exponentiations or any other kind of public key operations. Consequently, the protocols are very efficient computationally.
M. Naor and B. Pinkas, Distributed Oblivious Transfer, Advances in Cryptology -- Asiacrypt '00 Proceedings, LNCS 1976, Springer-Verlag, pp. 200-219, December 2000.

Oblivious transfer with adaptive queries
This work describes protocols for the following two-party problem: One party, the sender, has N values and the other party, the receiver, would like to learn k of them, deciding which ones in an adaptive manner (i.e. the i'th value may depend on the first i-1 values). The sender does not want the receiver to obtain more than k values. This is a variant of the well known Oblivious Transfer (OT) problem and has applications in protecting privacy in various settings. We present efficient protocols for the problem that require an O(N) computation in the preprocessing stage and fixed computation (independent of k) for each new value the receiver obtains. The on-line computation involves roughly log(N) invocations of a 1-out-2 OT protocol.
M. Naor and B. Pinkas, Oblivious Transfer with Adaptive Queries, Advances in Cryptology - Crypto '99 Proceedings, LNCS 1666, Springer-Verlag, pp. 573-590, August 1999. (gzipped)

Oblivious transfer and polynomial evaluation
This work describes efficient constructions for two oblivious two-party computation problems: 1-out-of-N Oblivious Transfer and Oblivious Polynomial Evaluation. The oblivious polynomial evaluation protocol is based on a new intractability assumption which is closely related to noisy polynomial reconstruction. A direct corollary of the 1-out-of-N OT protocol is an efficient transformation of any Private Information Retrieval (PIR) protocol to a Symmetric PIR (SPIR) protocol without increasing the number of databases. The new construction for 1-out-of-N OT is highly efficient - it requires only log(N) executions of a 1-out-of-2 OT protocol. We also present a construction for k-out-of-N OT which is more efficient than k repetitions of 1-out-of-N OT. The efficiency of the new OT protocols makes them useful for a variety of applications. These include {\em oblivious sampling} which can be used to securely compare the sizes of web search engines, protocols for privately solving the {\em list intersection problem} and for mutually authenticated key exchange based on (possibly weak) passwords, and protocols for anonymity preserving web usage metering.
M. Naor and B. Pinkas, Oblivious Transfer and Polynomial Evaluation, Proc. of the 31st Symp. on Theory of Computer Science (STOC), Atlanta, GA, pp. 245-254, May 1-4, 1999.