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.