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

A key generation method for generating a finite field Fq, 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 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 Fq, 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, by a processor a first 2-variable polynomial λx(s, t) for the parameter s and the parameter t defined on the finite field Fq;
• 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 Fq;
• generating two 2-variable polynomials ux(s, t) and vx(s, t) for the parameter s and the parameter t defined on the finite field Fq so that a difference {ux(s, t)−vx(s, t)} between the two 2-variable polynomials equals the first 2-variable polynomial λx(s, t);
• generating two 2-variable polynomials uy(s, t) and vy(s, t) for the parameter s and the parameter t defined on the finite field Fq so that a difference {uy(s, t)−vy(s, t)} between the two 2-variable polynomials equals the second 2-variable polynomial
• generating a section D1:
• (x, y, s, t)=(ux(s, t), uy(s, t), s, t) which has the 2-variable polynomial ux(s, t) as an x-coordinate, and the 2-variable polynomial uy(s, t) as a y-coordinate, and a section D2:
• (x, y, s, t)=(vx(s, t), vy(s, t), s, t) which has the 2-variable polynomial vx(s, t) as an x-coordinate, and the 2-variable polynomial vy(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.

A key generation program for generating a finite field Fq, 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 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 Fq, 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:

• a first program instruction which when executed by a computer processor, would generate a first 2-variable polynomial λx(s, t) for the parameter s and the parameter t defined on the finite field Fq;
• a second program instruction which when executed by the computer processor, would 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 Fq;
• a third program instruction which when executed by the computer processor, would generate two 2-variable polynomials ux(s, t) and vx(s, t) for the parameter s and the parameter t defined on the finite field Fq so that a difference {ux(s, t)−vx(s, t)} between the two 2-variable polynomials equals the first 2-variable polynomial λx(s, t);
• a fourth program instruction which when executed by the computer processor, would generate two 2-variable polynomials uy(s, t) and vy(s, t) for the parameter s and the parameter t defined on the finite field Fq so that a difference {uy(s, t)−vy(s, t)} between the two 2-variable polynomials equals the second 2-variable polynomial λy(s, t);
• a fifth program instruction which when executed by the computer processor, would generate a section D1:
• (x, y, s, t)=(ux(s, t), uy(s, t), s, t) which has the 2-variable polynomial ux(s, t) as an x-coordinate, and the 2-variable polynomial uy(s, t) as a y-coordinate, and a section D2:
• (x, y, s, t)=(vx(s, t), vy(s, t), s, t) which has the 2-variable polynomial vx(s, t) as an x-coordinate, and the 2-variable polynomial vy(s, t) as a y-coordinate;
• and
• a sixth program instruction which when executed by the computer processor, would generate a polynomial of the three-dimensional manifold A(x, y, s, t) which includes the section D1 and the section D2.