An information processing apparatus comprising: a message generating unit that generates messages of N times (where N ≥ 2) based on a multi-order multivariate polynomial set F=(f 1,...,f m) defined on a ring K and a vector s that is an element of a set K n, and calculates a first hash value based on the messages of N times; a message providing unit that provides a verifier holding the multi-order multivariate polynomial set F and a vector y=(y 1,...,y m)=(f 1 (s),...,f m (s)) with the first hash value; an interim information generating unit that generates third information of N times using first information randomly selected by the verifier on the respective messages of N times and second information of N times obtained when the messages are generated, and generates a second hash value based on the third information of N times; an interim information providing unit that provides the verifier with the second hash value; and a response providing unit that provides the verifier with response information of N times corresponding to verification patterns selected by the verifier from among k (where k ≥ 2) verification patterns on the respective messages of N times, a part of messages, and a part of third information, wherein the vector s is a secret key, wherein the multi-order multivariate polynomial set F is a public key or a system parameter, wherein the vector y is a public key, wherein the messages and the third information are information obtained by performing an operation prepared for a verification pattern corresponding to the response information in advance using the public keys, the first information, and the response information, or information obtained based on the response information, wherein the part of messages and the part of third information are information that is not obtained even when the operation prepared for the verification pattern corresponding to the response information in advance is performed using the multi-order multivariate polynomial set F, the vector y, and the response information, and wherein the multi-order multivariate polynomial set F is set in a manner that F b (x,y) defined as F b (x,y) = F(x+y)-F(x)-F(y) is bilinear for x and y. a message generating unit that generates messages of N times (where N ≥ 2) based on a multi-order multivariate polynomial set F=(f 1,...,f m) defined on a ring K and a vector s that is an element of a set K n, and calculates a first hash value based on the messages of N times; a message providing unit that provides a verifier holding the multi-order multivariate polynomial set F and a vector y=(y 1,...,y m)=(f 1 (s),...,f m (s)) with the first hash value; an interim information generating unit that generates third information of N times using first information randomly selected by the verifier on the respective messages of N times and second information of N times obtained when the messages are generated, and generates a second hash value based on the third information of N times; an interim information providing unit that provides the verifier with the second hash value; and a response providing unit that provides the verifier with response information of N times corresponding to verification patterns selected by the verifier from among k (where k ≥ 2) verification patterns on the respective messages of N times, a part of messages, and a part of third information, wherein the vector s is a secret key, wherein the multi-order multivariate polynomial set F is a public key or a system parameter, wherein the vector y is a public key, wherein the messages and the third information are information obtained by performing an operation prepared for a verification pattern corresponding to the response information in advance using the public keys, the first information, and the response information, or information obtained based on the response information, wherein the part of messages and the part of third information are information that is not obtained even when the operation prepared for the verification pattern corresponding to the response information in advance is performed using the multi-order multivariate polynomial set F, the vector y, and the response information, and wherein the multi-order multivariate polynomial set F is set in a manner that F b (x,y) defined as F b (x,y) = F(x+y)-F(x)-F(y) is bilinear for x and y.