An information processing apparatus including a random number generation unit configured to generate a pair of random numbers from a seed, a message generation unit configured to generate a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn, a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)), and a response supply unit configured to supply the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧3) verification patterns.