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:2512.02869 · Globecom

Detecting Symmetrizability in Physical Systems

Florian Seitz, Janis Nötzel

quant-phSubmitted Dec 2, 2025• Announced Dec 3, 2025• 1 citation
arXivHTMLPDF

Abstract

We study the problem of data transmission under the influence of a jammer, which is typical for wireless systems and commonly modeled as an arbitrarily varying channel (AVC) in information theory. AVC fulfilling a certain set of linear equations are called symmetrizable and are known to be prone to denial of service attacks. Recent work has shown that deciding if a given AVC is symmetrizable or not is a non-Turing computable problem. By relaxing the formulation of symmetrizability, we show the existence of a polynomial-time algorithm that determines whether a given AVC is non-symmetrizable, but displays a critical dependence on the number of jammer input states. We then show how imposing an energy constraint on the jammer allows the same algorithm to efficiently identify large classes of AVCs which are non-symmetrizable.

Comments
6 pages, 3 figures

Related papers

Reliable Communication under the Influence of a State-Constrained Jammer: An Information-Theoretic Perspective on Receive Diversity

C. Arendt, Janis Nötzel, Holger Boche

The impact of diversity on reliable communication over arbitrarily varying channels (AVC) is investigated as follows. First, the concept of an identical state-constrained jammer is motivated. Second, it is proved that symmetrizability of binary symmetric AVCs (AVBSC) caused by identical state-constrained jamming is circumvented when communication takes place over at least three orthogonal channels. Third, it is proved that the deterministic capacity of the identical state-constrained AVBSC is continuous and shows super-activation. This effect was hitherto demonstrated only for quantum communication and for classical communication under secrecy constraints.

arXiv:1710.10811•Problems of Information Transmission•Apr 1, 2019•7 citations

Detectability of Denial-of-Service Attacks on Arbitrarily Varying Classical-Quantum Channels

Holger Boche, Minglai Cai, H. Vincent Poor +1 more

Communication systems are subject to adversarial attacks since malevolent adversaries might harm and disrupt legitimate transmissions intentionally. Of particular interest in this paper are so-called denial-of-service (DoS) attacks in which the jammer completely prevents any transmission. Arbitrarily varying classical-quantum channels, providing a suitable model to capture the jamming attacks of interest, are studied. Algorithmic detection frameworks are developed based on Turing machines and also Blum-Shub-Smale (BSS) machines, where the latter can process and store arbitrary real numbers. It is shown that Turing machines are not capable of detecting DoS attacks. However, BSS machines are capable thereof implying that real number signal processing enables the algorithmic detection of DoS attacks.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•6 citations

Entanglement Enabled Data Transmission over an Arbitrarily Varying Channel

Janis Nötzel, Florian Seitz

Shared randomness is the central ingredient for stabilizing symmetrizable communication systems against arbitrarily varying jammers. Given the presence of the jammer, however, the question arises how this precious resource could have been distributed. Several works discuss the use of external sources for this task. In this work, we show, based on the most standard optical communication model, how the sender and receiver can employ entangled two-mode squeezed states to counter the jamming attack of an energy-limited jammer during the distribution phase when both the sender and jammer are allowed to use binary phase shift keying and two-mode squeezed vacuum states.

quant-pharXiv:2605.00132•IEEE International Symposium on Information Theory (ISIT)•May 4, 2026•0 citations

The arbitrarily varying channel when the jammer knows the channel input

Ning Cai, Terence Chan, Alex J. Grant

The arbitrarily varying channel can be modeled as communication in the presence of a jammer. In this paper we propose a new model: a jammer who knows the channel input, and where the transmitter and receiver share a secret random key. Shared randomness differentiates this scenario from the case where the jammer knows the message. For sufficiently large key rate, we determine the capacity of this channel (which may be strictly smaller than the case where the jammer knows only the message). We also provide an upper bound on the minimum key rate required to achieve capacity. We prove that additionally revealing the message to the jammer does not change the capacity, provided the key rate is sufficiently large. This new capacity result differs from existing results for the AVC, and in fact coincides with a well-known upper bound on the deterministic coding capacity of the AVC with maximum error. Without secret keys, our problem degenerates to deterministic coding for the AVC with maximum probability of error, a well-known hard problem. Our results demonstrate that knowledge of the channel input is better than knowledge of the message for the jammer.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•6 citations

