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

• US 20080037776A1
• Filed: 07/24/2006
• Published: 02/14/2008
• Est. Priority Date: 07/25/2005
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Akiyama, Koichiro, Goto, Yasuhiro
• Granted Patent: US 7,836,304 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

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.

Claims

1. 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) 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.

2. The apparatus according to claim 1, wherein the memory stores a plurality of different sections D_i(u_x,i(s, t), u_y,i(s, t), s, t) (i is an arbitrary positive integer which meets 0≦

i≦

n), and

the second generation unit generates the digital signature by selecting one of the sections D_i stored in the memory.

3. 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) 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 first input unit configured to input a message m;

a second input unit configured to 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

a first calculation unit configured to calculate a hash value of the message m;

a generation unit configured to 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;

a second calculation unit configured to 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

a verification unit configured to verifying 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).

4. A key generation apparatus for generating a finite field F_q, a three-dimensional manifold A(x, y, s, t) which 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 first generation unit configured to generate a first 2-variable polynomial λ

_x(s, t) for the parameter s and the parameter t defined on the finite field F_q;

a second generation unit configured to generate a second 2-variable polynomial λ

_y(s, t) which is divisible by the first 2-variable polynomial λ

_x(s, t) and is defined on the finite field F_q;

a third generation unit configured to generate two 2-variable polynomials u_x(s, t) and v_x(s, t) for the parameter s and the parameter t defined on the finite field F_q so that a difference {u_x(s, t)−

v_x(s, t)} between the two 2-variable polynomials equals the first 2-variable polynomial λ

_x(s, t);

a fourth generation unit configured to generate two 2-variable polynomials u_y(s, t) and v_y(s, t) for the parameter s and the parameter t defined on the finite field F_q so that a difference {u_y(s, t)−

v_y(s, t)} between the two 2-variable polynomials equals the second 2-variable polynomial λ

_y(s, t);

a section generation unit configured to generate a section D1;

(x, y, s, t)=(u_x(s, t), u_y(s, t), s, t) which has the 2-variable polynomial u_x(s, t) generated by the third generation unit as an x-coordinate, and the 2-variable polynomial u_y(s, t) generated by the fourth generation unit as a y-coordinate, and a section D2;

(x, y, s, t)=(v_x(s, t), v_y(s, t), s, t) which has the 2-variable polynomial v_x(s, t) generated by the third generation unit as an x-coordinate, and the 2-variable polynomial v_y(s, t) generated by the fourth generation unit as a y-coordinate; and

a manifold generation unit configures to generate a polynomial of the three-dimensional manifold A(x, y, s, t) which includes the section D1 and the section D2.

5. A key generation apparatus for generating a finite field F_q, a three-dimensional manifold A(x, y, s, t) which 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 first generation unit 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) (i;

1≦

i≦

n) for the parameter s and the parameter t defined on the finite field F_q;

a second generation unit configured to 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) generated by the first generation unit as an x-coordinate and a y-coordinate, respectively;

a third generation unit configured to 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) generated by the first generation unit;

a fourth generation unit configured to 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

a fifth generation unit configured to generate a polynomial of the three-dimensional manifold A(x, y, s, t) by expanding the equation generated by the fourth generation unit.

6. The apparatus according to claim 5, wherein the first generation unit includes:

a first determination unit configured to determine a maximum value h_x of a degree associated with the parameter s of the 2-variable polynomial u_x,i(s, t) and a maximum value kx of a degree associated with the parameter t;

a first generation unit configured to generate the i-th 2-variable polynomial u_x,i(s, t) (i;

1≦

i≦

n) which includes a plurality of monomials each of which has, as a factor, at least one of a variable s whose degree is equal to or less than the maximum value hx and a variable t whose degree is equal to or less than the maximum value kx, and a term of s^hxt^kx;

a second determination unit configured to determine a maximum value hy of a degree associated with the parameter s of the 2-variable polynomial u_y,i(s, t) and a maximum value ky of a degree associated with the parameter t; and

a second generation unit configured to generate the i-th 2-variable polynomial u_y,i(s, t) (i;

1≦

i≦

n) which includes a plurality of monomials each of which has, as a factor, at least one of a variable s whose degree is equal to or less than the maximum value h_y and a variable t whose degree is equal to or less than the maximum value ky, and a term of s^hyt^ky.

