Projective Systematic Authentication via Reed-Muller Codes

In this paper, we study the problem of constructing projective systematic authentication schemes based on binary linear codes. In systematic authentication, a tag for authentication is generated and then appended to the information, also referred to as the source, to be sent from the sender. Existing approaches to leverage projective constructions focus primarily on codes over large alphabets, and the projection is simply into one single symbol of the codeword. In this work, we extend the projective construction and propose a general projection process in which the source, which is mapped to a higher dimensional codeword in a given code, is first projected to a lower dimensional vector. The resulting vector is then masked to generate the tag. To showcase the new method, we focus on leveraging binary linear codes and, in particular, Reed-Muller (RM) codes for the proposed projective construction. More specifically, we propose systematic authentication schemes based on RM codes, referred to as RM-Acodes. We provide analytical results for probabilities of deception, widely considered as the main metrics to evaluate the performance of authentication systems. Through our analysis, we discover and discuss explicit connections between the probabilities of deception and various properties of RM codes.