Oblivious transfer (OT) is a fundamental primitive of secure computation. In a
series of works we demonstrated efficient protocols and applications for
various variants of oblivious transfer (in reverse chronological order):
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.
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.