| 摘要 |
<p>[Problem] To implement an efficient, highly-secure public-key authentication scheme. [Solution] Provided is an information processing device that: generates a message on the basis of a tuple (F = (f1, …, fm)) of multivariate polynomials and a vector s; provides said message to a verifier who knows the tuple (F) of multivariate polynomials and a vector y (y = (f1(s), …, fm(s))); and provides said verifier with response information corresponding to a verification pattern the verifier has selected from among k verification patterns. The tuple (F) of multivariate polynomials comprises polynomials (f1, …, fm) defined on a ring (R) with characteristic q and order qk. Also, a polynomial G(x1, x2) defined as G(x1, x2) = F(x1+x2) − F(x1) − F(x2) for a vector x1 (xl = (xl1, …, xln)) comprises terms proportional to (x1i)q(z) (with 1 ≤ i ≤ n, q(z) = qz, and 1 ≤ z ≤ k).</p> |
