Oblivious Transfer - 1-out-of-n Oblivious Transfer and K-out-of-n Oblivious Transfer

1-out-of-n Oblivious Transfer and K-out-of-n Oblivious Transfer

A 1-out-of-n oblivious transfer protocol can be defined as a natural generalization of a 1-out-of-2 oblivious transfer protocol. Specifically, a sender has n messages, and the receiver has an index i, and the receiver wishes to receive the i-th among the sender's messages, without the sender learning i, while the sender wants to ensure that the receiver receive only one of the n messages.

1-out-of-n oblivious transfer is incomparable to private information retrieval (PIR). On the one hand, 1-out-of-n oblivious transfer imposes an additional privacy requirement for the database: namely, that the receiver learn at most one of the database entries. On the other hand, PIR requires communication sublinear in n, whereas 1-out-of-n oblivious transfer has no such requirement.

1-n oblivious transfer protocols were proposed, e.g., by Moni Naor and Benny Pinkas, William Aiello, Yuval Ishai and Omer Reingold, Sven Laur and Helger Lipmaa .

Brassard, Crépeau and Robert further generalized this notion to k-n oblivious transfer5, wherein the receiver obtains a set of "k" messages from the "n" message collection. The set of k messages may be received simultaneously ("non-adaptively"), or they may be requested consecutively, with each request based on previous messages received6.