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.
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 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.
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.
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.
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.
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 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.