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 International Symposium on Information Theory (ISIT)

On Oblivious Transfer Capacity

Rudolf Ahlswede, Imre Csiszár

Published Jun 1, 2007• 30 citations
Publisher

Abstract

The concept of oblivious transfer capacity has been recently introduced by Nascimento and Winter. We give an upper bound to this capacity, both for source and channel models, and prove that it is tight for a class of channels. For other cases, lower bounds are provided. The tools include known results on secrecy capacity of simple source and channel models.

DOI
10.1109/isit.2007.4557524

Related papers

On oblivious transfer capacity

Rudolf Ahlswede, Imre Csiszár

The concept of oblivious transfer capacity has been introduced by Nascimento and Winter, ISIT06. Its value has been determined for certain models, and bounds to it were given for other models, in the present authors' ISIT07 contribution. This talk is based on the latter work. The tools include known results on secrecy capacity of simple source and channel models.

IEEE Information Theory Workshop (ITW)•Jun 1, 2009•7 citations

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

A new upperbound for the oblivious transfer capacity of discrete memoryless channels

K. Sankeerth Rao, Vinod M. Prabhakaran

We derive a new upper bound on the string oblivious transfer capacity of discrete memoryless channels (DMCs). The main tool we use is the tension region of a pair of random variables introduced in Prabhakaran and Prabhakaran (2014) where it was used to derive upper bounds on rates of secure sampling in the source model. In this paper, we consider secure computation of string oblivious transfer in the channel model. Our bound is based on a monotonicity property of the tension region in the channel model. We show that our bound strictly improves upon the upper bound of Ahlswede and Csiszár (2013).

arXiv:1405.2049•IEEE Information Theory Workshop (ITW)•Nov 1, 2014•9 citations

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

On ObliviousTransfer Capacity

Rudolf Ahlswede

Theconcept ofoblivious transfer capacity hasbeen recently introduced byNascimento andWinter. Wegive anupper boundtothis capacity, bothforsource andchannel models, and provethatitistight fora class ofchannels. Forothercases, lowerboundsareprovided. Thetools include knownresults on secrecy capacity ofsimple source andchannel models.

•Jan 1, 2007•0 citations
The concept of oblivious transfer capacity has been recently introduced by Nascimento and Winter. We give an upper bound to this capacity, both for source and channel models, and prove that it is tight for a class of channels. For other cases, lower bounds are provided. The tools include known results on secrecy capacity of simple source and channel models.
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 derive a new upper bound on the string oblivious transfer capacity of discrete memoryless channels (DMCs). The main tool we use is the tension region of a pair of random variables introduced in Prabhakaran and Prabhakaran (2014) where it was used to derive upper bounds on rates of secure sampling in the source model. In this paper, we consider secure computation of string oblivious transfer in the channel model. Our bound is based on a monotonicity property of the tension region in the channel model. We show that our bound strictly improves upon the upper bound of Ahlswede and Csiszár (2013).
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.