Digital signature generation apparatus, digital signature verification apparatus, and key generation apparatus

摘要

A digital signature generation apparatus includes memory to store finite field F_q and section D(u_x(s, t), u_y(s, t), s, t) as secret key, section being one of surfaces of three-dimensional manifold A(x, y, s, t) which is expressed by x-coordinate, y-coordinate, parameter s, and parameter t and is defined on finite field Fq, x-coordinate and y-coordinate of section being expressed by functions of parameter s and parameter t, calculates hash value of message m, generates hash value polynomial by embedding hash value in 1-variable polynomial h(t) defined on finite field F_q, and generates digital signature D_s(U_x(t), U_y(t), t) which is curve on section, the x-coordinate and y-coordinate of curve being expressed by functions of parameter t, by substituting hash value polynomial in parameter s of section.