Scalar Product-Based Distributed Oblivious Transfer - Information Security and Cryptology-ICISC 2010 - page 339

obtain any of the messages. To increase the availability of messages, the sender
distributes them to m servers. However, to keep the messages confidential, a
server is only provided with parts - called shares - of the original messages.
Then, the receiver needs to communicate with at least k servers to gain enough
shares to reconstruct a chosen message. In this distributed model, the sender
does not intervene in the rest of the protocol once he has transmitted the partial
secret messages to the servers.
In 2000, Naor and Pinkas [8] introduced the first distributed model for an
OT in an unconditionally secure setting. In this Distributed Oblivious Transfer
(DOT) protocol, the parties encompass a sender who has two secrets, m servers
owning shares of the secrets, and a receiver whose purpose is to obtain one of
the secrets. The protocol itself is composed of two phases: (i) the initialization
phase and (ii) the transfer phase . During the initialization phase, the sender
generates a bivariate polynomial Q , determines shares from this polynomial and
sends to each of the m servers a different set of shares. In the transfer phase,
the receiver chooses the index of a secret and selects the k servers she intends to
contact. Then, she generates a univariate polynomial S and sends to each of the
k selected servers a value determined by the polynomial S and the identifier of
the server. Each contacted server generates a response based on its program and
the received value from the receiver. The response is sent back to the receiver.
After receiving k responses, the receiver is able to determine the chosen secret.
In [3,4], Blundo, D'Arco, De Santis and Stinson generalize Naor and Pinkas's
protocol to n secrets, and define a security model composed of four fundamental
conditions that every DOT must satisfy:

C 1. Correctness - The receiver is able to determine the chosen secret once she
receives information from the k contacted servers.
C 2. Receiver's privacy - A coalition of up to k − 1 servers cannot obtain any

information on the choice of the receiver.
C 3. Sender's privacy with respect to k − 1 servers and the receiver - A coalition
of up to k 1 servers with the receiver does not obtain any information

about the secrets.
C 4. Sender's privacy with respect to a “greedy” receiver - Given the transcript
of the interaction with k servers, a coalition of up to k

−

−

1 dishonest servers
and the receiver does not obtain any information about secrets which were
not chosen by the receiver.

As it has been pointed out by Blundo et al. in [3,4], the protocol introduced by
Naor and Pinkas only satisfies conditions C 1and C 2. Their own protocol satisfies
conditions C 1, C 2and C 3 only. Actually, they have proven that condition C 4
cannot be guaranteed with a one-round DOT protocol - a round being defined
as a set of consistent requests/responses exchanged between the receiver and k
servers.
In this paper, we show that allowing communication amongst the servers
enables us to devise an unconditionally secure DOT protocol that satisfies all the
above conditions. We have chosen to assess the security of our protocol against