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....[ Read more ]

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 P_d0 of impersonation attack essentially reaches the minimum and the deception probability P_d1 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 P_d1 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 P_d0 and P_d1 can be evaluated completely. The codes in this class have smaller values of P_d0 and P_d1 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 P_d1 is complex, we provide a table of possible codes with exact values of P_d1.

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.