Bounds and constructions for threshold shared generation of authenticators

Shared generation of authenticates systems (or SGA-systems) generalise Simmons' traditional authentication codes when authenticators for source states are produced by collaboration of a group of senders, rather than a single sender. In this paper we study threshold SGA-systems. We derive information-theoretic and combinatorial lower bounds on the probability of success and the size of the key space, and give two key efficient constructions for SGA-systems based on den Boer A-codes and error-correcting codes. We also give a recursive construction method using perfect hash families to construct SGA-systems for large groups.