List decoding for arbitrarily varying wiretap channels

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer

We consider a communication scenario in which the channel undergoes two different classes of attacks at the same time: a passive eavesdropper and an active jammer. This scenario is modeled by the concept of arbitrarily varying wiretap channels (AVWCs), in which the channel varies from one channel use to the other in an unknown and arbitrary manner. It has been shown that uncorrelated codes fail to establish reliable communication over the class of symmetrizable AVWCs. For this class more sophisticated coding techniques such as correlated random codes are needed. Correlated random codes are not easy to realize in practice because they require a sort of coordination between the transmitter and the receiver, which is not always possible. In this paper, we aim to resolve the ambiguity of symmetrizable AVWCs in the absence of coordination resources using list decoding. In particular, we show that for an AVWC where we allow for a non-vanishing decoding error probability, we can construct a list code whose rate is close to the correlated secrecy capacity. The list size needed by such code is shown to be finite and independent of the block length. Moreover, the constructed list code assures that the information leakage of the confidential message with respect to the strong secrecy criterion decays exponentially fast.

IEEE Conference on Communications and Network Security•Oct 1, 2016•4 citations

The secrecy capacity of the arbitrarily varying wiretap channel under list decoding

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer

We consider a communication scenario in which the channel undergoes two different classes of attacks at the same time: a passive eavesdropper and an active jammer. This scenario is modelled by the concept of arbitrarily varying wiretap channels (AVWCs). In this paper, we derive a full characterization of the list secrecy capacity of the AVWC, showing that the list secrecy capacity is equivalent to the correlated random secrecy capacity if the list size L is greater than the order of symmetrizability of the AVC between the transmitter and the legitimate receiver. Otherwise, it is zero. Our result indicates that for a sufficiently large list size L, list codes can overcome the drawbacks of correlated and uncorrelated codes and provide a stable secrecy capacity for AVWCs. Furthermore, we investigate the effect of relaxing the reliability and secrecy constraints by allowing a non-vanishing error probability and information leakage on the list size L. We found that we can construct a list code whose rate is close to the correlated secrecy capacity using a finite list size L that only depends on the average error probability requested. Finally, we point out that our capacity characterization is an important step in investigating the analytical properties of the capacity function such as: the continuity behavior, Turing computability and super-activation of parallel AVWCs.

