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

Scalar Product-Based Distributed Oblivious
Trans fer

Christian L.F. Corniaux and Hossein Ghodosi

James Cook University, Townsville QLD 4811, Australia
{ chris.corniaux,hossein.ghodosi } @jcu.edu.au

Abstract. In a distributed oblivious transfer (DOT) the sender is re-
placed with m servers, and the receiver must contact k ( k ≤ m )ofthese
servers to learn the secret of her choice. Naor and Pinkas introduced
the first unconditionally secure DOT for a sender holding two secrets.
Blundo, D'Arco, Santis, and Stinson generalized Naor and Pinkas's pro-
tocol, in the case that the sender holds n secrets, in the first so-called
(

)-DOT- 1 protocol. Such a protocol should be secure against a
coalition of less than k parties. However, Blundo et al. have shown that
this level of security is impossible to achieve in one-round polynomial-
based constructions.
In this paper, we show that if communication is allowed amongst the
servers, we are able to construct an unconditionally secure, polynomial-
based ( k , m )-DOT- 1 protocol with the highest level of security. More
precisely, in our construction, a receiver who contacts k servers and cor-
rupt up to k − 1 servers (not necessarily from the set of the contacted
servers) cannot learn more than one secret.

k , m

Keywords: Oblivious Transfer, Unconditional Security, Secret Sharing
Scheme.

1 Introduction

Oblivious Transfer (OT) is a cryptographic protocol which allows two parties to
exchange, in total privacy, one or more secret messages. The first OT, introduced
by Rabin [10], enables a sender to transmit a message to a receiver in such a
way that the receiver gets the message with probability

1

2 while the sender does
not know whether the message was received. Even, Goldreich and Lempel [7]
introduced a variant of the original OT for a contract signature application.

This OT, identified as OT- 1 , is an exchange protocol between a receiver and a
sender who has two secret messages; the receiver chooses one of the two messages
and the sender transmits the chosen message to the receiver. At the end of the
protocol, the sender does not know which message was selected and the receiver
knows nothing of the other message.

A major drawback with OT- 1 andwiththemoregeneralOT- 1 described
by Brassard, Crepeau and Roberts [5] is the restriction in the availability of the
secret messages, because if the unique sender is unavailable, the receiver cannot