IEEE International Symposium on Information Theory (ISIT)
Capacity of K-out-of-N Oblivious Transfer over the Binary Erasure Channel
Amirhossein Shekofteh, Rémi A. Chou
Abstract
We study K-out-of-N oblivious transfer (OT) over a binary erasure channel (BEC) and a public noiseless channel, under an honest-but-curious model. In this setting, a client retrieves K out of N messages stored by a server; the protocol must guarantee that the unselected messages remain private to the server and that the client’s choices remain hidden from the server. We show that the K-out-of-N OT capacity over a BEC with erasure probability ϵ is $C = \min \left({\frac{{K\varepsilon }}{{N - K}},1 - \varepsilon }\right).$ This characterization recovers the known capacity for 1-out-of-2 OT and, for 1-out-of-N OT, recovers the established capacity when $\frac{{N - 1}}{N} \leq \varepsilon $ while further establishing the capacity for all ϵ ∈ [0,1]. We also show that the naive K-out-of-N OT construction obtained by repeating an optimal 1-out-of-N OT protocol K times is suboptimal.