Combinatorial characterizations of authentication codes in verification oracle model

ABSTRACT

We consider unconditionally secure authentication codes where the adversary has access to a verification oracle that when presented with a message query gives a response of 1 or 0 if the query corresponds to an authenticated message or not, respectively.We define two types of attack, offline and online, and their two corresponding games. We define the advantage of the adversary in each game and obtain a lower bound on the maximum advantage when the adversary plays his optimal strategy. For each game, authentication codes that satisfy the lower bounds with equality are said to provide perfect protection and guarantee the minimum success chance for the attacker in the corresponding game. We prove that an optimal code for the offline attack is also an optimal code for the online attack. In both cases, we prove that perfect protection of order i implies perfect protection of order j for j < i and derive a lower bound on the number of keys for an optimal code. Finally we show that the encoding matrix of codes with perfect protection of order i and minimum number of keys correspond to a Steiner system.

REFERENCES

• 1: M. Bellare, O. Goldreich and A. Mityagin, The power of verification queries in message authentication and authenticated encryption, Cryptology ePrint Archive: Report 2004/309.
• 2: E. F. Brickell, A few results in message authentication, Congressus Numerantium 43 (1984), 141--154.
• 3: J. L. Carter, M. N. Wegman, Universal classes of hash functions, Journal of Computer and System Sciences 18(2) (1979), pp. 143--154.
• 4: E. N. Gilbert, F. J. MacWilliams and N. J. A. Sloane, Codes which detect deception, Bell System Technical Journal 53 (1974), 405--424.
• 5: J. L. Massey, Cryptography - a selective survey, Alta Frequenza LV (1) (1986), 4--11.
• 6: D. Pei, Information-theoretic bounds for authentication codes and block designs, Journal of Cryptology 8 (1995), 177--188.
• 7: U. Rosenbaum, A lower bound on authentication after having observed a sequence of messages, Journal of Cryptology 6 (1993), 135--156.
• 8: R. Safavi-Naini, L. McAven and M. Yung, General group authentication codes and their relation to "unconditionally-secure signatures", PKC'04, LNCS 2947, 231--247.
• 9: R. Safavi-Naini and P. Wild, Bounds on authentication systems in query model, Proceedings of the 2005 IEEE Information Theory Workshop on Theory and Practice in Information-Theoretic Security, 85--91, 2005.
• 10: Andrea Sgarro, Informational divergence bounds for authentication codes, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.93-101, November 1990, Houthalen, Belgium
• 11: A. Sgarro, Information-theoretic bounds for authentication frauds, Journal of Computer Security 2 (1993), 53--63.
• 12: G. J. Simmons, Message authentication: a game on hypergraphs, Congressus Numerantium 45 (1984), 161--192.
• 13: Gustavus J Simmons, Authentication theory/coding theory, Proceedings of CRYPTO 84 on Advances in cryptology, p.411-431, August 1985, Santa Barbara, California, United States
• 14: D. R. Stinson, Some constructions and bounds for authentication codes, Journal of Cryptology, v.1 n.1, p.37-51, 1988
• 15: D. R. Stinson, The combinatorics of authentication and secrecy codes, Journal of Cryptology, v.2 n.1, p.23-49, 1990 [doi>10.1007/BF02252868]
• 16: D. R. Stinson, Combinatorial characterizations of authentication codes, Designs, Codes and Cryptography, v.2 n.2, p.175-187, June 1992 [doi>10.1007/BF00124896]
• 17: Rolf S. Rees , Douglas R. Stinson, Combinatorial Characterizations of Authentication Codes II, Designs, Codes and Cryptography, v.7 n.3, p.239-259, March 1996 [doi>10.1023/A:1018094824862]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Keywords:
active adversary model, authentication codes, combinatorial bounds, unconditional security