Authentication over Arbitrarily Varying Channels with Causal Adversaries
Abstract
We study authentication over a discrete memoryless arbitrarily varying channel (AVC) in which the adversary selects the channel state causally based on past channel outputs. We prove that the authentication capacity is positive exactly when the channel is not distribution-overwritable under stochastic encoding, and not I-overwritable under deterministic encoding. In the stochastic case, whenever the authentication capacity is positive, it coincides with the no-adversary Shannon capacity. Both converses follow from a novel wait-and-overwrite attack: the adversary tracks the no-adversary posterior over the message via the posterior guessing probability, and once it concentrates past a threshold, it samples a guess and a decoy from the posterior and overwrites the channel to mimic a no-adversary transmission of the decoy. The positivity results are obtained by constructing positive-rate codes with controlled overlap between codewords, together with a martingale concentration argument that handles adaptive adversarial strategies. For stochastic encoding, the full-capacity achievability further combines a capacity-achieving channel code with an authentication tag. These characterizations separate the causal stochastic-code and causal deterministic-code settings from each other and from the oblivious-adversary setting studied by Kosut and Kliewer.
Related
- JEPA-kMMVAE: CSI Prediction for Time-Varying Wireless Channels
- Sensitivity of RMS Delay Spread Estimation to Power Delay Profile Thresholding in Time-Varying Channels at 33 GHz
- Leveraging Slowly Time-Varying AP-AP Channels for Interference Mitigation in Dynamic TDD
- FedPGT: Progressive Gradient Transmission for Vehicular Federated Learning over Time-Varying Channels
- PRB-WM: Physics-Regularized Beta World Models for Predictive Link Adaptation on Real Time-Varying Underwater Acoustic Channels
BibTeX
@misc{bakshi2026authentication,
title = {{Authentication over Arbitrarily Varying Channels with Causal Adversaries}},
author = {Mayank Bakshi and Vinod M. Prabhakaran and Bikash Kumar Dey and Oliver Kosut},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28939},
eprint = {2608.28939},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28939},
}
RIS
TY - UNPB
TI - Authentication over Arbitrarily Varying Channels with Causal Adversaries
AU - Mayank Bakshi
AU - Vinod M. Prabhakaran
AU - Bikash Kumar Dey
AU - Oliver Kosut
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.28939
UR - https://arxiv.org/abs/2608.28939
AB - We study authentication over a discrete memoryless arbitrarily varying channel (AVC) in which the adversary selects the channel state causally based on past channel outputs. We prove that the authentication capacity is positive exactly when the channel is not distribution-overwritable under stochastic encoding, and not I-overwritable under deterministic encoding. In the stochastic case, whenever the authentication capacity is positive, it coincides with the no-adversary Shannon capacity. Both converses follow from a novel wait-and-overwrite attack: the adversary tracks the no-adversary posterior over the message via the posterior guessing probability, and once it concentrates past a threshold, it samples a guess and a decoy from the posterior and overwrites the channel to mimic a no-adversary transmission of the decoy. The positivity results are obtained by constructing positive-rate codes with controlled overlap between codewords, together with a martingale concentration argument that handles adaptive adversarial strategies. For stochastic encoding, the full-capacity achievability further combines a capacity-achieving channel code with an authentication tag. These characterizations separate the causal stochastic-code and causal deterministic-code settings from each other and from the oblivious-adversary setting studied by Kosut and Kliewer.
ER -