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:2611.01678

Communication with Adversarial Users: Byzantine Models in Multi-User Information Theory

Minglai Cai, Christian Deppe, Neha Sangwan

Published Nov 1, 2026• 0 citations
arXivHTMLPDF

Abstract

We consider communication systems operating in environments where some participating users cannot be trusted. This motivates the study of Byzantine communication models, in which users may behave adversarially. In this survey, we provide a unified information-theoretic perspective on communication with adversarial users in multi-user settings. We review recent advances in Byzantine multiple access channels, including reliable communication, adversary identification, and distributed function computation. Furthermore, we discuss extensions to classical-quantum channels and highlight fundamental differences between classical and quantum models. Finally, we outline key open problems and future research directions at the intersection of communication, computation, and security.

DOI
10.48550/arxiv.2611.01678

Related papers

Byzantine Multiple Access Channels—Part I: Reliable Communication

Neha Sangwan, Mayank Bakshi, Bikash Kumar Dey +1 more

We study communication over a Multiple Access Channel (MAC) where users can possibly be adversarial. The receiver is unaware of the identity of the adversarial users (if any). When all users are non-adversarial, we want their messages to be decoded reliably. When a user behaves adversarially, we require that the honest users’ messages be decoded reliably. An adversarial user can mount an attack by sending any input into the channel rather than following the protocol. It turns out that the 2-user MAC capacity region follows from the point-to-point Arbitrarily Varying Channel (AVC) capacity. For the 3-user MAC in which at most one user may be malicious, we characterize the capacity region for deterministic codes and randomized codes (where each user shares an independent random secret key with the receiver). These results are then generalized for the$k$-user MAC where the adversary may control all users in one out of a collection of given subsets.

arXiv:2211.12769•IEEE Transactions on Information Theory•Dec 12, 2023•4 citations

Communication With Adversary Identification in Byzantine Multiple Access Channels

Neha Sangwan, Mayank Bakshi, Bikash Kumar Dey +1 more

We introduce the problem of determining the identity of a byzantine user (internal adversary) in a communication system. We consider a two-user discrete memoryless multiple access channel where either user may deviate from the prescribed behaviour. Owing to the noisy nature of the channel, it may be overly restrictive to attempt to detect all deviations. In our formulation, we only require detecting deviations which impede the decoding of the non-deviating user's message. When neither user deviates, correct decoding is required. When one user deviates, the decoder must either output a pair of messages of which the message of the non-deviating user is correct or identify the deviating user. The users and the receiver do not share any randomness. The results include a characterization of the set of channels where communication is feasible, and an inner and outer bound on the capacity region.

arXiv:2105.03380•IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•5 citations

Secure Communication Under Channel Uncertainty and Adversarial Attacks

Rafael F. Schaefer, Holger Boche, H. Vincent Poor

Information theoretic approaches to security have been examined as a promising complement to current cryptographic techniques. Such information theoretic approaches establish reliable communication and data confidentiality directly at the physical layer of a communication network by taking the properties of the noisy channel into account leading to unconditional security regardless of the computational capabilities of eavesdroppers. The provision of accurate channel state information is a major challenge particularly in wireless communication systems, especially information about the channels to eavesdroppers. In addition, there might be malevolent adversaries who jam or influence the channel of the legitimate users. This paper surveys different models for secure communication under channel uncertainty and adversarial attacks and reviews the corresponding secrecy capacity results, which characterize the maximum rate at which information can be sent to legitimate receivers while being kept perfectly security from eavesdroppers.

Proceedings of the IEEE•Aug 21, 2015•73 citations

Quantum Byzantine Multiple Access Channels

Minglai Cai, Christian Deppe

In communication theory, attacks like eavesdropping or jamming are typically assumed to occur at the channel level, while communication parties are expected to follow established protocols. But what happens if one of the parties turns malicious? In this work, we investigate a compelling scenario: a multiple-access channel with two transmitters and one receiver, where one transmitter deviates from the protocol and acts dishonestly. To address this challenge, we introduce the Byzantine multiple-access classical-quantum channel and derive an achievable communication rate for this adversarial setting.

arXiv:2502.12047•Feb 17, 2025•0 citations

Quantum One-Way Functions and Related Cryptographic Primitives

Georgios M. Nikolopoulos

Quantum cryptographic primitives beyond key distribution remain a less well understood area of research. In classical cryptography, one-way functions underpin nearly all standard cryptographic protocols, motivating the search for meaningful quantum analogues and for a clear understanding of the physical and computational mechanisms that could enforce one-wayness. In this article, we review quantum one-way functions and a range of closely related quantum-state primitives, including one-way state generators, pseudorandom quantum states, and efficiently indistinguishable pairs of states. We discuss both computational and information-theoretic notions of quantum one-wayness, emphasizing the different adversarial models and security assumptions that underlie these constructions. We compare and contrast the various proposed primitives, and clarify their conceptual relationships. Particular emphasis is placed on questions of physical realizability, experimental feasibility, and robustness to noise. Finally, we outline open problems and future directions toward the development of practical quantum cryptographic primitives beyond key distribution, and the emergence of a broader quantum-cryptographic ecosystem.

quant-pharXiv:2608.05754•New Journal of Physics•Aug 7, 2026•1 citation

Multiple Access Channels with Adversarial Users

Neha Sangwan, Mayank Bakshi, Bikash Kumar Dey +1 more

