Homomorphic authentication codes for network coding

Authentication codes (A-codes) are a well studied technique to provide unconditionally secure authentication. An A-code is defined by a map that associates a pair formed by a message and a key to a tag. A-codes linear in the keys have been studied for application to distributed authentication schemes. In this paper, we address the dual question, which is the study of A-codes that are linear in the messages. This is usually an undesired property, except in the context of network coding. Regarding these A-codes, we derive some lower bounds on security parameters when key space is known. We also show a lower bound on key size when security parameter values are given (with some special properties) and construct some codes meeting the bound. We finally present a variant of these codes that authenticate multiple messages with the same key while preserving unconditional security. Copyright (C) 2013 John Wiley & Sons, Ltd.