An authentication device (11-n, 21-n, 31-n) comprising: a storage (111-n) adapted to store a common key and identifiers ID,..., ID where n ∈ {1,..., N} and N is an integer greater than or equal to 2; a first output unit (112-n, 212-n) adapted to output a first challenge value corresponding to a random number along with a first authentication request; a second input unit (112-n, 212-n) adapted to receive a second challenge value along with a second authentication request; a first input unit (112-n, 212-n) adapted to receive a first response value; a second output (112-n, 212-n) unit adapted to output a second response value which is obtained by encrypting a value corresponding to the second challenge value by using the common key by a symmetric key cryptosystem; and a decision unit (117-n, 217-n) adapted to decide whether or not a decrypting result which is obtained by decrypting the first response value by using the common key and a value corresponding to the first challenge value coincide with each other, wherein the first output unit (112-n, 212 -n) is adapted to output the first authentication request for requesting first authentication of the authentication device (11-n, 21-n, 31-n) which is performed by another authentication device (11-m, 21-m, 31-m) where m ∈ {1,..., N}, the first challenge value for second authentication of the other authentication device (11-m, 21-m, 31-m) which is performed by the authentication device (11-n, 21-n, 31-n), and identifiers ID(n) and ID(m), the second input unit (112-n, 212-n) is adapted to receive the second authentication request for requesting the second authentication, the second challenge value for the first authentication, and identifiers ID(n) and ID(m) which are sent from the other authentication device (11-m, 21-m, 31-m), and the authentication device (11-n, 21-n, 31-n) further comprises a response generating unit (115-n, 215-n) adapted to decide whether or not the identifiers ID(n) and ID(m) read from the storage (111-n) and the identifiers ID(n) and ID(m) which are sent from the other authentication device (11-m, 21-m, 31-m) are respectively equal to each other, and to generate the second response value when the identifiers ID(n) and ID(m) read from the storage (111-n) and the identifiers ID(n) and ID(m) sent from the other authentication device (11-m, 21-m, 31-m) are respectively equal to each other, otherwise authentication is regarded as having failed. a storage (111-n) adapted to store a common key and identifiers ID,..., ID where n ∈ {1,..., N} and N is an integer greater than or equal to 2; a first output unit (112-n, 212-n) adapted to output a first challenge value corresponding to a random number along with a first authentication request; a second input unit (112-n, 212-n) adapted to receive a second challenge value along with a second authentication request; a first input unit (112-n, 212-n) adapted to receive a first response value; a second output (112-n, 212-n) unit adapted to output a second response value which is obtained by encrypting a value corresponding to the second challenge value by using the common key by a symmetric key cryptosystem; and a decision unit (117-n, 217-n) adapted to decide whether or not a decrypting result which is obtained by decrypting the first response value by using the common key and a value corresponding to the first challenge value coincide with each other, wherein the first output unit (112-n, 212 -n) is adapted to output the first authentication request for requesting first authentication of the authentication device (11-n, 21-n, 31-n) which is performed by another authentication device (11-m, 21-m, 31-m) where m ∈ {1,..., N}, the first challenge value for second authentication of the other authentication device (11-m, 21-m, 31-m) which is performed by the authentication device (11-n, 21-n, 31-n), and identifiers ID(n) and ID(m), the second input unit (112-n, 212-n) is adapted to receive the second authentication request for requesting the second authentication, the second challenge value for the first authentication, and identifiers ID(n) and ID(m) which are sent from the other authentication device (11-m, 21-m, 31-m), and the authentication device (11-n, 21-n, 31-n) further comprises a response generating unit (115-n, 215-n) adapted to decide whether or not the identifiers ID(n) and ID(m) read from the storage (111-n) and the identifiers ID(n) and ID(m) which are sent from the other authentication device (11-m, 21-m, 31-m) are respectively equal to each other, and to generate the second response value when the identifiers ID(n) and ID(m) read from the storage (111-n) and the identifiers ID(n) and ID(m) sent from the other authentication device (11-m, 21-m, 31-m) are respectively equal to each other, otherwise authentication is regarded as having failed.