We consider a message authentication with distortion (DMA), where Alice encodes a source state and sends it over an unknown channel to Bob, who then tries to recover it, up to a small distortion. We formulate a formal model for this problem and define the authentication rate for DMA as the number of source symbols transmitted for each channel use. We characterize the best possible authentication rate (called authentication capacity) for a general DMA. We also obtain a lower bound on the adversarial success probability for a typical class of DMA.
We consider a message authentication with distortion (DMA), where Alice encodes a source state and sends it over an unknown channel to Bob, who then tries to recover it, up to a small distortion. We formulate a formal model for this problem and define the authentication rate for DMA as the number of source symbols transmitted for each channel use. We characterize the best possible authentication rate (called authentication capacity) for a general DMA. We also obtain a lower bound on the adversarial success probability for a typical class of DMA.
Message authentication is an interactive procedure that allows a legitimate sender Alice to send and authenticate a message M to a legitimate receiver Bob. To prevent the attacks from an adversary Eve, Alice and Bob usually share a secret key K. In this paper, we study a novel authentication framework as follows. Firstly, Alice sends a message M to Bob over a noiseless channel; Secondly, Alice generates an authentication tag with the message M and secret key K; Thirdly, Alice encodes the tag into a codeword Xn; Finally, Alice transmits the codeword Xn to Bob over a wiretap channel. This paper defines an authentication channel capacity under a fixed tag rate, and show that it equals to H(X|Z). Specifically, we prove that the authentication protocol proposed in Ref. [15] is capacity-achievable under our authentication model.
An approximate message authentication scheme is a primitive that allows a sender Alice to send a source state to a receiver Bob such that the latter is assured of its authenticity, where the source state is considered as authentic if it only undergoes a minor change. Here, the authors propose an efficient scheme for this problem and prove its security under a rigorous model. Our scheme only needs a lightweight computation cost and hence is very efficient. As the authentication message is transmitted over a noisy channel, we also value the channel efficiency (i.e. the coding rate). For a fixed coding method, this is determined by the admissible decoding bit error probability . A larger admits a shorter codeword length and hence a larger coding rate. It turns out that the can be set to be a significantly large constant (determined by the legal distortion level for the source state). Compared with existing schemes, the advantage in is evident.
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.
This paper investigates the secret key authentication capacity region. Specifically, the focus is on a model where a source must transmit information over an adversary controlled channel where the adversary, prior to the source's transmission, decides whether or not to replace the destination's observation with an arbitrary one of their choosing (done in hopes of having the destination accept a false message). To combat the adversary, the source and destination share a secret key which they may use to guarantee authenticated communications. The secret key authentication capacity region here is then defined as the region of jointly achievable message rate, authentication rate, and key consumption rate (i.e., how many bits of secret key are needed). This is the second of a two part study, with the studies separated by how the authentication rate is measured. Here, the authentication rate is measured by the minimum of the maximum probability of false acceptance where the minimization is over all highly probable subsets of observations at the adversary. That is, consider the maximum probability of false authentication as a function of the adversary's observation, and the adversary's observation as a random variable. The authentication rate is then measured as the smallest number for which the probability that the maximum probability of false authentication is greater than said number is arbitrary small. This is termed typical authentication, since it only needs to consider adversarial observations which are typical with the transmission. Under this measure of authentication matching inner and outer bounds are determined.
This paper investigates the secret key-authenticated-capacity region, where information-theoretic authentication is defined by the ability of the decoder to accept and decode messages originating from a valid encoder while rejecting messages from other invalid sources. The model considered here consists of a valid encoder-decoder pairing that can communicate through a channel controlled by an adversary who is also able to eavesdrop on the encoder’s transmissions. Prior to the encoder’s transmission, the adversary decides whether or not to replace the decoder’s observation with an arbitrary one of the adversary’s choosing, with the adversary’s objective being to have the decoder accept and decode their observation to a valid message (different from that of the encoder). To combat the adversary, the encoder and decoder share a secret key. The secret key-authenticated-capacity region is defined as the region of jointly achievable message rate, authentication rate (a to be defined per symbol measure that will generally represent the likelihood that an adversary can fool the decoder), and the key-consumption rate (how many bits of secret key are needed per symbol sent). This is the second of a two-part study, with the parts differing in their measure of the authentication rate. For this second study, the probability of false authentication is considered as a function of the system state, where the system state is defined by the message being transmitted, the value of the secret key, the adversary’s channel observations, and the adversary’s (possibly stochastic) choice for the decoder’s observation. Termed the typical-authentication rate, the authentication measure considered here corresponds to an upper bound on the probability of false authentication for the majority of system states. For this measure, we derive matching inner and outer bounds for the secret key-enabled authenticated capacity region in terms of traditional information-theoretic measures. In doing so, it is shown that the typical-authentication rate and the message rate exhibit a one-to-one trade-off in the capacity region.
This paper investigates the secret-key-authenticated-capacity region, where information-theoretic authentication is defined by the ability of the decoder to accept and decode messages originating from a valid encoder while rejecting messages from other invalid sources. The model considered here consists of a valid encoder-decoder pairing that can communicate through a channel controlled by an adversary who is also able to eavesdrop on the encoder’s transmissions. Over multiple rounds of communication, the adversary first decides whether or not to replace the decoder’s observation with an arbitrary one of the adversary’s choosing, with the goal of the adversary being to have the decoder accept and decode their observation as a valid message (different from that of the encoder). To combat the adversary, the encoder and decoder share a secret key. The secret-key-authenticated-capacity region here is then defined as the region of jointly achievable message rate, authentication rate (a to be defined per symbol measure that will generally represent the likelihood that an adversary can fool the decoder), and the key-consumption rate (how many bits of secret key are needed per symbol sent). This is the first of a two-part study, with the parts differing in their measure of the authentication rate. In this first study, the authentication rate is the exponent of blocklength-normalized exponent of the expected probability of false authentication. For this metric, we provide an inner bound which improves on those existing in the literature. This is achieved by adopting and merging different classical techniques in novel ways. Within these classical secret-key-based authentication techniques, one technique derives authentication capability from secure channel coding to send the secret key with the message, and the other technique derives its authentication capability directly from obscuring the source.