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

Authentication Against a Myopic Adversary

Mayank Bakshi, Allison Beemer, Oliver Kosut, Eric Graves, Jörg Kliewer, Paul L. Yu

Published Jan 10, 2020• 0 citations
arXivHTMLPDF

Abstract

We consider keyless authentication for point-to-point communication in the presence of a myopic adversary. In particular, the adversary has access to a non-causal noisy version of the transmission and uses this knowledge to choose the state of an arbitrarily-varying channel between legitimate users. The receiver succeeds by either decoding accurately or correctly detecting adversarial interference. We introduce a single-letter channel condition called $U$-distribution overwritability, and show that as long as the channel does not satisfy this condition, the authentication capacity with stochastic coding is positive and equals the no-adversary channel capacity. Our encoding scheme relies on authentication tags that allow verifying the correctness of a message that has already been received. We provide multi-letter extensions of $U$-distribution overwritability and show that the infinite letter limit yields exact characterization for positivity of authentication capacity. Noting that this characterization may, in general, be uncomputable, we next provide a single-letter channel condition called $U$-overwritability and show that it is a sufficient condition for zero authentication capacity. When restricted to deterministic codes, we show that when the channel is not $I$-overwritable, the authentication capacity is strictly positive. Further, when the channel to the legitimate receiver is degraded with respect to the channel to the adversary, $I$-overwritability is also a sufficient condition for the deterministic authentication capacity to equal zero. Lastly, we give examples demonstrating that the various notions of overwritability presented in this paper differ from each other. Our results also show that stochastic encoders are necessary for positive authentication capacity in some cases. Illustrating this, we examine in detail a binary adversarial channel that illustrates this necessity.

DOI
10.48550/arxiv.2001.03593

Related papers

Authentication Against a Myopic Adversary

Allison Beemer, Oliver Kosut, Jörg Kliewer +2 more

We consider keyless authentication for point-to-point communication in the presence of a myopic adversary. In particular, the adversary has access to a non-causal noisy version of the transmission and may use this knowledge to choose a channel state; the receiver is successful if it either decodes to the correct message or correctly detects adversarial interference. We show that, depending on the relationship between the channels to the legitimate receiver and the adversary, the authentication capacity is either zero or bounded above by the no-adversary capacity. To this end we introduce a novel channel property, termed U -overwritability, which allows the adversary to make its false message appear legitimate. We conjecture that if the capacity is nonzero, it is in fact equal to the no-adversary capacity, and show that this is true for a particular binary model.

IEEE Conference on Communications and Network Security•Jun 1, 2019•9 citations

Authentication with Mildly Myopic Adversaries

Allison Beemer, Eric Graves, Jörg Kliewer +2 more

In unsecured communications settings, ascertaining the trustworthiness of received information, called authentication, is paramount. We consider keyless authentication over an arbitrarily-varying channel, where channel states are chosen by a malicious adversary with access to noisy versions of transmitted sequences. We have shown previously that a channel condition termed U-overwritability is a sufficient condition for zero authentication capacity over such a channel, and also that with a deterministic encoder, a sufficiently clear-eyed adversary is essentially omniscient. In this paper, we show that even if the authentication capacity with a deterministic encoder and an essentially omniscient adversary is zero, allowing a stochastic encoder can result in a positive authentication capacity. Furthermore, the authentication capacity with a stochastic encoder can be equal to the no-adversary capacity of the underlying channel in this case. We illustrate this for a binary channel model, which provides insight into the more general case.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•4 citations

On Authentication against a Myopic Adversary using Stochastic Codes

Mayank Bakshi, Oliver Kosut

We consider the problem of authenticated communication over a discrete arbitrarily varying channel where the legitimate parties are unaware of whether or not an adversary is present. When there is no adversary, the channel state always takes a default value ∅. When the adversary is present, they may choose the channel state sequence based on a non-causal noisy view of the transmitted codewords and the encoding and decoding scheme. We require that the decoder output the correct message with a high probability when there is no adversary, and either output the correct message or reject the transmission when the adversary is present. Further, we allow the transmitter to employ private randomness during encoding that is known neither to the receiver nor the adversary. Our first result proves a dichotomy property for the capacity for this problem – the capacity either equals zero or it equals the non-adversarial capacity of the channel. Next, we give a sufficient condition for the capacity for this problem to be positive even when the non-adversarial channel to the receiver is stochastically degraded with respect to the channel to the adversary. Our proofs rely on a connection to a standalone authentication problem, where the goal is to accept or reject a candidate message that is already available to the decoder. Finally, we give examples and compare our sufficient condition with other related conditions known in the literature.

arXiv:2305.07292•IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•1 citation

