According to one embodiment, an authenticatee includes, a memory configured to store secret information XYmain, XYsub, and secret information XYmain
E , XYsub
E, 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 generation module configured to generate secret information XY based on the secret information XYmain, XYsub loaded from the memory, 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, 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.