Degree Name

Doctor of Philosophy


Department of Computer Science


Rapid development of distributed computer systems in recent years has dramatically increased the importance of cryptography. One of the main goals of cryptography is to provide authenticity of the information. This thesis presents new results on unconditionally secure authentication systems.

Two classes of enemy strategies are considered and new combinatorial bounds on the enemy's probability of success are found. Necessary and sufficient conditions on the incidence matrix of authentication codes with r-fold security are derived and used to characterise these codes in terms of well-known combinatorial structures. A new concept of 'near-perfect protection' is introduced. It is shown that providing near-perfect protection is a necessary condition for authentication codes that satisfy the best known information-theoretic bounds with equality.

A classification of attacks depending on the goal of the attack and the information available to the enemy is proposed. Two new types of attacks, plaintext and chosencontent attacks, are investigated. Perfect and near-perfect protection for each type of attack is defined and information-theoretic bounds on the probability of the enemy's success are proved. Constructions of authentication codes that are resistant against these attacks are proposed.