Authentication Codes and Combinatorial Designs
This book is concerned with two authentication schemes. In both of them there is a sender, a receiver and an opponent. The scheme consists of a set of source states, a set of messages and a set of keys. The goal is to transmit a source state by means of sending a message. Each key is a one-to-one mapping from a subset of the message set into the set of source states. The sender and receiver agree on some key and the opponent tries to mislead the receiver with a fraudulent message. If the sender and the receiver are supposed to trust each other, one speaks about an authentication scheme with three participants. The scheme with four participants involves an arbiter between the sender and receiver in the case when they are not regarded as trustworthy. The main line of the book consists of considering the designs that appear when a key is associated with a set of admissible messages (i.e. with the range of a mapping with which we identify a given key).
In the beginning the author uses probability and entropy computations to show that the perfect 3-party authentication schemes with uniform probability distributions correspond to strong partially balanced t-designs. The definition of a partially balanced design differs from that of a t-design with parameters (v, b, k, λ) by allowing the existence of k-sets that do not extend to any t-set. Such a design is called strong when it is also a partial balanced r-design for every r smaller than t. The conditions for perfect 4-party authentications are of a similar type but much more technically complicated. Much of the content of the book is a survey of various designs that can be used for the studied authentication schemes. A lot of material is taken from other sources and the exposition is very careful, often in an elementary manner. Even some well known topics are covered in detail, like Steiner triples or mutually orthogonal Latin squares. There is an overview of constructions of orthogonal arrays and a description of interesting families of authentication schemes based on curves and on finite geometries.