Patent ID: 7512801

Claim:
A signing apparatus, including a processor, used in an authentication system which uses authentication data created by applying one-way functions to information divisible into a plurality of data divisions thereof, the apparatus comprising: a dividing unit which divides the information into the plurality of data divisions; an authenticator creating unit which creates a first authenticator by applying a first one-way function using a first key to all of the data divisions, and creates a second authenticator by applying a second one-way function using a second key to each all of the data divisions, where the first and second keys are different; and an appending unit which links the first and second authenticators, and appends linked authenticators to the information for sending with the information to a certifying apparatus in the authentication system, wherein the dividing unit divides the information into the plurality of data divisions including a first data division and a second data division, each having a pre-specified length, and the authenticator creating unit creates the first authenticator by applying the first one-way function using the first key to a first initial value and one of the data divisions to obtain a first result and by applying the first one-way function using the first key to the first result obtained by previous application of the first one-way function and each of the other data divisions respectively, and creates the second authenticator by applying the second one-way function using the second key to a second initial value and the first one of the data divisions to obtain a second result and by applying the second one-way function using the second key to the second result obtained by previous application of the second one-way function and each of the other data divisions respectively.