Authentication Capacity of Adversarial Channels

Oliver Kosut, Jörg Kliewer

Keyless authentication is considered in an adversarial point-to-point channel. Namely, a legitimate transmitter and receiver aim to communicate over a noisy channel that may or may not also contain an active adversary, capable of transmitting an arbitrary signal into the channel. If the adversary is not present, then the receiver must successfully decode the message with high probability; if it is present, then the receiver must either decode the message or detect the adversary's presence. Thus, whenever the receiver decodes, it can be certain that the decoded message is authentic. The exact authentication capacity is characterized for discrete-memoryless adversary channels, where the adversary is assumed to know the code but not the message. The authentication capacity is shown to be either zero or equal to the no-adversary capacity, depending on whether the channel satisfies a condition termed overwritability.

IEEE Information Theory Workshop (ITW)•Nov 1, 2018•25 citations

Keyless Authentication and Authenticated Capacity

Wenwen Tu, Lifeng Lai

We consider the problem of keyless message authentication over noisy channels in the presence of an active adversary. Different from the existing models, in our model, the legitimate users do not have any pre-shared key for authentication. Instead, we use the noisy channel connecting the legitimate users for authentication. The main idea is to utilize the noisy channel connecting the legitimate users to distinguish a legitimate message from a fake message, by generating an output at the receiver that is difficult for the adversary to replicate through its noisy channel. By interpreting the message authentication as a hypothesis testing problem, we investigate the authentication exponent and the authenticated channel capacity of the noisy channel. In the authentication exponent problem, for a given message rate, we investigate the speed at which the optimal successful attack probability can be driven to zero. We fully characterize the authentication exponent for the zero-rate message case and provide both an upper bound and a lower bound on the exponent for the non-zero message rate case. In the authenticated capacity problem, we study the largest data transmission rate under which the attacker's optimal successful attack probability can still be made arbitrarily small. We establish an all or nothing result. In particular, we show that the authenticated channel capacity is the same as the classic channel capacity if a simulatability condition is not satisfied, while the authenticated capacity will be zero if this condition is satisfied. We also provide efficient algorithms to check this condition. We further show that our results are robust to modeling uncertainties about the eavesdropper's channels.

IEEE Transactions on Information Theory•Feb 26, 2018•26 citations

Authentication and Partial Message Correction over Adversarial Multiple-Access Channels

Allison Beemer, Eric Graves, Jörg Kliewer +2 more

In this paper, we present results on the authentication capacity region for the two-user arbitrarily-varying multipleaccess channel. We first consider a standard definition of authentication, in which the receiver may discard both messages if an adversary is detected. For this setting, we show that an extension of the arbitrarily-varying channel condition overwritability characterizes the authentication capacity region. We then define γ-correcting authentication, where we require that at least a γ fraction of the users' messages be correctable, even in the presence of an adversary. We give necessary conditions for the γ-correcting authentication capacity region to have nonempty interior, and show that positive rate pairs are achievable over a particular channel that satisfies these conditions.

