Patent ID: 8543820

Claim:
A tag generation apparatus that adds, to a message for which input was received from the outside, a tag for distinguishing whether or not the message has been altered, comprising: a processor operating as a hash unit, a random number generation unit, a random number encryption unit, a masked encryption unit, and a tag generation unit by executing a program; and an output unit, wherein: said hash unit generates, as a hash value, a value obtained by applying a predetermined hash function to said message; said random number generation unit, when input of said message is received from the outside, generates a random number that is independent of the message; said random number encryption unit generates, as a first intermediate variable, a value obtained by applying an encryption function having a first key to said random number; said masked encryption unit generates, as a second intermediate variable, a value obtained by applying said encryption function having a second key to the exclusive OR of said random number and said hash value; said tag generation unit generates, as said tag, a value that is contained in bits of a predetermined number of bits that is less than or equal to the number of bits of said random number that are extracted from among the exclusive OR of said first intermediate variable and said second intermediate variable; said output unit transmits said message, said random number, and said tag to the destination of the message; and said masked encryption unit, together with generating said second intermediate variable, generates as a third intermediate variable, a value obtained by applying said encryption function having a third key to said hash value.