An information processing method executed by an information processing apparatus configured to store a pair of quadratic multivariate polynomials F=(f1, . . . , fm) defined in a ring K and expressed in a quadratic form and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)), the information processing method comprising:
- a step of acquiring a message generated based on the pair of quadratic multivariate polynomials F and a vector s that is an element of a set Kn;
- a step of supplying a prover supplying the message with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
- a step of acquiring response information corresponding to the selected verification pattern from the prover;
- and
- a step of verifying whether or not the prover stores the vector s based on the message, the pair of quadratic multivariate polynomials F, the vectors y, and the response information,
- wherein the vector s is a secret key,
- wherein the pair of quadratic 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 and the response information, and
- wherein, in the step of verifying whether or not the prover stores the vector s, calculation of F(x)+G(x, y) including a function G=(g1, . . . , gm) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) is executed as F(x, y)+F(y) which is calculation between quadratic forms when the message used for the verification is reproduced.