Multiuser authentication with anonymity constraints over noisy channels

We consider authentication of messages sent by L legitimate transmitters to a legitimate receiver over a noisy multiple access channel. We assume the presence of a computationally unbounded opponent who has access to noisy observations of the messages transmitted, and can perform impersonation or substitution attacks. In addition, we consider anonymity constraints where the legitimate receiver must be able to authenticate the messages he receives with respect to predetermined groups of transmitters, but must be kept ignorant of the transmitter's identity of a given message in a given group. Our main result is an authentication coding scheme for which asymptotically matching upper and lower bounds on the probability of successful attack are derived. Our result analytically quantifies the impact of a multiuser setting compared to a single-user setting, as well as the negative impact of anonymity constraints on the probability of successful attack.