The present invention allows even small-size
verification devices to authenticate rights and qualifications without leaking
authentication characteristic information to third parties. A
ticket issuance device computes document private information mu from a private function f of an
interaction device owned by a user and document m to be transferred to the
interaction device when generating interaction, and issues
ticket t generated from
authentication characteristic information x and the document private information mu to the user. The
interaction device, when document m is input, generates document private information mu using a private function f specific to the interaction device, and performs interaction based on the document private information. The interaction comprises output of commitment r, input of challenge chi, output of response sigma, and message M output. The user converts interaction (r, chi, M, sigma) into interaction (r, chi, M, s) using
ticket t to perform Guillou-Quisquater
authentication.