摘要 |
Provided is an authentication device including a key setting unit for setting a multi-order polynomial ui(t) (i=1 to n-1) to a secret key and setting a multi-order polynomial f that satisfies f(u1(t), . . . , un-1(t),t)=0 to a public key, a message transmission unit for transmitting a message c to a verifier, a verification pattern reception unit for receiving information on one verification pattern selected by the verifier from k (k>=3) verification patterns for one message c, and a response transmission unit for transmitting, to the verifier, response information, among k types of response information, corresponding to the information on the verification pattern received by the verification pattern reception unit. The response information is information that enables calculation of the secret key ui in a case all of the k verification patterns for the message c performed by using the k types of response information have been successful.
|