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.

Problems of Information Transmission•Apr 1, 2019•6 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

Arbitrarily Varying Wiretap Channels with Non-Causal Side Information at the Jammer

Carsten Rudolf Janda, Moritz Wiese, Eduard Axel Jorswieck +1 more

Secure communication in a potentially malicious environment becomes more and more important. The arbitrarily varying wiretap channel (AVWC) provides information theoretical bounds on how much information can be exchanged even in the presence of an active attacker. If the active attacker has non-causal side information, situations in which a legitimate communication system has been hacked, can be modeled. We investigate the AVWC with non-causal side information at the jammer for the case that there exists a best channel to the eavesdropper. Non-causal side information means that the transmitted codeword is known to an active adversary before it is transmitted. By considering the maximum error criterion, we allow also messages to be known at the jammer before the corresponding codeword is transmitted. A single letter formula for the common randomness secrecy capacity is derived. Additionally, we provide a single letter formula for the common randomness secrecy capacity, for the cases that the channel to the eavesdropper is strongly degraded, strongly noisier, or strongly less capable with respect to the main channel. Furthermore, we compare our results to the random code secrecy capacity for the cases of maximum error criterion but without non-causal side information at the jammer, maximum error criterion with non-causal side information of the messages at the jammer, and the case of average error criterion without non-causal side information at the jammer.

arXiv:2001.03035•Jan 9, 2020•0 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.
Secure communication in a potentially malicious environment becomes more and more important. The arbitrarily varying wiretap channel (AVWC) provides information theoretical bounds on how much information can be exchanged even in the presence of an active attacker. If the active attacker has non-causal side information, situations in which a legitimate communication system has been hacked, can be modeled. We investigate the AVWC with non-causal side information at the jammer for the case that there exists a best channel to the eavesdropper. Non-causal side information means that the transmitted codeword is known to an active adversary before it is transmitted. By considering the maximum error criterion, we allow also messages to be known at the jammer before the corresponding codeword is transmitted. A single letter formula for the common randomness secrecy capacity is derived. Additionally, we provide a single letter formula for the common randomness secrecy capacity, for the cases that the channel to the eavesdropper is strongly degraded, strongly noisier, or strongly less capable with respect to the main channel. Furthermore, we compare our results to the random code secrecy capacity for the cases of maximum error criterion but without non-causal side information at the jammer, maximum error criterion with non-causal side information of the messages at the jammer, and the case of average error criterion without non-causal side information at the jammer.