Abstract
In this paper we study authentication systems and consider the following scenario: Each encoding rule is used for the transmission of a sequence of i messages. We prove a lower bound on the probability that a spoofer observing i messages succeeds in generating an authentic message without knowing the encoding rule used. This bound is based on the conditional entropy of the encoding rules when a sequence of messages is known. Authentication systems which meet the bound are investigated and compared with systems that are l-fold secure against spoofing introduced by Massey [8]. We also give a bound for the probability of success if the opponent can choose how many messages he observes before trying to cheat.
Article PDF
Similar content being viewed by others
References
Beutelspacher, A., and Rosenbaum, U., Essentially Perfect Authentication Systems, Advances in Cryptology: Proceedings of EUROCRYPT 1990, pp. 294–305.
Brickell, E. F., A Few Results in Message Authentication, Congressus Numerantium, 43 (1984), 141–154.
Castagnoli, G., Comments on Massey's Concepts of Perfect Secrecy and Perfect Authenticity, Alta Frequenza LV1(4) (1987), 227–228.
De Soete, M., Some Constructions for Authentication-Secrecy Codes, Advances in Cryptology: Proceedings of EUROCRYPT 1988, pp. 33–39.
De Soete, M., Vedder, K., and Walker M., Cartesian Authentication Schemes, Advances in Cryptology: Proceedings of EUROCRYPT 1989, pp. 476–490.
Fåk, V., Repeated Use of Codes which Detect Deception, IEEE Transactions on Information Theory, 25(2) (1979), 233–234.
Gilbert, E. N., MacWilliams, F. J., and Sloane, N. J. A., Codes which Detect Deception, The Bell System Technical Journal, 53 (1974), 405–425.
Massey, J. L., Cryptography—A Selective Survey, Alta Frequenza, LV(1) (1986), 4–11.
Mitchell, C., Walker, M., and Wild, P., The Combinatorics of Perfect Authentication Schemes, to appear.
Simmons, G. J., A Game Theoretical Model of Digital Message Authentication, Congressus Numerantium, 34 (1982), 413–424.
Simmons, G. J., Authentication Theory/Coding Theory, Advances in Cryptology: Proceedings of CRYPTO 1984, pp. 411–432.
Simmons, G. J., Message Authentication: A Game on Hypergraphs, Congressus Numerantium, 45 (1984), 161–192.
Simmons, G. J., The Practice of Authentication, Advances in Cryptology: Proceedings of EUROCRYPT 1985, pp. 261–272.
Simmons, G. J., and Smeets, B., A Paradoxical Result in Unconditionally Secure Authentication Codes—and an Explanation, IMA Conference on Cryptography and Coding, Dec. 18–20, 1989, Cirencester, England.
Smeets, B., Bounds on the Probability of Deception in Multiple Authentication, to appear. (Partially presented at the IEEE Symposium on Information Theory, Budapest, Hungary, June 1991.)
Stinson, D. R., Some Constructions and Bounds for Authentication Codes, Journal of Cryptology, 1 (1988), 37–51.
Stinson, D. R., The Combinatorics of Authentication and Secrecy Codes, Journal of Cryptology, 2 (1990), 23–49.
Walker, M., Information-Theoretic Bounds for Authentication Schemes, Journal of Cryptology, 2 (1990), 131–143.
Author information
Authors and Affiliations
Additional information
Communicated by Gustavus J. Simmons
Rights and permissions
About this article
Cite this article
Rosenbaum, U. A lower bound on authentication after having observed a sequence of messages. J. Cryptology 6, 135–156 (1993). https://doi.org/10.1007/BF00198462
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00198462