MPhil Thesis Defence


"Cyclotomic Cartesian Authentication Codes"

By

Mr. Tsz-Wo Sze


Abstract

Authentication is an important issue in many communications systems.
Simmons has developed the theory of unconditional authentication analogous
to Shannon's theory of unconditional secrecy. Based on Simmons'
authentication model, Chanson, Ding and Salomaa have recently constructed
several classes of authentication codes using functions with perfect
nonlinearity and optimal nonlinearity.

In this thesis, we further extend that work by constructing three classes
of Cartesian authentication codes using the logarithm function over
groups. We observe that logarithm function over groups has high
nonlinearity. To describe authentication codes based on the logorithm
function, the theory of cyclotomy is used. It can be shown that the codes
constructed here are better than the existing codes with comparable
parameters.

In the first class of authentication codes, the deception probability Pd0
of impersonation attack essentially reaches the minimum and the deception
probability Pd1 of substitution attack is bounded below and above by the
maximum cyclotomic number of order d, where d is a parameter of the codes.
For d=2, the value of Pd1 is determined completely. For d=3 and d=4, some
codes are proved to be asymptotically optimal. In the second class of
authentication codes, both Pd0 and Pd1 can be evaluated completely. The
codes in this class have smaller values of Pd0 and Pd1 compared with the
codes in the first class. However, the size of the key space is larger. In
the third class of authentication codes, we introduce multiplication to
the authentication mapping. Although the form of Pd1 is quite complicated,
we provide a table of possible codes with exact value of Pd1.

In this thesis, we also demonstrate how the codes can be used for
authentication in a wireless communication environment for the control of
nuclear weapons. The computation requirement of the authentication system
is very low. The system can be implemented on a PDA-like handheld device
which need only perform arithmetic operations on one-byte integers. Also
we present a detailed example of implementation of the authentication
system in smart cards, which have very limited computing and memory
capacities. The average running time for encoding or verifying a message
is 4 seconds only on a Java card. Most other existing authentication codes
could not even run on smart cards.

The chapters in the thesis are organized as follows: Chapter 1 provides an
introduction to authentication codes. Chapter 2 reviews the theory of
cyclotomy and states useful theorems needed by the subsequent chapters.
Chapters 3, 4 and 5 discuss the first, second and third classes of
authentication codes respectively. The application and implementation
details are discussed in Chapter 6. Chapter 7 presents some related work
by other people.


Date:			Monday, 13 August 2001

Time:			3:30p.m.-5:30p.m.

Venue:			Room 1505
			Lifts 25-26

Committee Members:		Prof. Samuel Chanson (Supervisor)
			Dr. Mordecai Golin (Chairman)
			Prof. Derick Wood


**** ALL are Welcome ****