betaFeedback

WorksComputer Science

K-out-of-N Oblivious Transfer over Erasure Channels: Capacity and Reductions

Abstract

We study KK-out-of-NN oblivious transfer (OT) between a server and a client over a discrete memoryless channel, under an honest-but-curious model. The client must retrieve KK out of NN messages stored by the server while learning nothing about the remaining N−KN-K messages, and the server must not learn the client's selection. For a binary erasure channel (BEC) with parameter εε, we show that the KK-out-of-NN OT capacity is min⁡(KεN−K,1−ε)\min\Big(\frac{Kε}{N-K},1-ε\Big). This characterization generalizes the known capacity results for 11-out-of-22 OT and for 11-out-of-NN OT when ε≥N−1Nε\ge\tfrac{N-1}{N}. We also investigate OT reductions, specifically, we show that constructing a KK-out-of-NN OT protocol from repeating KK times an optimal 11-out-of-NN OT protocol can be suboptimal, but we also identify certain ranges of εε and M<NM < N for which a 11-out-of-NN OT protocol can be optimally realized via the repetition of a 11-out-of-MM OT protocol. Finally, we discuss extensions of our results to a generalized erasure channel (GEC).

Paper details

vlnc:W_u44dgywj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…