We study authenticated communication over two-user multiple access channels (MAC) where one of the users is possibly adversarial. When both users behave non-adversarially, we want their messages to be decoded reliably. However, we also want to ensure that an adversarial user cannot cause an undetected error on the other (honest) user's message. We show that the following three-phase scheme is rate-optimal: a standard MAC code is first used to achieve unauthenticated communication; this is followed by two authentication phases where each user authenticates their message treating the other user as a possible adversary. We show that the authentication phases can be very short since this form of authentication itself, when possible, can be achieved for message sets whose size grow doubly exponentially in blocklength. This leads to our result that the authenticated communication capacity region of a discrete memoryless MAC is either zero or the (unauthenticated) MAC capacity region itself. This also, arguably, explains the similar nature of authenticated communication capacity of a discrete memoryless point-to-point adversarial channel recently found by Kosut and Kliewer (ITW, 2018). We also obtain analogous results for additive Gaussian noise channels.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•13 citations
We consider communication systems operating in environments where some participating users cannot be trusted. This motivates the study of Byzantine communication models, in which users may behave adversarially. In this survey, we provide a unified information-theoretic perspective on communication with adversarial users in multi-user settings. We review recent advances in Byzantine multiple access channels, including reliable communication, adversary identification, and distributed function computation. Furthermore, we discuss extensions to classical-quantum channels and highlight fundamental differences between classical and quantum models. Finally, we outline key open problems and future research directions at the intersection of communication, computation, and security.
We study communication over a Multiple Access Channel (MAC) where users can possibly be adversarial. The receiver is unaware of the identity of the adversarial users (if any). When all users are non-adversarial, we want their messages to be decoded reliably. When a user behaves adversarially, we require that the honest users’ messages be decoded reliably. An adversarial user can mount an attack by sending any input into the channel rather than following the protocol. It turns out that the 2-user MAC capacity region follows from the point-to-point Arbitrarily Varying Channel (AVC) capacity. For the 3-user MAC in which at most one user may be malicious, we characterize the capacity region for deterministic codes and randomized codes (where each user shares an independent random secret key with the receiver). These results are then generalized for thekkk-user MAC where the adversary may control all users in one out of a collection of given subsets.
We introduce the problem of determining the identity of a byzantine user (internal adversary) in a communication system. We consider a two-user discrete memoryless multiple access channel where either user may deviate from the prescribed behaviour. Owing to the noisy nature of the channel, it may be overly restrictive to attempt to detect all deviations. In our formulation, we only require detecting deviations which impede the decoding of the non-deviating user's message. When neither user deviates, correct decoding is required. When one user deviates, the decoder must either output a pair of messages of which the message of the non-deviating user is correct or identify the deviating user. The users and the receiver do not share any randomness. The results include a characterization of the set of channels where communication is feasible, and an inner and outer bound on the capacity region.
Information theoretic approaches to security have been examined as a promising complement to current cryptographic techniques. Such information theoretic approaches establish reliable communication and data confidentiality directly at the physical layer of a communication network by taking the properties of the noisy channel into account leading to unconditional security regardless of the computational capabilities of eavesdroppers. The provision of accurate channel state information is a major challenge particularly in wireless communication systems, especially information about the channels to eavesdroppers. In addition, there might be malevolent adversaries who jam or influence the channel of the legitimate users. This paper surveys different models for secure communication under channel uncertainty and adversarial attacks and reviews the corresponding secrecy capacity results, which characterize the maximum rate at which information can be sent to legitimate receivers while being kept perfectly security from eavesdroppers.
In communication theory, attacks like eavesdropping or jamming are typically assumed to occur at the channel level, while communication parties are expected to follow established protocols. But what happens if one of the parties turns malicious? In this work, we investigate a compelling scenario: a multiple-access channel with two transmitters and one receiver, where one transmitter deviates from the protocol and acts dishonestly. To address this challenge, we introduce the Byzantine multiple-access classical-quantum channel and derive an achievable communication rate for this adversarial setting.
Quantum cryptographic primitives beyond key distribution remain a less well understood area of research. In classical cryptography, one-way functions underpin nearly all standard cryptographic protocols, motivating the search for meaningful quantum analogues and for a clear understanding of the physical and computational mechanisms that could enforce one-wayness. In this article, we review quantum one-way functions and a range of closely related quantum-state primitives, including one-way state generators, pseudorandom quantum states, and efficiently indistinguishable pairs of states. We discuss both computational and information-theoretic notions of quantum one-wayness, emphasizing the different adversarial models and security assumptions that underlie these constructions. We compare and contrast the various proposed primitives, and clarify their conceptual relationships. Particular emphasis is placed on questions of physical realizability, experimental feasibility, and robustness to noise. Finally, we outline open problems and future directions toward the development of practical quantum cryptographic primitives beyond key distribution, and the emergence of a broader quantum-cryptographic ecosystem.
We study authenticated communication over two-user multiple access channels (MAC) where one of the users is possibly adversarial. When both users behave non-adversarially, we want their messages to be decoded reliably. However, we also want to ensure that an adversarial user cannot cause an undetected error on the other (honest) user's message. We show that the following three-phase scheme is rate-optimal: a standard MAC code is first used to achieve unauthenticated communication; this is followed by two authentication phases where each user authenticates their message treating the other user as a possible adversary. We show that the authentication phases can be very short since this form of authentication itself, when possible, can be achieved for message sets whose size grow doubly exponentially in blocklength. This leads to our result that the authenticated communication capacity region of a discrete memoryless MAC is either zero or the (unauthenticated) MAC capacity region itself. This also, arguably, explains the similar nature of authenticated communication capacity of a discrete memoryless point-to-point adversarial channel recently found by Kosut and Kliewer (ITW, 2018). We also obtain analogous results for additive Gaussian noise channels.