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 Transactions on Information Theory

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

Rafael Dowsley, Anderson C. A. Nascimento

Published Aug 3, 2017• 9 citations
Publisher

Abstract

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 ).

DOI
10.1109/tit.2017.2735423

Related papers

On the Oblivious Transfer Capacity of Generalized Erasure Channels against Malicious Adversaries

Rafael Dowsley, Anderson C. A. Nascimento

Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretically 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 (\emph{ISIT'07}) presented upper and lower bounds on the OT capacity of generalized erasure channels (GEC) 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. (\emph{IEEE Trans. Inf. Theory 57(8)}) that in this case there is also a protocol against malicious adversaries achieving the same lower bound, and hence 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 work we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. In order to obtain our results we introduce a novel use of interactive hashing that is suitable for dealing with the case of low erasure probability ($p^* <1/2$).

arXiv:1410.2862•Oct 10, 2014•0 citations

Achieving Oblivious Transfer Capacity of Generalized Erasure Channels in the Malicious Model

Adriana C. B. Pinto, Rafael Dowsley, Kirill Morozov +1 more

Information-theoretically secure string oblivious transfer (OT) can be constructed based on discrete memoryless channel (DMC). The oblivious transfer capacity of a channel characterizes - similarly to the (standard) information capacity - how efficiently it can be exploited for secure oblivious transfer of strings. The OT capacity of a generalized erasure channel (GEC) - which is a combination of a (general) DMC with the erasure channel - has been established by Ahlswede and Csizar at ISIT'07 in the case of passive adversaries. In this paper, we present the protocol that achieves this capacity against malicious adversaries for GEC with erasure probability at least 1/2. Our construction is based on the protocol of Crepeau and Savvides from Eurocrypt'06 which uses interactive hashing (IH). We solve an open question posed by the above paper, by basing it upon a constant round IH scheme (previously proposed by Ding et al. at TCC'04). As a side result, we show that the Ding et al. IH protocol can deal with transmission errors.

IEEE Transactions on Information Theory•Aug 1, 2011•25 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

An Improved Lower Bound on Oblivious Transfer Capacity Using Polarization and Interaction

So Suda, Shun Watanabe

We consider the oblivious transfer (OT) capacities of noisy channels against the passive adversary; this problem has not been solved even for the binary symmetric channel (BSC). In the literature, the general construction of OT has been known only for generalized erasure channels (GECs); for the BSC, we convert the channel to the binary symmetric erasure channel (BSEC), which is a special instance of the GEC, via alphabet extension and erasure emulation. In a previous paper by the authors, we derived an improved lower bound on the OT capacity of BSC by proposing a method to recursively emulate BSEC via interactive communication. In this paper, we introduce two new ideas of OT construction: (i) via “polarization” and interactive communication, we recursively emulate GECs that are not necessarily a BSEC; (ii) in addition to the GEC emulation part, we also utilize interactive communication in the key agreement part of OT protocol. By these methods, we derive lower bounds on the OT capacity of BSC that are superior to the previous one for a certain range of crossover probabilities of the BSC. Via our new lower bound, we show that, at the crossover probability being zero, the slope of tangent of the OT capacity is unbounded.

arXiv:2501.11883•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•5 citations

Oblivious Transfer Over Compound Binary Erasure Channels

Anuj Kumar Yadav, Preetam Kumar

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.

IEEE Communications Letters•Mar 3, 2022•2 citations

On the Commitment Capacity of Unfair Noisy Channels

Claude Crépeau, Rafael Dowsley, Anderson C. A. Nascimento

Noisy channels are a valuable resource from a cryptographic point of view. They can be used for exchanging secret-keys as well as realizing other cryptographic primitives such as commitment and oblivious transfer. To be really useful, noisy channels have to be considered in the scenario where a cheating party has some degree of control over the channel characteristics. Damgård et al. (EUROCRYPT 1999) proposed a more realistic model where such level of control is permitted to an adversary, the so called unfair noisy channels, and proved that they can be used to obtain commitment and oblivious transfer protocols. Given that noisy channels are a precious resource for cryptographic purposes, one important question is determining the optimal rate in which they can be used. The commitment capacity has already been determined for the cases of discrete memoryless channels and Gaussian channels. In this work we address the problem of determining the commitment capacity of unfair noisy channels. We compute a single-letter characterization of the commitment capacity of unfair noisy channels. In the case where an adversary has no control over the channel (the fair case) our capacity reduces to the well-known capacity of a discrete memoryless binary symmetric channel.

arXiv:1905.10921•IEEE Transactions on Information Theory•Jan 17, 2020•15 citations
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 ).
Noisy channels are a powerful resource for cryptography as they can be used to obtain information-theoretically 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 (\emph{ISIT'07}) presented upper and lower bounds on the OT capacity of generalized erasure channels (GEC) 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. (\emph{IEEE Trans. Inf. Theory 57(8)}) that in this case there is also a protocol against malicious adversaries achieving the same lower bound, and hence 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 work we show that there is a protocol against malicious adversaries achieving the same OT rate that was obtained against passive adversaries. In order to obtain our results we introduce a novel use of interactive hashing that is suitable for dealing with the case of low erasure probability (p∗<1/2p^* <1/2p∗<1/2).
Information-theoretically secure string oblivious transfer (OT) can be constructed based on discrete memoryless channel (DMC). The oblivious transfer capacity of a channel characterizes - similarly to the (standard) information capacity - how efficiently it can be exploited for secure oblivious transfer of strings. The OT capacity of a generalized erasure channel (GEC) - which is a combination of a (general) DMC with the erasure channel - has been established by Ahlswede and Csizar at ISIT'07 in the case of passive adversaries. In this paper, we present the protocol that achieves this capacity against malicious adversaries for GEC with erasure probability at least 1/2. Our construction is based on the protocol of Crepeau and Savvides from Eurocrypt'06 which uses interactive hashing (IH). We solve an open question posed by the above paper, by basing it upon a constant round IH scheme (previously proposed by Ding et al. at TCC'04). As a side result, we show that the Ding et al. IH protocol can deal with transmission errors.
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.
We consider the oblivious transfer (OT) capacities of noisy channels against the passive adversary; this problem has not been solved even for the binary symmetric channel (BSC). In the literature, the general construction of OT has been known only for generalized erasure channels (GECs); for the BSC, we convert the channel to the binary symmetric erasure channel (BSEC), which is a special instance of the GEC, via alphabet extension and erasure emulation. In a previous paper by the authors, we derived an improved lower bound on the OT capacity of BSC by proposing a method to recursively emulate BSEC via interactive communication. In this paper, we introduce two new ideas of OT construction: (i) via “polarization” and interactive communication, we recursively emulate GECs that are not necessarily a BSEC; (ii) in addition to the GEC emulation part, we also utilize interactive communication in the key agreement part of OT protocol. By these methods, we derive lower bounds on the OT capacity of BSC that are superior to the previous one for a certain range of crossover probabilities of the BSC. Via our new lower bound, we show that, at the crossover probability being zero, the slope of tangent of the OT capacity is unbounded.
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.
Noisy channels are a valuable resource from a cryptographic point of view. They can be used for exchanging secret-keys as well as realizing other cryptographic primitives such as commitment and oblivious transfer. To be really useful, noisy channels have to be considered in the scenario where a cheating party has some degree of control over the channel characteristics. Damgård et al. (EUROCRYPT 1999) proposed a more realistic model where such level of control is permitted to an adversary, the so called unfair noisy channels, and proved that they can be used to obtain commitment and oblivious transfer protocols. Given that noisy channels are a precious resource for cryptographic purposes, one important question is determining the optimal rate in which they can be used. The commitment capacity has already been determined for the cases of discrete memoryless channels and Gaussian channels. In this work we address the problem of determining the commitment capacity of unfair noisy channels. We compute a single-letter characterization of the commitment capacity of unfair noisy channels. In the case where an adversary has no control over the channel (the fair case) our capacity reduces to the well-known capacity of a discrete memoryless binary symmetric channel.