Authentication is performed at a high speed even in a device with small CPU power and memory. A challenge information computation unit of a verification instrument generates a random number and transfers the random number and identification information together as challenge information to a proving instrument. A unidirectional function computation unit of a proving instrument applies a unidirectional function to private information stored in a private information memory unit and right identification information of challenge information. A response information computation unit performs operations on a computation result of the unidirectional function and the proof support information to obtain proof information. A unidirectional function computation part applies a unidirectional function to the proof information and a random number contained in the challenge information to obtain response information and returns it to the verification unit. A unidirectional function computation unit of the verification instrument applies a unidirectional function to the proof information and a random number of the challenge information. A response information verification instrument compares the application result of the unidirectional function with the response information and acknowledges use qualifications if and only if they coincide.