Patent ID: 8458471

Claim:
A digital signature verification apparatus comprising: a memory to store a finite field F q and a polynomial of a three-dimensional manifold A(x, y, s, t) defined as having degrees of freedom of three dimensions of a set of solutions of simultaneous equations, which 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 ; a processor configured to; input a message m; input a digital signature Ds: (U x (t), U y (t), t) corresponding to the message m, the digital signature being a curve on a section D(u x (s, t), u y (s, t), s, t) which is one of surfaces of the three-dimensional manifold A(x, y, s, t), the x-coordinate and y-coordinate of the section being expressed by functions of the parameter t, the digital signature being generated by using the section as a secret key; calculate a hash value of the message m; generate a hash value polynomial by embedding the hash value in a 1-variable polynomial for the parameter t defined on the finite field F q ; calculate an algebraic surface X(x, y, t) corresponding to the hash value by substituting the hash value polynomial in the parameter s of the polynomial stored in the memory; and verify authenticity of the message and the digital signature by substituting a function U x (t) representing the x-coordinate of the digital signature and a function U y (t) representing the y-coordinate of the digital signature in an x-coordinate and a y-coordinate, respectively, of the algebraic surface X(x, y, t).