On the cardinality of systematic authentication codes via error-correcting codes

Gregory A. Kabatianskii, Ben Smects, Thomas Johansson

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)

Abstract

Abstract-In both open and private communication the participants face potential threats from a malicious enemy who has access to the communication channel and can insert messages (impersonation attack) or alter already transmitted messages (substitution attack). Authentication codes (A-codes) have been developed to provide protection against these treats. In this paper we introduce a new distance, called the authentication distance (A-distance), and show that an A-code can be described as a code for the A-distance. The A-distance is directly related to the probability PS of success in a substitution attack. We show how to transform an error-correcting code into an A-code and vice versa. We further use these transformations to provide both upper and lower bounds on the size of the information to be authenticated, and study their asymptotic behavior. As examples of obtained results, we prove that the cardinality of the source state space grows exponentially with the number of keys provided Pi > Pi, we generalize the square-root bound given by Gilbert, MacWilliams, and Sloane in 1979, and we provide very efficient constructions using concatenated Reed-Solomon codes. Index Terms- Authentication codes, error-correcting codes, universal hash functions, information integrity.

Original languageEnglish
Pages (from-to)566-578
Number of pages13
JournalIEEE Transactions on Information Theory
Volume42
Issue number2
DOIs
Publication statusPublished - 1996
Externally publishedYes

Fingerprint

Dive into the research topics of 'On the cardinality of systematic authentication codes via error-correcting codes'. Together they form a unique fingerprint.

Cite this