7. A digital signature generation method including:

storing, in a memory, (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) 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;

calculating a hash value of a message m;

generating a hash value polynomial by embedding the hash value in a 1-variable polynomial h(t) defined on the finite field F_q; and

generating 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.

8. The method according to claim 7, wherein storing stores, in the memory, a plurality of different sections D_i(u_x,i(s, t), u_y,i(s, t), s, t) (i is an arbitrary positive integer which meets 0≦

i≦

n), and

generating the digital signature generates the digital signature by selecting one of the sections D_i stored in the memory.

9. A digital signature verification method including:

storing, in a memory, a finite field F_q and a polynomial of a three-dimensional manifold A(x, y, s, t) 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;

inputting a message m;

inputting 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

calculating a hash value of the message m;

generating 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;

calculating 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

verifying 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).

10. A key generation method for generating a finite field F_q, a three-dimensional manifold A(x, y, s, t) which 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, the method including:

generating a first 2-variable polynomial λ

_x(s, t) for the parameter s and the parameter t defined on the finite field F_q;

generating a second 2-variable polynomial λ

_y(s, t) which is divisible by the first 2-variable polynomial λ

_x(s, t) and is defined on the finite field F_q;

generating two 2-variable polynomials u_x(s, t) and v_x(s, t) for the parameter s and the parameter t defined on the finite field F_q so that a difference {u_x(s, t)−

v_x(s, t)} between the two 2-variable polynomials equals the first 2-variable polynomial λ

_x(s, t);

generating two 2-variable polynomials u_y(s, t) and v_y(s, t) for the parameter s and the parameter t defined on the finite field F_q so that a difference {u_y(s, t)−

v_y(s, t)} between the two 2-variable polynomials equals the second 2-variable polynomial

generating a section D1;

(x, y, s, t)=(u_x(s, t), u_y(s, t), s, t) which has the 2-variable polynomial u_x(s, t) as an x-coordinate, and the 2-variable polynomial u_y(s, t) as a y-coordinate, and a section D2;

(x, y, s, t)=(v_x(s, t), v_y(s, t), s, t) which has the 2-variable polynomial v_x(s, t) as an x-coordinate, and the 2-variable polynomial v_y(s, t) as a y-coordinate; and

generating a polynomial of the three-dimensional manifold A(x, y, s, t) which includes the section D1 and the section D2.

11. A key generation method for generating a finite field F_q, a three-dimensional manifold A(x, y, s, t) which 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, the method including:

generating 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) (i;

1≦

i≦

n) for the parameter s and the parameter t defined on the finite field F_q;

generating n, first to n-th sections D_i (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;

generating 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);

generating 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

generating a polynomial of the three-dimensional manifold A(x, y, s, t) by expanding the equation.

12. The method according to claim 11, wherein generating first to n-th 2-variable polynomials u_x,i(s, t) includes:

determining a maximum value hx of a degree associated with the parameter s of the 2-variable polynomial u_x,i(s, t) and a maximum value kx of a degree associated with the parameter t;

generating the i-th 2-variable polynomial u_x,i(s, t) (i;

1≦

i≦

n) which includes a plurality of monomials each of which has, as a factor, at least one of a variable s whose degree is equal to or less than the maximum value h_x and a variable t whose degree is equal to or less than the maximum value kx, and a term of s^hxt^kx;

determining a maximum value hy of a degree associated with the parameter s of the 2-variable polynomial u_y,i(s, t) and a maximum value ky of a degree associated with the parameter t; and

generating the i-th 2-variable polynomial u_y,i(s, t) (i;

1≦

i≦

n) which includes a plurality of monomials each of which has, as a factor, at least one of a variable s whose degree is equal to or less than the maximum value h_y and a variable t whose degree is equal to or less than the maximum value ky, and a term of s^hyt^ky.

13. A digital signature generation program stored on a computer readable medium, the program including:

first program instruction means for instructing a computer processor to store, in a memory, (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) 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;

second program instruction means for instructing the computer processor to calculate a hash value of a message m;

third program instruction means for instructing the computer processor 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

fourth program instruction means for instructing the computer processor 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.

14. The program according to claim 13, wherein the first program instruction means for instructing the computer processor to store, in the memory, a plurality of different sections D_i(u_x,i(s, t), u_y,i(s, t), s, t) (i is an arbitrary positive integer which meets 0≦

i≦

n), and

