264 X. Wei et al.
Diffie-Hellman (DDH) assumption. Our proposed protocol is secure against semi-
honest sender and receiver, which means that the privacy of the sender and
receiver is protected when completing the full protocol. Compared with other
original OT
k
n
protocol, to our best knowledge, our protocol is the most efficient.
For the communication cost, the receiver only sends two group elements to the
sender and the sender sends 2n group elements to the receiver which is inde-
pendent of k. Regarding modular exponentiations computed by the parties, the
receiver and sender compute 2k +3 and 2.5n separately, therefore the compu-
tational complexity of our protocol is just O(n + k), not O(nk) in some other
schemes.
Our proposed protocol has the following advantages.
1. Our work firstly considers how to construct OT
k
n
protocol in the server-aided
(cloud-assisted) setting. In the traditional k-out-of-n oblivious transfer setting,
there exist only two parties, the sender and receiver, and they interact with
each other in real protocol. Therefore, they must compute complex computa-
tional task by themselves. Differently, in our server-aided setting, there also
exist two cloud servers, which help the participants to compute numerous mod-
ular exponentiations. As a result, the computational complexity of the partic-
ipants is improved. We emphasize that the two servers are honest-and-curious
and independent, which means that they will not collude with each other, as
well as the sender or the receiver. The above assumption is reasonable in real
life. For example, many famous public cloud providers Amazon EC2, Windows
Azure or Google Computer Engine, will not collude with each other in view of
benefit, privacy and reputation. Therefore, our server-aided oblivious transfer
model is reasonable and practical in the era of cloud computing.
2. Our proposed OT
k
n
protocol is the most efficient comparing with other pro-
tocols. The idea behind our protocol mainly benefits from the DDH-based
instantiation of the dual-mode cryptosystem presented in [24], which means
that the receiver constructs two tuples satisfying that only one is a Diffie-
Hellman tuple. We extend this (1,2)-dual-mode into a general (k,n)-dual-
mode, where the receiver constructs n tuples satisfying that only k of them
are Diffie-Hellman tuples, using the technique of oblivious polynomial eval-
uation. In detail, the receiver constructs a k-degree polynomial whose roots
are its choices and sends the k coefficients of f(x) in masked state. Then
the sender and two servers evaluate the polynomial obliviously and generate
n tuples satisfying that only k of them are Diffie-Hellman tuples. At last,
the sender transfers its own input values using the above n tuples and the
receiver can only obtain the desired k values it chooses. Furthermore, our
protocol protects the receiver’s choice against the sender and cloud servers,
and the sender’s input values which are not chosen by the receiver are still
secret to the receiver.
1.4 Organization
This paper is organized as follows. In Sect. 2 we give the problem statement
of the server-aided OT
k
n
protocol. In Sect. 3 we introduce the preliminaries and