K-out-of-N Oblivious Transfer over Erasure Channels: Capacity and Reductions
We study $K$-out-of-$N$ oblivious transfer (OT) between a server and a client over a discrete memoryless channel, under an honest-but-curious model. The client must retrieve $K$ out of $N$ messages stored by the server while learning nothing about the remaining $N-K$ messages, and the server must not learn the client's selection. For a binary erasure channel (BEC) with parameter $ε$, we show that the $K$-out-of-$N$ OT capacity is $\min\Big(\frac{Kε}{N-K},1-ε\Big)$. This characterization generalizes the known capacity results for $1$-out-of-$2$ OT and for $1$-out-of-$N$ OT when $ε\ge\tfrac{N-1}{N}$. We also investigate OT reductions, specifically, we show that constructing a $K$-out-of-$N$ OT protocol from repeating $K$ times an optimal $1$-out-of-$N$ OT protocol can be suboptimal, but we also identify certain ranges of $ε$ and $M < N$ for which a $1$-out-of-$N$ OT protocol can be optimally realized via the repetition of a $1$-out-of-$M$ OT protocol. Finally, we discuss extensions of our results to a generalized erasure channel (GEC).
Authors
- Rémi A. Chou (ORCID: https://orcid.org/0000-0003-4431-3175)
- Amirhossein Shekofteh
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.48550/arxiv.2611.21359
- Primary Topic
- Cryptography and Data Security
- Type
- preprint