WorksComputer Science
K-out-of-N Oblivious Transfer over Erasure Channels: Capacity and Reductions
Abstract
We study -out-of- oblivious transfer (OT) between a server and a client over a discrete memoryless channel, under an honest-but-curious model. The client must retrieve out of messages stored by the server while learning nothing about the remaining messages, and the server must not learn the client's selection. For a binary erasure channel (BEC) with parameter , we show that the -out-of- OT capacity is . This characterization generalizes the known capacity results for -out-of- OT and for -out-of- OT when . We also investigate OT reductions, specifically, we show that constructing a -out-of- OT protocol from repeating times an optimal -out-of- OT protocol can be suboptimal, but we also identify certain ranges of and for which a -out-of- OT protocol can be optimally realized via the repetition of a -out-of- OT protocol. Finally, we discuss extensions of our results to a generalized erasure channel (GEC).