Patent ID: 7836304

Claim:
A digital signature generation apparatus comprising: a memory to store (1) a finite field F q and (2) a section D(u x (s, t), u y (s, t), s, t) as a secret key, the section being one of surfaces of a three-dimensional manifold A(x, y, s, t), the three dimensional manifold being defined as having degrees of freedom of three dimensions of a set of solutions of simultaneous equations, and which is expressed by an x-coordinate, a y-coordinate, a parameter s, and a parameter t and is defined on the finite field Fq, the x-coordinate and y-coordinate of the section being expressed by functions of the parameter s and the parameter t; a calculation unit configured to calculate a hash value of a message m; a first generation unit configured to generate a hash value polynomial by embedding the hash value in a 1-variable polynomial h(t) defined on the finite field F q ; and a second generation unit configured to generate a digital signature D s (U x (t), U y (t), t) which is a curve on the section, the x-coordinate and y-coordinate of the curve being expressed by functions of the parameter t, by substituting the hash value polynomial in the parameter s of the section.