According to one embodiment, an authentication method between an authenticatee which stores key information having a data structure composed of a key transition record, secret information XY of a matrix form, and secret information XYE which is created by encrypting the secret information XY, and an authenticator which authenticates the authenticatee, includes selecting, by the authenticator, a record corresponding to a device index of the authenticator from the key information which is received from the authenticatee, and decrypting the record by a device key, thereby taking out a key transition, and executing, by the authenticator, a decryption process on the secret information XYE, which is received from the authenticatee, by using the corresponding key transition, and sharing the secret information XY.