A message authentication apparatus compresses a message M into a value H of 2n bits, and divides the value H into two values H[1] and H[2] each having n bits. The message authentication apparatus extracts two values U[1] and U[2] each having min{t, n/2} bits from the value H[1], generates a value V[1] of t bits, using as input the message M and the value U[1], and generates a value V[2] of t bits, using as input the message M and the value U[2]. The message authentication apparatus encrypts the value H[2] by a tweakable block cipher E, using the value V[1] as a tweak, to generate a value Z[1], and encrypts the value H[2] by the tweakable block cipher E, using the value V[2] as a tweak, to generate a value Z[2]. The message authentication apparatus generates an authenticator Z from the value Z[1] and the value Z[2].