Authentication over noisy channels

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 imper-sonation 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 fur-ther 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 authen-tication for the case in which the source and receiver possess only correlated sequences is studied. Index Terms—Authentication, impersonation attack, noisy channel, substitution attack, wiretapper. I.