Strongly Secure Multiuser Communication and Authentication with Anonymity Constraints

We consider authentication of messages sent from transmitters to a receiver over a multiple access channel, where each transmitter shares a secret key with the legitimate receiver. Additionally, there exists a computationally unbounded opponent who has access to noisy observations of the messages transmitted and can initiate impersonation or substitution attacks. We require that the legitimate receiver must be able to authenticate the messages he receives with respect to predetermined groups of transmitters, but at the same time must be kept ignorant of the transmitter's identity of a given message in a given group. We propose an information-theoretic formulation of these anonymity constraints as well as an authentication coding scheme for which the asymptotic probability of successful attack is shown to optimally scale with the length of the secret keys shared between each transmitter and the legitimate receiver. Our results quantify the positive impact of the multiple access setting compared to the single-user setting on the probability of successful attack.