摘要 |
Provided is an authentication device including a key setting unit for setting sepsilonKn to a secret key and setting a multi-order polynomial fi(x1, . . . , xn) (i=1 to m) on a ring K and yi=fi(s) 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, where the response information is information that enables calculation of the secret key s 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.
|