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

Patent metadata

Field	Value
Publication number	US-9948462-B2
Application number	US-201415022435-A
Country	US
Kind code	B2
Filing date	Dec 30, 2014
Priority date	Jan 13, 2014
Publication date	Apr 17, 2018
Grant date	Apr 17, 2018

Abstract

A hypersphere-based multivariable public key signature/verification system includes signature and verification modules, wherein the signature module comprises a processor, an affine transformation inversion part I, a trap door part and an affine transformation inversion part II. Corresponding operations are sequentially executed on a message, one or more groups of solutions are produced after the processing of the trapdoor part, a group of solutions are randomly selected, then a signature is continuously produced by the various parts, and finally the signature, together with the message, is transmitted to the processor. The verification module comprises a processor and a public key transformation part, wherein the processor transmits a signature to the public key transformation part to execute an operation, and then judges whether the obtained data is equal to a message in a memory or not: if so, the signature is valid, otherwise the signature is invalid.

First claim

The invention claimed is:

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

⁢

Assignees

• Univ South China Tech

Inventors

• Tang Shaohua
• Chen Jiahui

Classifications

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• H04L9/30 Primary

  Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy · CPC title

• H04L9/0618

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · CPC title

• H04L9/3093 Primary

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title