Information processing apparatus, information processing method, program, and recording medium

An information processing apparatus comprising:

• circuitry configured to
• store a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
• acquire a message generated based on the pair of multi-order multivariate polynomials F and a vector s which is an element of a set Kn;
• supply randomly selected first information to a prover that supplies the message;
• acquire third information generated by the prover based on the first information and second information obtained at a time of generation of the message;
• supply the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
• acquire response information corresponding to the selected verification pattern from the prover;
• and
• verify whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of multi-order multivariate polynomials F, and the response information,
• wherein the vector s is a secret key,
• wherein the pair of multi-order 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, the first information, the third information, and the response information, and
• wherein the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qZ, and 1≦z≦k).

An information processing method comprising:

• generating 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;
• supplying, by circuitry of an information processing apparatus, the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
• generating, by the circuitry, third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
• supplying, by the circuitry, the third information to the verifier;
• and
• supplying, by the circuitry, the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧2) verification patterns,
• wherein the vector s is a secret key,
• wherein the pair of multi-order 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, the first information, the third information, and the response information, and
• wherein the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

An information processing method comprising:

• by an information processing apparatus storing a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and vectors y=(y1, Ym)=(f1(s), fm(s)),
• acquiring a message generated based on the pair of multi-order multivariate polynomials F and a vector s which is an element of a set Kn;
• supplying, by circuitry of an information processing apparatus, randomly selected first information to a prover that supplies the message;
• acquiring third information generated by the prover based on the first information and second information obtained at a time of generation of the message;
• supplying, by the circuitry, the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
• and
• acquiring response information corresponding to the selected verification pattern from the prover;
• verifying, by the circuitry, whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of multi-order multivariate polynomials F, and the response information,
• wherein the vector s is a secret key,
• wherein the pair of multi-order 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, the first information, the third information, and the response information, and
• wherein the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

A non-transitory computer-readable recording medium having a program recorded thereon, the program causing a computer to:

• generate 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;
• supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
• generate third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
• supply the third information to the verifier;
• and
• supply the verifier with response information corresponding to a verification pattern which the verifier selects from among k (where k≧2) verification patterns,
• wherein the vector s is a secret key,
• wherein the pair of multi-order 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, the first information, the third information, and the response information, and
• wherein the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1 . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).

A non-transitory computer-readable recording medium having a program recorded thereon, the program causing a computer to:

• store a pair of multi-order multivariate polynomials F=(f1, . . . , fm) and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
• acquire a message generated based on the pair of multi-order multivariate polynomials F and a vector s that is an element of a set Kn;
• supply randomly selected first information to a prover that supplies the message;
• acquire third information generated by the prover based on the first information and second information obtained at a time of generation of the message;
• supply the prover with information on one verification pattern randomly selected from among k (where k≧3) verification patterns;
• acquire response information corresponding to the selected verification pattern from the prover;
• and
• verify whether or not the prover stores the vector s based on the message, the first information, the third information, the pair of multi-order multivariate polynomials F, and the response information,
• wherein the vector s is a secret key,
• wherein the pair of multi-order 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, the first information, the third information, and the response information, and
• wherein the pair of multi-order multivariate polynomials F include polynomials f1, . . . , fm defined in a ring R of a characteristic q and an order qk and are set in a manner that a polynomial G(x1, x2) defined as G(x1, x2)=F(x1+x2)−F(x1)−F(x2) with respect to vectors x1=(xl1, . . . , xln) (where l=1, 2) is configured as a term proportional to (x1i)q(z) (where 1≦i≦n, q(z)=qz, and 1≦z≦k).