Information processing apparatus, information processing method, program, and recording medium

摘要

Provided an information processing apparatus including a message generation unit that generates a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and a vector s that is an element of a set Kn, a message supply unit that supplies the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)), an intermediate information generation unit that generates third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message, an intermediate information supply unit that supplies the third information to the verifier, and a response supply unit that supplies the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧2) verification patterns.

主权项

1. An information processing apparatus comprising:
circuitry configured to
generate a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and a vector s that is an element of a set Kn;supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));generate third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;supply the third information to the verifier; andsupply the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧2) verification patterns, wherein the vector s is a secret key, wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys, wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information, and wherein the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).