This work establishes that the physical layer can be used to perform information-theoretic authentication in additive white Gaussian noise (AWGN) channels, as long as the adversary is not omniscient. The model considered consists of an encoder, decoder, and adversary, where the adversary knows the message given to the encoder, has a non-causal noisy observation of the encoder’s transmission and may use unlimited transmission power, while the decoder observes a noisy version of the sum of the encoder and adversary’s outputs. A method to modify a generic existing channel code to enable authentication is presented. This method relies on injecting message-dependent noise into the transmission and accepting the transmission as authentic only if the correct noise levels for the decoded message are observed. One drawback to this method is that the encoder must still transmit a low-power signal in the case where there is no message to send. It is shown that this modification costs an asymptotically negligible amount of the coding rate, while still enabling authentication as long as the adversary’s observation is not noiseless. Also notable is that this modification is not (asymptotically) a function of the statistical characterization of the adversary’s channel and no secret key is required. We believe these features will pave the way for a robust practical implementation. Using these results, the channel-authenticated capacity is calculated and shown to be equal to the non-adversarial channel capacity. As our results will show, information-theoretic authentication in AWGN channels is possible without the need for the legitimate party to have a model-based advantage over the adversary. While this modular scheme is designed for use in the given channel model, it is applicable to a wide range of settings.
This work establishes that the physical layer can be used to perform information-theoretic authentication in additive white Gaussian noise (AWGN) channels, as long as the adversary is not omniscient. The model considered consists of an encoder, decoder, and adversary, where the adversary knows the message given to the encoder, has a non-causal noisy observation of the encoder’s transmission and may use unlimited transmission power, while the decoder observes a noisy version of the sum of the encoder and adversary’s outputs. A method to modify a generic existing channel code to enable authentication is presented. This method relies on injecting message-dependent noise into the transmission and accepting the transmission as authentic only if the correct noise levels for the decoded message are observed. One drawback to this method is that the encoder must still transmit a low-power signal in the case where there is no message to send. It is shown that this modification costs an asymptotically negligible amount of the coding rate, while still enabling authentication as long as the adversary’s observation is not noiseless. Also notable is that this modification is not (asymptotically) a function of the statistical characterization of the adversary’s channel and no secret key is required. We believe these features will pave the way for a robust practical implementation. Using these results, the channel-authenticated capacity is calculated and shown to be equal to the non-adversarial channel capacity. As our results will show, information-theoretic authentication in AWGN channels is possible without the need for the legitimate party to have a model-based advantage over the adversary. While this modular scheme is designed for use in the given channel model, it is applicable to a wide range of settings.
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 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 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.
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 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.