Two-Dimensional Compound Message Authentication Code in Lossy Channels

Efficient message authentication is crucial for secure communications. However, the traditional integrity check scheme imposes significant overhead by appending a unique Message Authentication Code (MAC) to each message. At the same time, existing solutions such as aggregate and compound MACs attempt to reduce this overhead by transmitting one MAC tag per multiple messages. This strategy is ineffective in lossy environments where any message loss prevents the corresponding tag from verifying the other messages assigned to it. In this paper, we introduce a novel two-dimensional (2D) MAC structure that organizes messages in a 2D format and computes a single authentication tag for each row and column. This approach enables precise identification of modified or erroneous messages using fewer tags than conventional methods. By integrating the 2D MAC structure with superimposed coding techniques, we further reduce bandwidth consumption by allowing simultaneous transmission of messages and authentication tags. Experimental validation in Wi-Fi networks demonstrates over 20 % increase in authentication throughput, with analytical results indicating additional improvements when tags are superimposed onto the message.