the fourth program instruction means for instructing the computer processor to generate the digital signature by selecting one of the sections D_i stored in the memory.

15. A digital signature verification program stored on a computer readable medium, the program including:

first program instruction means for instructing a computer processor to store, in a memory, a finite field F_q and a polynomial of a three-dimensional manifold A(x, y, s, t) 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;

second program instruction means for instructing the computer processor to input a message m;

third program instruction means for instructing the computer processor to 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

fourth program instruction means for instructing the computer processor to calculate a hash value of the message m;

fifth program instruction means for instructing the computer processor to 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;

sixth program instruction means for instructing the computer processor to 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

seventh program instruction means for instructing the computer processor to 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).

16. A key generation program for generating a finite field F_q, a three-dimensional manifold A(x, y, s, t) which 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, the program stored on a computer readable medium, the program including:

first program instruction means for instructing a computer processor to generate a first 2-variable polynomial λ

_x(s, t) for the parameter s and the parameter t defined on the finite field F_q;

second program instruction means for instructing the computer processor to generate a second 2-variable polynomial λ

_y(s, t) which is divisible by the first 2-variable polynomial λ

_x(s, t) and is defined on the finite field F_q;

third program instruction means for instructing the computer processor to generate two 2-variable polynomials u_x(s, t) and v_x(s, t) for the parameter s and the parameter t defined on the finite field F_q so that a difference {u_x(s, t)−

v_x(s, t)} between the two 2-variable polynomials equals the first 2-variable polynomial λ

_x(s, t);

fourth program instruction means for instructing the computer processor to generate two 2-variable polynomials u_y(s, t) and v_y(s, t) for the parameter s and the parameter t defined on the finite field F_q so that a difference {u_y(s, t)−

v_y(s, t)} between the two 2-variable polynomials equals the second 2-variable polynomial λ

_y(s, t);

fifth program instruction means for instructing the computer processor to generate a section D1;

(x, y, s, t)=(u_x(s, t), u_y(s, t), s, t) which has the 2-variable polynomial u_x(s, t) as an x-coordinate, and the 2-variable polynomial u_y(s, t) as a y-coordinate, and a section D2;

(x, y, s, t)=(v_x(s, t), v_y(s, t), s, t) which has the 2-variable polynomial v_x(s, t) as an x-coordinate, and the 2-variable polynomial v_y(s, t) as a y-coordinate; and

sixth program instruction means for instructing the computer processor to generate a polynomial of the three-dimensional manifold A(x, y, s, t) which includes the section D1 and the section D2.

17. A key generation program for generating a finite field F_q, a three-dimensional manifold A(x, y, s, t) which 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, the program stored on a computer readable medium, the program including:

first program instruction means for instructing a computer processor 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) (i;

1≦

i≦

n) for the parameter s and the parameter t defined on the finite field F_q;

second program instruction means for instructing the computer processor to 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;

third program instruction means for instructing the computer processor to 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);

fourth program instruction means for instructing the computer processor to 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

fifth program instruction means for instructing the computer processor to generate a polynomial of the three-dimensional manifold A(x, y, s, t) by expanding the equation.

18. The program according to claim 17, wherein the first program instruction means for instructing the computer processor (1) to determine a maximum value hx of a degree associated with the parameter s of the 2-variable polynomial u_x,i(s, t) and a maximum value kx of a degree associated with the parameter t;

(2) to generate the i-th 2-variable polynomial u_x,i(s, t) (i;

1≦

i≦

n) which includes a plurality of monomials each of which has, as a factor, at least one of a variable s whose degree is equal to or less than the maximum value h_x and a variable t whose degree is equal to or less than the maximum value kx, and a term of s^hxt^kx;

(3) to determine a maximum value hy of a degree associated with the parameter s of the 2-variable polynomial u_y,i(s, t) and a maximum value ky of a degree associated with the parameter t; and

(4) to generate the i-th 2-variable polynomial u_y,i(s, t) (i;

1≦

i≦

n) which includes a plurality of monomials each of which has, as a factor, at least one of a variable s whose degree is equal to or less than the maximum value hy and a variable t whose degree is equal to or less than the maximum value ky, and a term of s^hyt^ky.