An authentication method between an authenticatee, which stores secret information XYmain, XYsub, and secret information XYmain E, XYsub E, which is created by encrypting the secret information XYmain, XYsub, and an authenticator which authenticates the authenticatee, wherein XYsub < XYmain, XYsub E < XYmain E in data size, comprising: executing, by the authenticator, a decryption process on the secret information XYmain E, XYsub E, which is received from the authenticatee, and sharing the secret information XYmain, XYsub; generating, by the authenticator, secret information XY based on the secret information XYmain, XYsub; receiving, by the authenticatee, a random number B which is generated by the authenticator, and loading the secret information XYmain, XYsub; generating, by the authenticatee, secret information XY based on the secret information XYmain, XYsub; generating, by the authenticatee, a random number A and data v, wherein ν having a probability η of occurrence of 1 and wherein η < 0.5; generating, by the authenticatee, a random number D which is composed of at least a part of the generated random number A and the received random number B; generating, by the authenticatee, data C by executing a compression operation with respect to at least a part of the random number D and the secret information XY; transmitting, by the authenticatee, an calculated result Z from the data ν and the data C, to the authenticator; generating, by the authenticator, a random number D which is composed of at least a part of the generated random number B and the received random number A; generating, by the authenticator, data C by executing a compression operation with respect to at least a part of the random number D and the secret information XY; and executing, by the authenticator, a determination process by using the received calculated result Z and the generated data C. executing, by the authenticator, a decryption process on the secret information XYmain E, XYsub E, which is received from the authenticatee, and sharing the secret information XYmain, XYsub; generating, by the authenticator, secret information XY based on the secret information XYmain, XYsub; receiving, by the authenticatee, a random number B which is generated by the authenticator, and loading the secret information XYmain, XYsub; generating, by the authenticatee, secret information XY based on the secret information XYmain, XYsub; generating, by the authenticatee, a random number A and data v, wherein ν having a probability η of occurrence of 1 and wherein η < 0.5; generating, by the authenticatee, a random number D which is composed of at least a part of the generated random number A and the received random number B; generating, by the authenticatee, data C by executing a compression operation with respect to at least a part of the random number D and the secret information XY; transmitting, by the authenticatee, an calculated result Z from the data ν and the data C, to the authenticator; generating, by the authenticator, a random number D which is composed of at least a part of the generated random number B and the received random number A; generating, by the authenticator, data C by executing a compression operation with respect to at least a part of the random number D and the secret information XY; and executing, by the authenticator, a determination process by using the received calculated result Z and the generated data C.