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:0802.2701 · IEEE Transactions on Information Theory

Authentication Over Noisy Channels

Lifeng Lai, Hesham El Gamal, H. Vincent Poor

Published Feb 1, 2009• 106 citations
arXivHTMLPDF

Abstract

An authentication counterpart of Wyner's study of the wiretap channel is developed in this work. More specifically, message authentication over noisy channels is studied while impersonation and substitution attacks are investigated for both single- and multiple-message scenarios. For each scenario, information-theoretic lower and upper bounds on the opponent's success, or cheating, probability are derived. Remarkably, in both scenarios, the lower and upper bounds are shown to match, and hence, the fundamental limits on message authentication over noisy channels are fully characterized. The opponent's success probability is further shown to be smaller than that derived in the classical noiseless channel model. These results rely on a novel authentication scheme in which shared key information is used to provide simultaneous protection against both types of attacks. Finally, message authentication for the case in which the source and receiver possess only correlated sequences is studied.

DOI
10.1109/tit.2008.2009842

Related papers

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

Message authentication with correlated sources

Daming Cao, Wei Kang

In this paper, we study the problem of message authentication with two correlated sources observed by the legitimate transmitter and receiver as secret information. We consider an active adversary capable of the impersonation attack and the substitution attack. We are interested in minimizing the maximum probability of successful deception under the two attacks, where the minimization is over all authentication schemes by the legitimate transmitter and receiver and the maximization is over all attack strategies by the adversary. We propose a random coding based authentication scheme and obtain upper bound on the solutions of the above min-max problem for both attacks. We also show that the proposed random coding based scheme outperforms the separation-based scheme, i.e., private-key generation first using the correlated sources and then authentication with the private key. Finally, for the impersonation attack, we obtain a lower bound, which meet the upper bound. Therefore, we solve the min-max problem and characterize the optimal performance of the authentication system under impersonation attacks.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•2 citations

On Message Authentication Channel Capacity Over a Wiretap Channel

Dajiang Chen, Shaoquan Jiang, Ning Zhang +2 more

In this paper, a novel message authentication model using the same key over wiretap channel is proposed to achieveinformation-theoretic security. Specifically, in the proposed model, there is a discrete memoryless channelW1:X→Ybetween transmitter Alice and receiver Bob, while an attacker Oscar is connected with Alice via discrete memoryless channelW2:X→Z. Alice encodes messageMto codeword (S,Xn), using an encoding function with secret keyK. Then,Sis sent to Bob over a one-way noiseless channel (fully controlled by Oscar), andXnis sent over the wiretap channel, sayX→(Y,Z). Building on this model, a new message authentication scheme is proposed. The scheme incorporates a secure channel coding, which uses random coding techniques to detect man-in-the-middle (MITM) attacks. The authentication channel capacity is studied in a specific channel model whenW2is not less noisy thanW1. We theoretically demonstrate that the authentication channel capacity is much larger than the secrecy capacity, since Bob does not need to recover information transmitted over the noisy channel.

IEEE Transactions on Information Forensics and Security•Jan 1, 2022•21 citations

On the Optimality of Keyless Authentication in a Noisy Model

Shaoquan Jiang

We further study the keyless authentication problem in a noisy model in our previous work, where no secret setup is available for sender Alice and receiver Bob while there is discrete memoryless channel (DMC) W1 from Alice to Bob and a two-way noiseless but insecure channel between them. We propose a construction such that the message length over DMC W1 does not depend on the size of the source space. If the source space is S and the number of channel W1 uses is n, then our protocol only has a round complexity of log* |S| - log* n + 4. In addition, we show that the round complexity of any secure protocol in our model is lower bounded by log* |S| - log* n - 5. We also obtain a lower bound on the success probability when the message size on DMC W1 is given. Finally, we derive the capacity for a noninteractive authentication protocol under general DMCs, which extends the result under Binary Symmetric Channels in our previous work.

arXiv:1409.1657•IEEE Transactions on Information Forensics and Security•Feb 24, 2015•15 citations

Message Authentication Scheme Under Gaussian Vector Multiple-Input Channels

HAN Jialiang, XU Ming

Message authentication allows the receiver of a message to detect whether the message is forged or illegally modified by someone other than the legitimate sender.Traditional message authentication schemes are typically implemented at the network layer or higher,which are vulnerable to security threats such as replay attacks,denial of service attacks and so forth.Based on the existing schemes based on the physical layer,this paper proposes a message authentication scheme using the Minimum Mean Square Error(MMSE) method for estimation of channels under the Gaussian vector multiple-input channel model.An optimal attack strategy for the eavesdropper is also formulated,and determines the reachable secrecy boundary according to the probabilities of successful attacks of the eavesdropper.By using the information theory to analyze the maximum security authentication rate of the channel,the secrecy capacity domain of the channel is obtained.Experimental results show that the average probability of successful attack of the eavesdropper decreases exponentially with the increased number of received messages.When the spatial correlation coefficients between all senders and the eavesdropper are lower than 0.3,the average probability of successful attack of the eavesdropper is less than 1.87×10-7,which verifies the security of the proposed scheme.

