Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Communications Letters

Oblivious Transfer Over Compound Binary Erasure Channels

Anuj Kumar Yadav, Preetam Kumar

Published Mar 3, 2022• 2 citations
Publisher

Abstract

Oblivious Transfer (OT) is a broadly studied cryptographic primitive which involves two mutually distrustful users who wish to interact with each other in order to transfer messages in an oblivious manner. Noise is an important resource to realize information-theoretically secure cryptographic protocols including oblivious transfer. However, oftentimes these noisy channels may be poorly characterized and the complete channel characteristics might be unknown to both users. Such channels are studied in the literature through the lens of compound channels. We study 1-out-of-2 oblivious transfer over a compound binary erasure channel (compound-BEC) and characterize the oblivious transfer capacity of compound-BEC. Our OT capacity characterization involves a general alphabet compound-DMC converse, subsequently specialized to compound-BEC along with an optimal and computationally-efficient achievability scheme for honest-but-curious users.

DOI
10.1109/lcomm.2022.3156704

Related papers

On the Oblivious Transfer Capacity of the Erasure Channel

Hideki Imai, Kirill Morozov, Anderson C. A. Nascimento

One of the most important primitives in two-party distrustful cryptography is oblivious transfer, a complete primitive for two-party computation. Recently introduced, the oblivious transfer capacity of a noisy channel measures an efficiency of information theoretical reductions from 1-out-of-k, l-string oblivious transfer to noisy channels. It is defined as the maximal achievable ratio l/n, where l is the length of the strings which are to be transferred and n is the number of times the noisy channel is invoked. This quantity is unknown in a general case. For discrete memoryless channels, it is known to be nonnegligible for honest-but-curious players, but the non-zero rates have not ever been proved achievable in the case of malicious players. Here, we show that in the particular case of the erasure channel, more precise answers can be obtained. We compute the OT capacity of the erasure channel for the case of honest-but-curious players and, for the fully malicious players, we give its lower bound.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•36 citations

Capacity of K-out-of-N Oblivious Transfer over the Binary Erasure Channel

Amirhossein Shekofteh, Rémi A. Chou

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•1 citation

On the Oblivious Transfer Capacity of Generalized Erasure Channels Against Malicious Adversaries: The Case of Low Erasure Probability