IEEE Conference on Communications and Network Security•Jun 1, 2020•8 citations
We consider keyless authentication for point-to-point communication in the presence of a myopic adversary. In particular, the adversary has access to a non-causal noisy version of the transmission and uses this knowledge to choose the state of an arbitrarily-varying channel between legitimate users. The receiver succeeds by either decoding accurately or correctly detecting adversarial interference. We introduce a single-letter channel condition called UUU-distribution overwritability, and show that as long as the channel does not satisfy this condition, the authentication capacity with stochastic coding is positive and equals the no-adversary channel capacity. Our encoding scheme relies on authentication tags that allow verifying the correctness of a message that has already been received. We provide multi-letter extensions of UUU-distribution overwritability and show that the infinite letter limit yields exact characterization for positivity of authentication capacity. Noting that this characterization may, in general, be uncomputable, we next provide a single-letter channel condition called UUU-overwritability and show that it is a sufficient condition for zero authentication capacity. When restricted to deterministic codes, we show that when the channel is not III-overwritable, the authentication capacity is strictly positive. Further, when the channel to the legitimate receiver is degraded with respect to the channel to the adversary, III-overwritability is also a sufficient condition for the deterministic authentication capacity to equal zero. Lastly, we give examples demonstrating that the various notions of overwritability presented in this paper differ from each other. Our results also show that stochastic encoders are necessary for positive authentication capacity in some cases. Illustrating this, we examine in detail a binary adversarial channel that illustrates this necessity.
We consider keyless authentication for point-to-point communication in the presence of a myopic adversary. In particular, the adversary has access to a non-causal noisy version of the transmission and may use this knowledge to choose a channel state; the receiver is successful if it either decodes to the correct message or correctly detects adversarial interference. We show that, depending on the relationship between the channels to the legitimate receiver and the adversary, the authentication capacity is either zero or bounded above by the no-adversary capacity. To this end we introduce a novel channel property, termed U -overwritability, which allows the adversary to make its false message appear legitimate. We conjecture that if the capacity is nonzero, it is in fact equal to the no-adversary capacity, and show that this is true for a particular binary model.
In unsecured communications settings, ascertaining the trustworthiness of received information, called authentication, is paramount. We consider keyless authentication over an arbitrarily-varying channel, where channel states are chosen by a malicious adversary with access to noisy versions of transmitted sequences. We have shown previously that a channel condition termed U-overwritability is a sufficient condition for zero authentication capacity over such a channel, and also that with a deterministic encoder, a sufficiently clear-eyed adversary is essentially omniscient. In this paper, we show that even if the authentication capacity with a deterministic encoder and an essentially omniscient adversary is zero, allowing a stochastic encoder can result in a positive authentication capacity. Furthermore, the authentication capacity with a stochastic encoder can be equal to the no-adversary capacity of the underlying channel in this case. We illustrate this for a binary channel model, which provides insight into the more general case.
We consider the problem of authenticated communication over a discrete arbitrarily varying channel where the legitimate parties are unaware of whether or not an adversary is present. When there is no adversary, the channel state always takes a default value ∅. When the adversary is present, they may choose the channel state sequence based on a non-causal noisy view of the transmitted codewords and the encoding and decoding scheme. We require that the decoder output the correct message with a high probability when there is no adversary, and either output the correct message or reject the transmission when the adversary is present. Further, we allow the transmitter to employ private randomness during encoding that is known neither to the receiver nor the adversary. Our first result proves a dichotomy property for the capacity for this problem – the capacity either equals zero or it equals the non-adversarial capacity of the channel. Next, we give a sufficient condition for the capacity for this problem to be positive even when the non-adversarial channel to the receiver is stochastically degraded with respect to the channel to the adversary. Our proofs rely on a connection to a standalone authentication problem, where the goal is to accept or reject a candidate message that is already available to the decoder. Finally, we give examples and compare our sufficient condition with other related conditions known in the literature.
Keyless authentication is considered in an adversarial point-to-point channel. Namely, a legitimate transmitter and receiver aim to communicate over a noisy channel that may or may not also contain an active adversary, capable of transmitting an arbitrary signal into the channel. If the adversary is not present, then the receiver must successfully decode the message with high probability; if it is present, then the receiver must either decode the message or detect the adversary's presence. Thus, whenever the receiver decodes, it can be certain that the decoded message is authentic. The exact authentication capacity is characterized for discrete-memoryless adversary channels, where the adversary is assumed to know the code but not the message. The authentication capacity is shown to be either zero or equal to the no-adversary capacity, depending on whether the channel satisfies a condition termed overwritability.
We consider the problem of keyless message authentication over noisy channels in the presence of an active adversary. Different from the existing models, in our model, the legitimate users do not have any pre-shared key for authentication. Instead, we use the noisy channel connecting the legitimate users for authentication. The main idea is to utilize the noisy channel connecting the legitimate users to distinguish a legitimate message from a fake message, by generating an output at the receiver that is difficult for the adversary to replicate through its noisy channel. By interpreting the message authentication as a hypothesis testing problem, we investigate the authentication exponent and the authenticated channel capacity of the noisy channel. In the authentication exponent problem, for a given message rate, we investigate the speed at which the optimal successful attack probability can be driven to zero. We fully characterize the authentication exponent for the zero-rate message case and provide both an upper bound and a lower bound on the exponent for the non-zero message rate case. In the authenticated capacity problem, we study the largest data transmission rate under which the attacker's optimal successful attack probability can still be made arbitrarily small. We establish an all or nothing result. In particular, we show that the authenticated channel capacity is the same as the classic channel capacity if a simulatability condition is not satisfied, while the authenticated capacity will be zero if this condition is satisfied. We also provide efficient algorithms to check this condition. We further show that our results are robust to modeling uncertainties about the eavesdropper's channels.
In this paper, we present results on the authentication capacity region for the two-user arbitrarily-varying multipleaccess channel. We first consider a standard definition of authentication, in which the receiver may discard both messages if an adversary is detected. For this setting, we show that an extension of the arbitrarily-varying channel condition overwritability characterizes the authentication capacity region. We then define γ-correcting authentication, where we require that at least a γ fraction of the users' messages be correctable, even in the presence of an adversary. We give necessary conditions for the γ-correcting authentication capacity region to have nonempty interior, and show that positive rate pairs are achievable over a particular channel that satisfies these conditions.