Authentication device, authentication method, program, and signature generation device

摘要

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.

主权项

1. An authentication device comprising:
circuitry of the device configured to: set a multi-order multivariate polynomial ui(t) (i=1 to n−1) to a secret key; set a multi-order multivariate polynomial f that satisfies f(ui(t), . . . , un-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εKn which is calculated based on a secret key s and a vector rεKn, t′εKn which is calculated based on the vector r and tεKn, and ei′εK which is calculated based on fi(r) substituted by the vector r for the multi-order multi-variable polynomials fi and eiεK, and wherein K is a ring.