•Dec 1, 2020•0 citations

Authentication Capacity Over Wiretap Channel

Chen Da-jian

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.

Dianzi Ke-ji Daxue xuebao•Jan 1, 2015•0 citations
An authentication counterpart of Wyner's study of the wiretap channel is developed in this work. More specifically, message authentication over noisy channels is studied while impersonation and substitution attacks are investigated for both single- and multiple-message scenarios. For each scenario, information-theoretic lower and upper bounds on the opponent's success, or cheating, probability are derived. Remarkably, in both scenarios, the lower and upper bounds are shown to match, and hence, the fundamental limits on message authentication over noisy channels are fully characterized. The opponent's success probability is further shown to be smaller than that derived in the classical noiseless channel model. These results rely on a novel authentication scheme in which shared key information is used to provide simultaneous protection against both types of attacks. Finally, message authentication for the case in which the source and receiver possess only correlated sequences is studied.
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 study the problem of message authentication with two correlated sources observed by the legitimate transmitter and receiver as secret information. We consider an active adversary capable of the impersonation attack and the substitution attack. We are interested in minimizing the maximum probability of successful deception under the two attacks, where the minimization is over all authentication schemes by the legitimate transmitter and receiver and the maximization is over all attack strategies by the adversary. We propose a random coding based authentication scheme and obtain upper bound on the solutions of the above min-max problem for both attacks. We also show that the proposed random coding based scheme outperforms the separation-based scheme, i.e., private-key generation first using the correlated sources and then authentication with the private key. Finally, for the impersonation attack, we obtain a lower bound, which meet the upper bound. Therefore, we solve the min-max problem and characterize the optimal performance of the authentication system under impersonation attacks.
In this paper, a novel message authentication model using the same key over wiretap channel is proposed to achieveinformation-theoretic security. Specifically, in the proposed model, there is a discrete memoryless channelW1:X→Ybetween transmitter Alice and receiver Bob, while an attacker Oscar is connected with Alice via discrete memoryless channelW2:X→Z. Alice encodes messageMto codeword (S,Xn), using an encoding function with secret keyK. Then,Sis sent to Bob over a one-way noiseless channel (fully controlled by Oscar), andXnis sent over the wiretap channel, sayX→(Y,Z). Building on this model, a new message authentication scheme is proposed. The scheme incorporates a secure channel coding, which uses random coding techniques to detect man-in-the-middle (MITM) attacks. The authentication channel capacity is studied in a specific channel model whenW2is not less noisy thanW1. We theoretically demonstrate that the authentication channel capacity is much larger than the secrecy capacity, since Bob does not need to recover information transmitted over the noisy channel.
We further study the keyless authentication problem in a noisy model in our previous work, where no secret setup is available for sender Alice and receiver Bob while there is discrete memoryless channel (DMC) W1 from Alice to Bob and a two-way noiseless but insecure channel between them. We propose a construction such that the message length over DMC W1 does not depend on the size of the source space. If the source space is S and the number of channel W1 uses is n, then our protocol only has a round complexity of log* |S| - log* n + 4. In addition, we show that the round complexity of any secure protocol in our model is lower bounded by log* |S| - log* n - 5. We also obtain a lower bound on the success probability when the message size on DMC W1 is given. Finally, we derive the capacity for a noninteractive authentication protocol under general DMCs, which extends the result under Binary Symmetric Channels in our previous work.
Message authentication allows the receiver of a message to detect whether the message is forged or illegally modified by someone other than the legitimate sender.Traditional message authentication schemes are typically implemented at the network layer or higher,which are vulnerable to security threats such as replay attacks,denial of service attacks and so forth.Based on the existing schemes based on the physical layer,this paper proposes a message authentication scheme using the Minimum Mean Square Error(MMSE) method for estimation of channels under the Gaussian vector multiple-input channel model.An optimal attack strategy for the eavesdropper is also formulated,and determines the reachable secrecy boundary according to the probabilities of successful attacks of the eavesdropper.By using the information theory to analyze the maximum security authentication rate of the channel,the secrecy capacity domain of the channel is obtained.Experimental results show that the average probability of successful attack of the eavesdropper decreases exponentially with the increased number of received messages.When the spatial correlation coefficients between all senders and the eavesdropper are lower than 0.3,the average probability of successful attack of the eavesdropper is less than 1.87×10-7,which verifies the security of the proposed scheme.
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.