Rafael Dowsley, Anderson C. A. Nascimento

Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretic secure key agreement, commitment, and oblivious transfer protocols, among others. Oblivious transfer (OT) is a fundamental primitive, since it is complete for secure multi-party computation, and the OT capacity characterizes how efficiently a channel can be used for obtaining string oblivious transfer. Ahlswede and Csiszár (ISIT'07) presented upper and lower bounds on the OT capacity of generalized erasure channels (GECs) against passive adversaries. In the case of GEC with erasure probability at least 1/2, the upper and lower bounds match and, therefore, the OT capacity was determined. It was later proved by Pinto et al. [IEEE Trans. Inf. Theory 57(8)] that the OT capacity is identical for passive and malicious adversaries. In the case of GEC with erasure probability smaller than 1/2, the known lower bound against passive adversaries that was established by Ahlswede and Csiszár does not match their upper bound and it was unknown whether this OT rate could be achieved against malicious adversaries as well. In this paper, we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. We obtain our results by a new combination of interactive hashing and typicality tests that are suitable for dealing with the case of low erasure probability (p* <;1/2 ).

arXiv:1410.2862•IEEE Transactions on Information Theory•Aug 3, 2017•10 citations

An Improved Lower Bound on Oblivious Transfer Capacity via Interactive Erasure Emulation

So Suda, Shun Watanabe, Haruya Yamaguchi

We revisit the oblivious transfer (OT) capacities of noisy channels against the passive adversary, which have been identified only for a limited class of channels. In the literature, the general construction of oblivious transfer has been known only for generalized erasure channels (GECs); for other channels, we first convert a given channel to a GEC via alphabet extension and erasure emulation, and then apply the general construction for GEC. In this paper, we derive an improved lower bound on the OT capacity of the binary symmetric channel (BSC) and binary symmetric erasure channel (BSEC) by proposing a new protocol; by using interactive communication between the sender and the receiver, our protocol emulates erasure events recursively in multiple rounds. We also discuss a potential necessity of multiple rounds interactive communication to attain the OT capacity.

arXiv:2401.14965•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•4 citations

Commitment over Compound Binary Symmetric Channels

Anuj Kumar Yadav, Manideep Mamindlapally, Amitalok J. Budkuley +1 more

In the commitment problem, two mutually distrustful parties Alice and Bob interact in a two-phase protocol, viz., commit and reveal phase, to achieve commitment over a bit string that Alice possesses. The protocol successfully achieves commitment if, firstly, Alice can commit to sharing a string with Bob, with the guarantee that this string remains hidden from Bob until she chooses to reveal it to him. Secondly, when Alice does reveal a string, Bob is able to detect precisely whether the revealed string is different from the one Alice committed to sharing. Information-theoretically secure commitment is impossible if Alice and Bob communicate only noiselessly; however, communication using a noisy channel can be a resource to realize commitment. Even though a noisy channel may be available, it is possible that the corresponding channel law is imprecisely known or poorly characterized. We define and study a compound-binary symmetric channel (compound-BSC) which models such a scenario. A compound-BSC is a BSC whose transition probability is fixed but unknown to either party; the set of potential values which this transition probability can take, though, is known to both parties a priori. In this work, we completely characterize the maximum commitment throughput or commitment capacity of a compound-BSC. We provide an optimal, computationally-efficient scheme for our achievability, and we derive a converse for general alphabet compound DMCs, which is then specialized for compound-BSCs.

National Conference on Communications•Jul 27, 2021•8 citations

On the oblivious transfer capacity region of the binary erasure broadcast channel

Manoj Mishra, Bikash Kumar Dey, Vinod M. Prabhakaran +1 more

We study oblivious transfer (OT) using a binary erasure broadcast channel from Alice to Bob and Charlie. Alice wants to establish independent OTs with Bob and Charlie with 2-privacy, i.e., where secrecy needs to be maintained even against pairs of parties in addition to against parties working on their own. We give an achievable rate-region in the honest-but-curious setting and show its optimality for a range of erasure probabilities.

IEEE Information Theory Workshop (ITW)•Nov 1, 2014•6 citations
Oblivious Transfer (OT) is a broadly studied cryptographic primitive which involves two mutually distrustful users who wish to interact with each other in order to transfer messages in an oblivious manner. Noise is an important resource to realize information-theoretically secure cryptographic protocols including oblivious transfer. However, oftentimes these noisy channels may be poorly characterized and the complete channel characteristics might be unknown to both users. Such channels are studied in the literature through the lens of compound channels. We study 1-out-of-2 oblivious transfer over a compound binary erasure channel (compound-BEC) and characterize the oblivious transfer capacity of compound-BEC. Our OT capacity characterization involves a general alphabet compound-DMC converse, subsequently specialized to compound-BEC along with an optimal and computationally-efficient achievability scheme for honest-but-curious users.
One of the most important primitives in two-party distrustful cryptography is oblivious transfer, a complete primitive for two-party computation. Recently introduced, the oblivious transfer capacity of a noisy channel measures an efficiency of information theoretical reductions from 1-out-of-k, l-string oblivious transfer to noisy channels. It is defined as the maximal achievable ratio l/n, where l is the length of the strings which are to be transferred and n is the number of times the noisy channel is invoked. This quantity is unknown in a general case. For discrete memoryless channels, it is known to be nonnegligible for honest-but-curious players, but the non-zero rates have not ever been proved achievable in the case of malicious players. Here, we show that in the particular case of the erasure channel, more precise answers can be obtained. We compute the OT capacity of the erasure channel for the case of honest-but-curious players and, for the fully malicious players, we give its lower bound.
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⁡(KεN−K,1−ε).C = \min \left({\frac{{K\varepsilon }}{{N - K}},1 - \varepsilon }\right).C=min(N−KKε​,1−ε). 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.
Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretic secure key agreement, commitment, and oblivious transfer protocols, among others. Oblivious transfer (OT) is a fundamental primitive, since it is complete for secure multi-party computation, and the OT capacity characterizes how efficiently a channel can be used for obtaining string oblivious transfer. Ahlswede and Csiszár (ISIT'07) presented upper and lower bounds on the OT capacity of generalized erasure channels (GECs) against passive adversaries. In the case of GEC with erasure probability at least 1/2, the upper and lower bounds match and, therefore, the OT capacity was determined. It was later proved by Pinto et al. [IEEE Trans. Inf. Theory 57(8)] that the OT capacity is identical for passive and malicious adversaries. In the case of GEC with erasure probability smaller than 1/2, the known lower bound against passive adversaries that was established by Ahlswede and Csiszár does not match their upper bound and it was unknown whether this OT rate could be achieved against malicious adversaries as well. In this paper, we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. We obtain our results by a new combination of interactive hashing and typicality tests that are suitable for dealing with the case of low erasure probability (p* <;1/2 ).
We revisit the oblivious transfer (OT) capacities of noisy channels against the passive adversary, which have been identified only for a limited class of channels. In the literature, the general construction of oblivious transfer has been known only for generalized erasure channels (GECs); for other channels, we first convert a given channel to a GEC via alphabet extension and erasure emulation, and then apply the general construction for GEC. In this paper, we derive an improved lower bound on the OT capacity of the binary symmetric channel (BSC) and binary symmetric erasure channel (BSEC) by proposing a new protocol; by using interactive communication between the sender and the receiver, our protocol emulates erasure events recursively in multiple rounds. We also discuss a potential necessity of multiple rounds interactive communication to attain the OT capacity.
In the commitment problem, two mutually distrustful parties Alice and Bob interact in a two-phase protocol, viz., commit and reveal phase, to achieve commitment over a bit string that Alice possesses. The protocol successfully achieves commitment if, firstly, Alice can commit to sharing a string with Bob, with the guarantee that this string remains hidden from Bob until she chooses to reveal it to him. Secondly, when Alice does reveal a string, Bob is able to detect precisely whether the revealed string is different from the one Alice committed to sharing. Information-theoretically secure commitment is impossible if Alice and Bob communicate only noiselessly; however, communication using a noisy channel can be a resource to realize commitment. Even though a noisy channel may be available, it is possible that the corresponding channel law is imprecisely known or poorly characterized. We define and study a compound-binary symmetric channel (compound-BSC) which models such a scenario. A compound-BSC is a BSC whose transition probability is fixed but unknown to either party; the set of potential values which this transition probability can take, though, is known to both parties a priori. In this work, we completely characterize the maximum commitment throughput or commitment capacity of a compound-BSC. We provide an optimal, computationally-efficient scheme for our achievability, and we derive a converse for general alphabet compound DMCs, which is then specialized for compound-BSCs.