Patent ID: 8832438

Claim:
A key generation apparatus for generating a finite field F q , a three-dimensional manifold A(x, y, s, t) which is defined as having degrees of freedom of three dimensions of a set of solutions of simultaneous equations and is used as a public key for signature verification, is expressed by an x-coordinate, a y-coordinate, a parameter s, and a parameter t, and is defined on the finite field F q , and a section which is used as a secret key for signature generation and is one of surfaces of the three-dimensional manifold A(x, y, s, t), x-coordinate and y-coordinate of the section being expressed by functions of the parameter s and the parameter t, comprising: a memory; a processor configured to: generate n (n is a positive integer), first to n-th (n is a positive integer) 2-variable polynomials u x,i (s, t) (i: 1≦i≦n) for the parameter s and the parameter t defined on the finite field F q , and n, first to n-th n 2-variable polynomials u y,i (s, t) (1≦i≦n) for the parameter s and the parameter t defined on the finite field F q ; generate n, first to n-th sections Di (1≦i≦n) by generating an i-th section Di: (x, y, s, t)=(u x,i (s, t), u y,i (s, t), s, t)(1≦i≦n) which has the i-th (1≦i≦n) 2-variable polynomials u x,i (s, t) and u y,i (s, t) as an x-coordinate and a y-coordinate, respectively; generate first to n-th x-factors and y-factors by generating an i-th x-factor (x−u x,i (s, t)) and y-factor (y−u y,i (s, t)) using the i-th (1≦i≦n) 2-variable polynomials u x,i (s, t) and u y,i (s, t); generate an equation obtained by distributing the i-th (1≦i≦n) x-factor and y-factor to a left-hand side and a right-hand side and coupling a product of n x-factors and y-factors distributed to the left-hand side and a product of n x-factors and y-factors distributed to the right-hand side by an equal sign; and generate a polynomial of the three-dimensional manifold A(x, y, s, t) by expanding the equation.