Patent ID: 8826025

Claim:
An authentication device comprising: circuitry of the device configured to: set a multi-order multivariate polynomial u i (t) (i=1 to n−1) to a secret key; set a multi-order multivariate polynomial f that satisfies f(u i (t), . . . , u n-1(t) ,t)=0 to a public key for a n-pass public key (n≧3) authentication scheme; transmit a message c to the verifier; receive, from a verification pattern reception unit, information on one verification pattern selected by the verifier from k (k≧3) verification patterns for one message c; transmit, 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; wherein the response information is calculated by using zεK n which is calculated based on a secret key s and a vector rεK n , t′εK n which is calculated based on the vector r and tεK n , and e i ′εK which is calculated based on f i (r) substituted by the vector r for the multi-order multi-variable polynomials f i and e i εK, and wherein K is a ring.