HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5723
Title: Cyclotomic cartesian authentication codes
Authors: Sze, Tsz Wo
Issue Date: 2001
Abstract: Authentication is an important issue in many communications systems. Simmons 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. We extend their work by constructing three classes of Cartesian authentication codes using the logarithm function over groups. We observe that the 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 we constructed are better than 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 allow multiplication in the authentication mapping. Although the form of Pd1 is complex, we provide a table of possible codes with exact values of Pd1. 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 implementation example of an authentication system for smart cards, which has very limited computing and memory capacities. The average running time for encoding or verifying a message is only 4 seconds on a Java card. Most other existing authentication codes would not even be able to run on smart cards.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2001
x, 60 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 2001 Sze
URI: http://hdl.handle.net/1783.1/5723
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.