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

arXiv:2401.15355 · IEEE International Symposium on Information Theory (ISIT)

Improved Bounds on the Interactive Capacity via Error Pattern Analysis

Mudit Aggarwal, Manuj Mukherjee

Published Jul 7, 2024• 1 citation
arXivHTMLPDF

Abstract

Any interactive protocol between a pair of parties can be reliably simulated in the presence of noise with a multiplicative overhead on the number of rounds (Schulman 1996). The reciprocal of the best (least) overhead is called the interactive capacity of the noisy channel. In this work, we present lower bounds on the interactive capacity of the binary erasure channel. Our lower bound improves the best-known bound due to Ben- Yishai et al. 2021 by roughly a factor of 1.75. The improvement is due to a tighter analysis of the correctness of the simulation protocol using error pattern analysis. More precisely, instead of using the well-known technique of bounding the least number of erasures needed to make the simulation fail, we identify and bound the probability of specific erasure patterns causing simulation failure. We remark that error pattern analysis can be useful in solving other problems involving stochastic noise, such as bounding the interactive capacity of different channels.

DOI
10.1109/isit57864.2024.10619345

Related papers

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 the Interactive Capacity of Finite-State Protocols

Assaf Ben-Yishai, Young-Han Kim, Rotem Oshman +1 more

The interactive capacity of a noisy channel is the highest possible rate at which arbitrary interactive protocols can be simulated reliably over the channel. Determining the interactive capacity is notoriously difficult, and the best known lower bounds are far below the associated Shannon capacity, which serves as a trivial (and also generally the best known) upper bound. This paper considers the more restricted setup of simulating finite-state protocols. It is shown that all two-state protocols, as well as rich families of arbitrary finite-state protocols, can be simulated at the Shannon capacity, establishing the interactive capacity for those families of protocols.

arXiv:2001.00499•Entropy•Dec 25, 2020•0 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

Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets

Debbie Leung, Ashwin Nayak, Ala Shayeghi +3 more

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a poly (n ) size alphabet, our main result is a simulation method that fails with probability less than 2-Θ(nϵ)and uses a qudit channel over the same alphabet n(1 + Θ(√{ϵ} )) times, of which an ϵ fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √{ϵ} term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., SICOMP'19] for low ϵ.

arXiv:2001.02818•IEEE Transactions on Information Theory•Jun 8, 2021•2 citations

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

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

IEEE Transactions on Information Theory•Aug 3, 2017•9 citations
Any interactive protocol between a pair of parties can be reliably simulated in the presence of noise with a multiplicative overhead on the number of rounds (Schulman 1996). The reciprocal of the best (least) overhead is called the interactive capacity of the noisy channel. In this work, we present lower bounds on the interactive capacity of the binary erasure channel. Our lower bound improves the best-known bound due to Ben- Yishai et al. 2021 by roughly a factor of 1.75. The improvement is due to a tighter analysis of the correctness of the simulation protocol using error pattern analysis. More precisely, instead of using the well-known technique of bounding the least number of erasures needed to make the simulation fail, we identify and bound the probability of specific erasure patterns causing simulation failure. We remark that error pattern analysis can be useful in solving other problems involving stochastic noise, such as bounding the interactive capacity of different channels.
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.
The interactive capacity of a noisy channel is the highest possible rate at which arbitrary interactive protocols can be simulated reliably over the channel. Determining the interactive capacity is notoriously difficult, and the best known lower bounds are far below the associated Shannon capacity, which serves as a trivial (and also generally the best known) upper bound. This paper considers the more restricted setup of simulating finite-state protocols. It is shown that all two-state protocols, as well as rich families of arbitrary finite-state protocols, can be simulated at the Shannon capacity, establishing the interactive capacity for those families of protocols.
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.
We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a poly (n ) size alphabet, our main result is a simulation method that fails with probability less than 2-Θ(nϵ)and uses a qudit channel over the same alphabet n(1 + Θ(√{ϵ} )) times, of which an ϵ fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √{ϵ} term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., SICOMP'19] for low ϵ.
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).
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 ).