An authenticating device 100 includes an authentication processing unit 197 to perform an authentication process with a communication device 200 using an authentication key, an update key generating unit 160 to generate a new authentication key when the communication device 200 does not hold an authentication key to be used in the authentication process by the authentication processing unit 197, and to generate a new authentication key for updating the authentication key when the communication device 200 holds the authentication key but the authentication process with the communication device 200 by the authentication processing unit 197 fails. The authentication processing unit 197 performs again the authentication process with the communication device 200 using the new authentication key generated by the update key generating unit 160.