Progress on Cryptography

Simple and Efficient Systematic A-codes from Error Correcting Codes (p. 33-34)

Cunsheng Ding, Xiaojian Tian, Xuesong Wang

Abstract: In this paper, we present a simple and generic construction of systematic authentication codes which are optimal with respect to several bounds. The construction is based on error correcting codes. The authentication codes provide the best level of security with respect to spoofing attacks of various orders, including the impersonation and substitution attacks. The encoding of source states and the authentication verification are very simple and are perhaps the most efficient among all authentication systems.

Keywords: authentication codes, cryptography, linear codes.


1. Introduction

Nowadays authentication and secrecy of messages are two basic security requirements in many computer and communication systems, and therefore two important areas in cryptography. Authentication codes are designed to provide sender and message authentication, and dates back to 1994 when Gilbert, MacWilliams and Sloane published the first paper in this area [see Gilbert, MacWilliams, Sloane, 1974]. Later Simmons [Simmos, 1984] developed a theory of unconditional authentication, which is analogous to Shannon’s theory of unconditional secrecy [Shannon, 1949].

During the last tweenty years codes that provide authentication and/or secrecy have been considered, and bounds and characterizations of these codes have been established, see, for example, [Gilbert, MacWilliams, Sloane, 1974], [Stinson 1990], [Casse, Martin, and Wild, 1998]. Most existing optimal authentication codes are constructed from combinatorial designs, and seem hard to implement. Even if some of them can be implemented in software or hardware, the implementation may not be efficient. In addition, these authentication codes provide protection against the imperson ation and substitution attacks, but may not provide protection against spoofing attacks of order more than 1.

The purpose of this paper is to present a simple and generic construction of systematic authentication codes with the following properties:

* The authentication codes are optimal with respect to certain bounds.

* They offer the best security with respect to not only impersonation and substitution atacks, but also spoofing attacks of higher orders.

* The encoding of source states and authentication are extremely efficient and can be easily implemented in both software and hardware.

The construction of authentication codes presented here is based on error correcting codes, and is different from other constructions of authentication codes, see [Bierauer 1997], [Bierbrauer, Johansson, Kabatianskii and Smeets 1993], [Gilbert, Mac Williams, Sloane, 1974], [Kabatianskii, Smeets, and Johansson, 1996], [Simmons 1984], [Safavi-Naini and Seberry 1991], [Safavi-Naini, Wang and Xing 2001], using error correcting codes, in the sense that error correcting codes are employed to construct only the source states here in this paper.