Tag generation apparatus, tag verification apparatus, communication system, tag generation method, tag verification method, and recording medium

A tag verification apparatus that verifies a message that is transmitted in from the outside by using a tag to distinguish whether or not the message has been altered, comprising:

• a hash unit that generates, as a verification hash value, a value that is obtained by applying a predetermined hash function to said message;
• a random number encryption unit that generates, as a first verification intermediate variable, a value obtained by applying an encryption function having a first verification key to a random number that was transmitted in together with said message;
• a masked encryption unit that generates, as a second verification intermediate variable, a value obtained by applying said encryption function having a second verification key to the exclusive OR of said random number and said verification hash value;
• a tag generation unit that generates, as a verification 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 verification intermediate variable and said second verification intermediate variable;
• and
• a comparison unit that compares said verification tag and said tag that was transmitted in from the outside together with said message.

A communication system having 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 and a tag verification apparatus that uses said tag to verify said message that was transmitted in from the transmission origin of said message;

• wherein:
• said tag generation apparatus:
• generates as a hash value a value that is obtained by applying a predetermined hash function to said message;
• when input of said message is received from the outside, generates a random number that is independent of the message, generates as a first intermediate variable a value that is obtained by applying an encryption function having a first key to said random number, 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, 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 and that are extracted from among the exclusive OR of said first intermediate variable and said second intermediate variable;
• and transmits said message, said random number, and said tag to said tag verification apparatus that is the destination of the message;
• and
• said tag verification apparatus:
• generates, as a verification hash value, a value that is obtained by applying said hash function to said message that is transmitted in, generates as a first verification intermediate variable a value obtained by applying said encryption function having a first verification key to a random number that was transmitted in together with said message, generates as a second verification intermediate variable a value that is obtained by applying said encryption function having a second verification key to the exclusive OR of said random number that was transmitted in and said verification hash value, generates as a verification tag a value that is contained in bits of said predetermined number of bits that are extracted from among the exclusive OR of said first verification intermediate variable and said second verification intermediate variable, and compares said verification tag and the tag that was transmitted in from the outside together with said message.

A tag generation method that adds, to a message for which input is received from the outside, a tag for distinguishing whether or not the message has been altered, the tag generation method comprising:

• a hash process of generating as a hash value a value that is obtained by applying a predetermined hash function to said message;
• a random number generation process of, when input of said message is received from the outside, generating a random number that is independent of the message;
• a random number encryption process of generating as a first intermediate variable a value that is obtained by applying an encryption function having a first key to said random number;
• a masked encryption process of generating as a second intermediate variable a value that is obtained by applying said encryption function having a second key to the exclusive OR of said random number and said hash value;
• a tag generation process of generating 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 the random number and that are extracted from among the exclusive OR of said first intermediate variable and said second intermediate variable;
• and
• an output process of transmitting said message, said random number, and said tag to the destination of the message.

A tag verification method of verifying a message that is transmitted in from the outside by using a tag to distinguish whether or not the message has been altered, comprising:

• a hash process of generating as a verification hash value a value obtained by applying a predetermined hash function to said message;
• a random number encryption process of generating as a first verification intermediate variable a value that is obtained by using an encryption function having a first verification key to a random number that was transmitted in together with said message;
• a masked encryption process of generating as a second verification intermediate variable a value obtained by applying said encryption function having a second verification key to the exclusive OR of said random number and said verification hash value;
• a tag generation process of generating as a verification tag a value contained in bits of a predetermined number of bits that is less than or equal to the number of bits of said random number and that are extracted from among the exclusive OR of said first verification intermediate variable and said second verification intermediate variable;
• and
• a comparison process of comparing said verification tag and said tag that was transmitted in from the outside together with said message.

A recording medium that records a program that causes a tag generation apparatus, which adds to a message for which input is received from the outside a tag for distinguishing whether or not the message has been altered, to execute:

• a hash procedure of generating as a hash value a value obtained by applying a predetermined hash function to said message;
• a random number generation procedure of, when input of said message is received from the outside, generating a random number that is independent of said message;
• a random number encryption procedure of generating as a first intermediate variable a value obtained by applying an encryption function having a first key to said random number;
• a masked encryption procedure of generating 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;
• a tag generation procedure of generating as said tag a value contained in bits of a predetermined number of bits that is less than or equal to the number of bits of said random number and that are extracted from among the exclusive OR of said first intermediate variable and said second intermediate variable;
• and
• an output procedure of transmitting said message, said random number, and said tag to the destination of said message.

A recording medium that records a program that causes a tag verification apparatus, which verifies a message that is transmitted in from the outside by using a tag to distinguish whether or not the message has been altered, to execute:

• a hash procedure of generating as a verification hash value a value that is obtained by applying a predetermined hash function to said message;
• a random number encryption procedure of generating as a first verification intermediate variable a value obtained by applying an encryption function having a first verification key to a random number that is transmitted in together with said message;
• a masked encryption procedure of generating as a second verification intermediate variable a value that is obtained by applying said encryption function having a second verification key to the exclusive OR of said random number and said verification hash value;
• a tag generation procedure of generating as a verification 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 and that are extracted from among the exclusive OR of said first verification intermediate variable and said second verification intermediate variable;
• and
• a comparison procedure of comparing said verification tag with said tag that is transmitted in from the outside together with said message.