An authentication device receives each authentication context including an output information block, an input information block, and an authenticator block. The output information block includes a process result and process result identification information. The input information block includes a process result and process result identification information. The authentication device verifies each authenticator block. The authentication device searches for the output information block having the same value of process result identification information as the value of process result identification information in the input information block from other authentication contexts based on process result identification information in the input information block included in each authentication context. The authentication device verifies whether or not the process result in the input information block is equal to the process result in the searched output information block, and authenticates that all the authentication contexts have validity when all the verification results are valid.