A validation authority for certificates searches for and verifies paths and certificate revocation lists periodically, and classifies the paths into valid paths and invalid paths in accordance with the results of the validations, so as to register the paths in databases beforehand. Besides, in a case where a request for authenticating the validity of a certificate has been received from an end entity, the validation authority judges the validity of the public key certificate by checking in which of the valid-path database and the invalid-path database a path corresponding to the request is registered. On the other hand, in a case where the path corresponding to the validity authentication request is not registered in either of the databases, the validity of the public key certificate is authenticated by performing path search and validation anew.