Alexandria Engineering Journal (Jul 2023)
Graph design for data authentication over insecure communication channel
Abstract
Data authentication is a critical issue in communication systems. Based on data authentication techniques, the receiver can affirm that the data is really sent from an authentic sender and it is not a fabricated message from an opponent. One of the important techniques of data authentication is authentication codes. Authentication codes are utilized in communication channels in which there may be an opponent besides the sender and the receiver. This opponent may play both substitution attack or impersonation attack. Via an impersonation attack the opponent can transmit a message on the channel to the receiver and hopes that the receiver will take delivery of it as an authentic. Through the substitution attack we imply that once the opponent observes a message is sent by the sender, he substitutes that message with another one and expect that the receiver will accepted it as authentic. For each of those styles of attacks, there is an associated probability that the opponent will success to cheat the receiver. That are the probability of a successful impersonation attack P1 and the probability of a successful substitution attack P2. For more security of the communication system, it is far proposed to construct an authentication code with small values of P1 and P2. In this paper, we present an approach for design a graph message authentication code. This approach constructs a set of mutually orthogonal graph designs on a regular graph H by a graph G. Imposing certain conditions on H and G, we build a combinatorial design on H that yields to an authentication code with low probability of impersonation attack and of substitution attack. Moreover, we prove that such probabilities are related to the order of the graph H.
