Advanced

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

Johansson, Thomas LU ; Smeets, Ben LU and Grigory, Kabatianskii (1996) In IEEE Transactions on Information Theory 42(2). p.566-578
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 threats. 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... (More)
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 threats. 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 PS>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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
IEEE Transactions on Information Theory
volume
42
issue
2
pages
566 - 578
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:0030106709
ISSN
0018-9448
DOI
10.1109/18.485725
language
English
LU publication?
yes
id
7f9fe7ef-5ebe-4b96-93b5-f35e2dea446c (old id 1157119)
date added to LUP
2008-06-09 11:39:08
date last changed
2017-01-01 07:53:35
@article{7f9fe7ef-5ebe-4b96-93b5-f35e2dea446c,
  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 threats. 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 PS>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.},
  author       = {Johansson, Thomas and Smeets, Ben and Grigory, Kabatianskii},
  issn         = {0018-9448},
  language     = {eng},
  number       = {2},
  pages        = {566--578},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Information Theory},
  title        = {On the cardinality of systematic authentication codes via error-correcting codes},
  url          = {http://dx.doi.org/10.1109/18.485725},
  volume       = {42},
  year         = {1996},
}