Advances in Mathematics of Communications•Dec 19, 2018•2 citations
We study the problem of data transmission under the influence of a jammer, which is typical for wireless systems and commonly modeled as an arbitrarily varying channel (AVC) in information theory. AVC fulfilling a certain set of linear equations are called symmetrizable and are known to be prone to denial of service attacks. Recent work has shown that deciding if a given AVC is symmetrizable or not is a non-Turing computable problem. By relaxing the formulation of symmetrizability, we show the existence of a polynomial-time algorithm that determines whether a given AVC is non-symmetrizable, but displays a critical dependence on the number of jammer input states. We then show how imposing an energy constraint on the jammer allows the same algorithm to efficiently identify large classes of AVCs which are non-symmetrizable.
The impact of diversity on reliable communication over arbitrarily varying channels (AVC) is investigated as follows. First, the concept of an identical state-constrained jammer is motivated. Second, it is proved that symmetrizability of binary symmetric AVCs (AVBSC) caused by identical state-constrained jamming is circumvented when communication takes place over at least three orthogonal channels. Third, it is proved that the deterministic capacity of the identical state-constrained AVBSC is continuous and shows super-activation. This effect was hitherto demonstrated only for quantum communication and for classical communication under secrecy constraints.
Communication systems are subject to adversarial attacks since malevolent adversaries might harm and disrupt legitimate transmissions intentionally. Of particular interest in this paper are so-called denial-of-service (DoS) attacks in which the jammer completely prevents any transmission. Arbitrarily varying classical-quantum channels, providing a suitable model to capture the jamming attacks of interest, are studied. Algorithmic detection frameworks are developed based on Turing machines and also Blum-Shub-Smale (BSS) machines, where the latter can process and store arbitrary real numbers. It is shown that Turing machines are not capable of detecting DoS attacks. However, BSS machines are capable thereof implying that real number signal processing enables the algorithmic detection of DoS attacks.
Shared randomness is the central ingredient for stabilizing symmetrizable communication systems against arbitrarily varying jammers. Given the presence of the jammer, however, the question arises how this precious resource could have been distributed. Several works discuss the use of external sources for this task. In this work, we show, based on the most standard optical communication model, how the sender and receiver can employ entangled two-mode squeezed states to counter the jamming attack of an energy-limited jammer during the distribution phase when both the sender and jammer are allowed to use binary phase shift keying and two-mode squeezed vacuum states.
The arbitrarily varying channel can be modeled as communication in the presence of a jammer. In this paper we propose a new model: a jammer who knows the channel input, and where the transmitter and receiver share a secret random key. Shared randomness differentiates this scenario from the case where the jammer knows the message. For sufficiently large key rate, we determine the capacity of this channel (which may be strictly smaller than the case where the jammer knows only the message). We also provide an upper bound on the minimum key rate required to achieve capacity. We prove that additionally revealing the message to the jammer does not change the capacity, provided the key rate is sufficiently large. This new capacity result differs from existing results for the AVC, and in fact coincides with a well-known upper bound on the deterministic coding capacity of the AVC with maximum error. Without secret keys, our problem degenerates to deterministic coding for the AVC with maximum probability of error, a well-known hard problem. Our results demonstrate that knowledge of the channel input is better than knowledge of the message for the jammer.
We consider a communication scenario in which the channel undergoes two different classes of attacks at the same time: a passive eavesdropper and an active jammer. This scenario is modeled by the concept of arbitrarily varying wiretap channels (AVWCs), in which the channel varies from one channel use to the other in an unknown and arbitrary manner. It has been shown that uncorrelated codes fail to establish reliable communication over the class of symmetrizable AVWCs. For this class more sophisticated coding techniques such as correlated random codes are needed. Correlated random codes are not easy to realize in practice because they require a sort of coordination between the transmitter and the receiver, which is not always possible. In this paper, we aim to resolve the ambiguity of symmetrizable AVWCs in the absence of coordination resources using list decoding. In particular, we show that for an AVWC where we allow for a non-vanishing decoding error probability, we can construct a list code whose rate is close to the correlated secrecy capacity. The list size needed by such code is shown to be finite and independent of the block length. Moreover, the constructed list code assures that the information leakage of the confidential message with respect to the strong secrecy criterion decays exponentially fast.
We consider a communication scenario in which the channel undergoes two different classes of attacks at the same time: a passive eavesdropper and an active jammer. This scenario is modelled by the concept of arbitrarily varying wiretap channels (AVWCs). In this paper, we derive a full characterization of the list secrecy capacity of the AVWC, showing that the list secrecy capacity is equivalent to the correlated random secrecy capacity if the list size L is greater than the order of symmetrizability of the AVC between the transmitter and the legitimate receiver. Otherwise, it is zero. Our result indicates that for a sufficiently large list size L, list codes can overcome the drawbacks of correlated and uncorrelated codes and provide a stable secrecy capacity for AVWCs. Furthermore, we investigate the effect of relaxing the reliability and secrecy constraints by allowing a non-vanishing error probability and information leakage on the list size L. We found that we can construct a list code whose rate is close to the correlated secrecy capacity using a finite list size L that only depends on the average error probability requested. Finally, we point out that our capacity characterization is an important step in investigating the analytical properties of the capacity function such as: the continuity behavior, Turing computability and super-activation of parallel AVWCs.