Topics in Authentication Theory

Sammanfattning: Authentication theory deals with problems connected with the protection of information sent over insecure channels. This thesis concerns different problems in authentication theory. In particular, we consider unconditionally secure authentication, i.e., providing authentication protection agains an enemy equipped with unlimited computing power. Several topics in authentication theory are treated: random authentication coding, multiround authentication, group authentication, anonymous secret sharing, and fast MACs. Random authentication encoding constructions are investigated. Expressions for the probability of a successful attack are given. We give an expression for the asymptotic behaviour of the key size of the random construction as a function of the message size. We provide some experimental data. Unconditionally secure multiround authentication schemes are treated. We define a multiround authentication model and show how to calculate the probability of a successful attack for this model. A multiround scheme constructed by Gemmell and Naor is cryptanalysed. We propose new multiround constructions for a 3-round protocol and for a protocol with an arbitrary number of rounds. A new upper bound on the key size is given. We define an authentication model for shared generation of an authenticator among a set of participants, called group authentication. Expressions for the probability of a successful attack for this model are given. We derive information theoretic lower bounds for the probability of a successful attack. Linear schemes are investigated and constructions based on codes for the rank metric are given. We give definitions of anonymous secret sharing schemes. Two different anonymity levels are used, called anonymous and strongly anonymous. Using the new definitions, threshold schemes and general access structures are investigated. A necessary and sufficient condition for the existence of a strongly anonymous secret sharing scheme is given. We investigate how a MAC can be calculated fast in software. Two different approaches are used: one that uses polynomial evaluation over a finite field and one tha uses random polynomial residue class codes. The binary complexity of the two suggested procedures is calculated. Examples of constructions are given.