摘要 |
Provided an information processing apparatus including a message generation unit that generates a message based on a pair of multi-order multivariate polynomials F = (f 1 , ..., f m ) and a vector s that is an element of a set K n , a message supply unit that supplies the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y = (y 1 , ..., y m ) = (f 1 (s), ..., f m (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. |