A first data generation unit generates identification key information (FKey) that may be decrypted from the identification key information (IDKey) using key management information (FKB) read from an authenticatee. A decryption unit decrypts encrypted secret identification information (E-SecretID) using the identification key information (FKey) to generate secret identification information (SecretID). A second data generation unit generates a first session key (Skey) using the first key information (Hkey) and a random number. A one-way conversion unit performs a one-way conversion process on the secret identification information (SecretID) using the generated first session key (SKey) to generate first one-way conversion data (Oneway-ID).