Abstract
If we agree to use one ofv possible messages to communicate one ofk possible source states, then an opponent can successfully impersonate a transmitter with probability at leastk/v, and can successfully substitute a message with a fraudulent one with probability at least (k−1)/(v−1). We wish to limit an opponent to these bounds. In addition, we desire that the observation of any two messages in the communication channel will give an opponent no clue as to the two source states. We describe a construction for a code which achieves these goals, and which does so with the minimum possible number of encoding rules (namely,v·(v−1)/2). The construction uses a structure from combinatorial design theory known as a perpendicular array.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. F. Brickell, A few results in message authentication,Congressus Numerantium,43 (1984), 141–154.
E. Gilbert, F. J. MacWilliams, and N. J. A. Sloane, Sloane, Codes which detect deception,Bell System Tech. J.,53 (1974), 405–424.
A. Granville, A. Moisiadis, and R. Rees, nested stinern-cycle systems and perpendicular arrays, preprint.
C. Huang, E. Mendelsohn, and A. Rosa, On partially resolvablet-partitionsd,Ann. Discrete Math.,12 (1983), 169–183.
C. C. Lindner and D. R. Stinson, Steiner pentagon systems,Discrete Math.,52 (1984), 67–74.
C. C. Lindner and D. R. Stinson, The spectrum for the conjugate invariant subgroups of perpendicular arrays,Ars Combin.,18(1984), 51–60.
C. C. Lindner, R. C. Mullin, and G. H. J. van Rees, Separable orthogonal arrays,Utilitas Math., to appear.
J. L. Massey, Cryptography—A selective survey, inDigital Communications (1986), 3–21.
R. C. Mullin, P. J. Schellenberg, G. H. J. van Rees, and S. A. Vanstone, On the construction of perpendicular arrays,Utilitas Math.,18(1980), 141–160.
S. C. Polhlig and M. E. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance,IEEE Trans. Inform. Theory,24(1978), 106–110.
P. Schobi, Perfect authentication systems for data sources with arbitrary statistics, preprint.
C. E. Shannon, Communication theory of secrecy systems,Bull System Tech. J.,28(1949), 656–715.
G. J. Simmons, A game theory model of digital message authentication,Congressus Numerantium,34(1982), 413–424.
G. J. Simmons, Message authentication: a game on hypergraphs,Congressus Numerantium,45 (1984), 161–192.
G. J. Simmons, Authentication theory/coding theory, inAdvances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, vol. 196, 411–432, Springer-Verlag, Berlin, 1985.
D. R. Stinson, Some constructions and bounds for authentication codes,J. Cryptology,1 (1988).
G. H. J. van Rees, private communication.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Stinson, D.R. A construction for authentication/secrecy codes from certain combinatorial designs. J. Cryptology 1, 119–127 (1988). https://doi.org/10.1007/BF02351720
Issue Date:
DOI: https://doi.org/10.1007/BF02351720