Message authentication with correlated sources

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.