Hypersphere-based multivariable public key signature/verification system and method

1. A method for multivariate public key signature/verification, based on hypersphere, comprising:

a signature process:

step A, receiving, by a processor, a message to be signed, storing the message and transmitting the message to a first affine transformation inversion component for performing affine transformation inversion on the message;

step B, transmitting the message processed by the first affine transformation inversion component to a trapdoor component, and performing operations of constructing a system of linear equations and solving the system of linear equations about the processed message respectively by a linear equations construction component and a linear equations solution component in the trapdoor component, to obtain a solution set forming by one group or multiple groups of solutions from the operation of solving the system of linear equations;

step C, selecting any one group of solutions from the solution set and transmitting the group of solutions to the second affine transformation inversion component for performing affine transformation inversion on the group of solutions; and

step D, using the result finally obtained in the step C as a signature of the message, transmitting the message and the signature to an end user by the processor; and

a verification process:

step E, receiving, by the processor, the message and the signature of the message, storing the message and the signature, and transmitting the signature to a public key transformation component; and

step F, substituting, by the public key transformation component, the signature into each of multivariate polynomials of a public key map, returning data calculated by the public key transformation component to the processor, and determining whether the data is equal to the message stored in the processor by the processor: if the data is equal to the message, the processor outputs “1” to the end user, indicating that the signature is valid; otherwise, the processor outputs “0” to the end user, indicating that the signature is invalid;

wherein the signature process further comprises:

in Step A, the message to be signed is (y 1 ′, . . . , y n ′)ϵF″ and the affine transformation inversion is ( y 1 , . . . , y n )=T −1 (y 1 ′, . . . , y n ′)

in step B, the message processed by the first affine transformation inversion component is ( y 1 , . . . , y n ), and the linear equations construction component simultaneously uses m groups of data (c i,1 , c i,2 , . . . , c i,n ) and ({tilde over (y)} 1 , . . . , {tilde over (y)} m ) pre-allocated by a scheduler in the trapdoor component to construct a first system of equations as below:

{

(

-

c

1

,

1

)

2

+

…

+

(

-

c

1

,

n

)

2

=

…

(

-

c

m

,

1

)

2

+

…

+

(

-

c

m

,

n

)

2

=

extending the first system of equations to a second system of equations:

{

(

2

-

2

⁢

c

1

,

1

⁢

+

c

1

,

1

2

)

+

…

+

(

2

-

2

⁢

c

1

,

n

⁢

+

c

1

,

n

2

)

=

…

(

2

-

2

⁢

c

m

,

1

⁢

+

c

m

,

1

2

)

+

…

+

(

2

-

2

⁢

c

m

,

n

⁢

+

c

m

,

n

2

)

=

,

subtracting the second system of equations from the first system of equations to obtain a third system of equations:

{

(

2

⁢

c

2

,

1

-

2

⁢

c

1

,

1

)

⁢

+

…

+

(

2

⁢

c

2

,

n

-

2

⁢

c

1

,

n

)

⁢

(

c

1

,

n

2

-

c

2

,

n

2

)

=

-

…

(

2

⁢

c

m

,

1

-

2

⁢

c

m

-

1

,

1

)

⁢

+

…

+

(

2

⁢

c

m

,

n

-

2

⁢

c

m

-

1

,

n

)

⁢

(

c

m

-

1

,

n

2

-

c

m

,

n

2

)

=

-

and converting the third system of equations into a matrix form to obtain a fourth system of equations:

[

(

2

⁢

c

2

,

1

-

2

⁢

c

1

,

1

)

⁢

⁢

…

⁢

⁢

(

2

⁢

c

2

,

n

-

2

⁢

c

1

,

n

)

…

(

2

⁢

c

m

,

1

-

2

⁢

c

m

-

1

,

1

)

⁢

⁢

…

⁢

⁢

(

2

⁢

c

m

,

n

-

2

⁢

c

m

-

1

,

n

)

]

⁡

[

…

]

=

[

(

-

)

+

∑

j

=

1

n

⁢

(

c

2

,

j

2

-

c

1

,

j

2

)

…

(

-

)

+

∑

j

=

1

n

⁢

(

c

m

,

j

2

-

c

m

-

1

,

j

2

)

]

wherein the fourth system of equations is the system of linear equations about ({tilde over (x)} 1 , . . . , {tilde over (x)} n ) constructed by the linear equations construction component; and solving, by the linear equations solution component, the fourth system of equations with a Gaussian elimination method to obtain a solution set formed by one group or multiple groups of solutions, wherein the number of groups is set as d, and the solution set is denoted by ({tilde over (x)} a , . . . , {tilde over (x)} in ), (1≤i≤d);

in step C, the group of solutions are ( x 1 , . . . , x n ) and the second affine transformation inversion is (x 1 ′, . . . , x n ′)=S −1 ( x 1 , . . . , x n ); and

in step D, the result is (x 1 ′, . . . , x n ′) the message is (y 1 ′, . . . , y n ′) and the signature is (x 1 ′, . . . , x n ′) and

wherein the verification process further comprises:

in step E, the message is (y 1 ′, . . . , y n ′) and the signature is (x 1 ′, . . . , x n ′) and

in step F, each of multivariate polynomials of public key map are P(x 1 , . . . , x n ), that is, calculating p 1 (x 1 ′, . . . , x n ′), . . . , p n (x 1 ′, . . . , x n ′) respectively to have results respectively denoted by y 1 ″, . . . , y n ″, transmitting y 1 ″, . . . , y n ″ to the processor by the public key transformation component, and determining whether y 1 ″, . . . , y n ″ is equal to the message (y 1 ′, . . . , y n ′) stored in the processor by the processor: if the y 1 ″, . . . , y n ″) is equal to the message, the processor outputs “1” to the end user, indicating that the signature is valid; otherwise, the processor outputs “0” to the end user, indicating that the signature is invalid.

2. The method of claim 1 , wherein before the signature process, the method for multivariate public key signature/verification further comprise making the signature module be operatable when a selector coupled to the processor is in an open state; and

before the verification process, the method further comprises making the verification module be operatable when a selector coupled to the processor is in a close state.

3. The method of claim 2 , wherein the processor comprises a scheduler coupled to the selector, and a memory, wherein the scheduler is configured to identify and manage the open state and close state of the selector, and to control and manage data stored in the processor to be scheduled to a corresponding component for a corresponding operation.

4. The method of claim 1 , wherein the processor further comprises a memory configured to implement data storage of the processor.