Mac tag list generating apparatus, mac tag list verifying apparatus, mac tag list generating method, mac tag list verifying method and program recording medium

Abstract

Disclosed is a MAC tag list generating apparatus capable of efficiently performing message authentication through which information pertaining to a falsified position as well as existence of falsification can be obtained. This MAC tag list generating apparatus is provided with: a group test matrix generating means for generating a group test matrix W, which is a parameter of a combined group test, on the basis of a plurality of items obtained by dividing an obtained message M; and a MAC tag list generating means that, while sharing results obtained by applying a pseudo random function to the items forming each row of the generated group test matrix W, sums the results, and then applies the summed results to pseudo random permutation to generate a MAC tag list T, which is a MAC tag list pertaining to the message M.