According to one embodiment, an authenticatee includes, a memory configured to store secret information XY, secret information XY which is created by multiply duplicating, at least twice, the secret information XY, and secret information XYE, a generation module configured to generate a random number A, a generation module configured to generate a random number D which is composed of at least a part of the generated random number A and a random number B which is received, a calculating module configured to generate data C by executing a compression calculated operation with respect to at least a part of the random number D and the secret information XY loaded from the memory, a generation module configured to generate data ν, and a bit-by-bit addition module configured to calculate an calculated result Z from the data ν and the data C.