Patent ID: 8433912

Claim:
An authentication device comprising: a processor; a key setting unit for setting a multi-order multivariate polynomial ui(t) (i=1 to n−1) to a secret key and setting a multi-order multivariate polynomial f that satisfies f(u1(t), . . . , u n-1 (t),t)=0 to a public key for a n-pass public key (n≧3) authentication scheme; a message transmission unit for transmitting a message c from a prover to a verifier, wherein the prover attempts to prove a legitimacy to the verifier; a verification pattern reception unit, at the prover, 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 the k verification patterns of response information, corresponding to the information on the verification pattern received by the verification pattern reception unit, wherein 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 verification patterns of response information have been successful.