A MAC tag list generation apparatus, on reception of a nonce N unique value to each MAC generation process and a message M, generates a t×m group test matrix H serving as combinatorial group testing parameters for s (a positive integer) which is the number of the MACs to be generated, generates a MAC tag list T=(T[1], . . . , T[t]) by generating a MAC value T[i] corresponding to the i-th test (i=1, . . . , t) using the group test matrix H, the nonce N, and pseudorandom functions F and G with variable length input and fixed length output for the message M, and outputs the MAC tag list.