Abstract
This paper provides new combinatorial bounds and characterizations of authentication codes (A-codes) and key predistribution schemes (KPS). We first prove a new lower bound on the number of keys in an A-code without secrecy, which can be thought of as a generalization of the classical Rao bound for orthogonal arrays. We also prove a new lower bound on the number of keys in a general A-code, which is based on the Petrenjuk, Ray-Chaudhuri and Wilson bound for t-designs. We also present new lower bounds on the size of keys and the amount of users' secret information in KPS, the latter of which is accomplished by showing that a certain A-code is “hiding” inside any KPS.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Beimel, Private communication, (1997).
J. Bierbrauer, Bounds on orthogonal arrays and resilient functions, Journal of Combinatorial Designs, Vol. 3 (1995) pp. 179–183.
R. Blom, An optimal class of symmetric key generation systems, Lecture Notes in Computer Science, Vol. 209 (1984) pp. 335–338 (Proceedings of EUROCRYPT’ 84).
C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro, and M. Yung, Perfectly secure key distribution for dynamic conferences, Lecture Notes in Computer Science, Vol. 740 (1993) pp. 471–486 (Proceedings of CRYPTO’ 92).
C. J. Colbourn and J.H. Dinitz, eds, CRC Handbook of Combinatorial Designs, CRC Press, Inc. (1996).
D. K. Ray-Chaudhuri and R. M. Wilson, On t-designs, Osaka Journal of Mathematics, Vol. 12 (1975) pp. 737–744.
R. S. Rees and D.R. Stinson, Combinatorial characterizations of authentication codes II, Designs, Codes and Cryptography, Vol. 7 (1996) pp. 239–259.
G. J. Simmons, A survey of information authentication, Contemporary Cryptology, The Science of Information Integrity, IEEE Press (1992) pp. 379–419.
D. R. Stinson, The combinatorics of authentication and secrecy codes, Journal of Cryptology, Vol. 2 (1990) pp. 23–49.
D. R. Stinson, Combinatorial characterizations of authentication codes, Designs, Codes and Cryptography, Vol. 2 (1992) pp. 175–187.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kurosawa, K., Okada, K., Saido, H. et al. New Combinatorial Bounds for Authentication Codes and Key Predistribution Schemes. Designs, Codes and Cryptography 15, 87–100 (1998). https://doi.org/10.1023/A:1008229625895
Issue Date:
DOI: https://doi.org/10.1023/A:1008229625895