Multivariate Signature Method for Resisting Key Recovery Attack

Abstract

A multivariate signature method for resisting key recovery attack, which establishes a new signature verification condition by adding additional value of signature. The verification condition implies verification of internal information x and y, thereby effectively resisting key recovery attack generated by the existence of equivalence key. Specifically, the method includes the three stages of data preprocessing, signature generation and signature verification. The invention is a signature authentication method based on polynomial equations of a plurality of variables in a finite field, which can effectively resist the key recovery attack, provide the basic technical support for the information security and the establishment of the trust system in the quantum computer era, and provide a secure digital signature option in the quantum era. The present invention is especially suitable for use under application condition which has limited storage and processing time, such as smart cards, wireless sensor networks and dynamic RFID tags.

Claims

1. A multivariate signature method for resisting Key Recovery Attack, characterized in that, the method comprises the steps of: Step 1: selecting system parameters: Taking a finite field F, positive integers n and m, a n-th extended field of F as F.sup.n, a m-th extended field of F as F.sup.m, taking a set of multivariable quadratic polynomial equations q.sub.1(x.sub.1, . . . , x.sub.n), . . . , q.sub.m(x.sub.1, . . . , x.sub.n) from F.sup.n to F.sup.m which is recorded as Q and then Q represents a center mapping of multivariate public key cryptographic system, where an input variable is n and an output variable is m, using Q.sup.−1 for the inverse polynomial of polynomial Q, where Q.sup.−1 is held by a legitimate user, taking another reversible affine transformation S and T on F.sup.n and F.sup.m as a secret key and their inverse polynomials are recorded as S.sup.−1 and T.sup.−1 respectively, then randomly selecting a set of n number n-quaternary multivariable polynomial equations (g.sub.1(x.sub.1, . . . , x.sub.n), . . . , g.sub.n(x.sub.1, . . . , x.sub.n)) on F.sup.n, where its polynomial vector is recorded as G, that is G(x.sub.1, . . . , x.sub.n)=(g.sub.1(x.sub.1, . . . , x.sub.n), . . . , g.sub.n(x.sub.1, . . . , x.sub.n)), and two unidirectional irreversible polynomial equations set H and {tilde over (H)}, wherein a user secret key consists of three parts, S, T and G, wherein H and {tilde over (H)} are secret selection of a credible third party which is only used for generating public key, where the inverse polynomial of G is expressed as G.sup.−1, the corresponding public key consists of five polynomials, which are: P=T∘Q∘S, H∘G.sup.−1∘S, H∘S, {tilde over (H)}∘Q∘G.sup.−1∘S, {tilde over (H)}∘T.sup.−1 respectively, where the operator ∘ represents a synthesis of operation, which is, processing substituting calculation from left to right in order; Step 2: generating signature: a coding of a known message M is vector (u.sub.1, . . . , u.sub.m) which is recorded as u, a signature is generated by the following steps: (2.1) generating a forward signature: (2.1a) substituting u=(u.sub.1, . . . , u.sub.m) which is the coding of message M into T.sup.−1 by the secret key T.sup.−1, obtaining (y.sub.1, . . . , y.sub.m), which is recorded as y; (2.1 b) substituting the obtained result y into the inverse polynomial Q.sup.−1 of the center mapping Q, obtaining (x.sub.1, . . . , x.sub.n), which is recorded as x; (2.1c) substituting the obtained result x into the inverse polynomial S.sup.−1 of the secret key S, obtaining (v.sub.1, . . . , v.sub.n), which is recorded as v, then v is the forward signature of the coding u of the message M; (2.2) generating a backward signature: (2.2a) substituting the obtained result x into the secret key G, obtaining G(x.sub.1, . . . , x.sub.n)=(g.sub.1(x.sub.1, . . . , x.sub.n), . . . , g.sub.n(x.sub.1, . . . , x.sub.n))=(g.sub.1, . . . , g.sub.n), which is recorded as g; (2.2b) substituting the obtained result g into the inverse polynomial S.sup.−1 of the secret key S, obtaining S.sup.−1(g)=S.sup.−1∘G(x)=(v.sub.g1, . . . , v.sub.gn), which is recorded as v.sub.g, then v.sub.g is the backward signature of the coding u of the message M; (2.3) processing a cascade of the forward signature and the back signature v∥v.sub.g, which is the signature of the coding u of the message M; Step 3, verifying the signature: (3.1) using public key P to process verification: (3.1a) substituting the forward signature v=(v.sub.1, . . . , v.sub.n) into the public key P, obtaining P(v.sub.1, . . . , v.sub.n)=(p.sub.1(v.sub.1, . . . , v.sub.n), . . . , p.sub.m(v.sub.1, . . . , v.sub.n)), obtaining and recording results as u′=(u′.sub.1, . . . , u′.sub.n); (3.1b) determining if u′ equals to the coding u of the original message M; (3.2) using public key H∘S and H∘G.sup.−1∘S to process verification: (3.2a) substituting the forward signature v=(v.sub.1, . . . , v.sub.n) into the public key H∘S, obtaining H∘S(v)=H∘S(v.sub.1, . . . , v.sub.n)=H(S(v.sub.1, . . . , v.sub.n)), and recording obtained results as h=(h.sub.1, . . . , h.sub.n); (3.2b) substituting the backward signature v.sub.g=(v.sub.g1, . . . , v.sub.gn) into the public key H∘G.sup.−1∘S, obtaining H∘G.sup.−1∘S(v.sub.g)=H∘G.sup.−1∘S(v.sub.g.sub.1, . . . , v.sub.g.sub.n)=H(G.sup.−1(S(v.sub.g.sub.1, . . . , v.sub.g.sub.n))), and recording obtained results as h′=(h′.sub.1, . . . , h′.sub.n); (3.2c) determining if h and h′ are equal; (3.3) using public key {tilde over (H)}∘Q∘G.sup.−1∘S and {tilde over (H)}∘T.sup.−1 to process verification: (3.3a) for the coding u of the message M, substituting u into the public key {tilde over (H)}∘T.sup.−1, obtaining {tilde over (H)}∘T.sup.−1(u)={tilde over (H)}(T.sup.−1(u)), and recording obtained results as {tilde over (h)}=(h.sub.1, . . . , {tilde over (h)}.sub.n); (3.3b) for the backward signature v.sub.g, substituting v.sub.g into the public key {tilde over (H)}∘Q∘G.sup.−1∘S, obtaining {tilde over (H)}∘Q∘G.sup.−1∘S(v.sub.g)={tilde over (H)}(Q(G.sup.−1(S(v.sub.g)))), recording obtained results as {tilde over (h)}′=({tilde over (h)}′.sub.1, . . . , {tilde over (h)}′.sub.n); (3.3c) determining if {tilde over (h)} and {tilde over (h)}′ are equal; if (3.1b), (3.2c) and (3.3c) are true, then v∥v.sub.g is a legitimate signature of the coding u of the message M, otherwise, the signature is invalid and rejected.

2. The multivariate signature method for resisting Key Recovery Attack, characterized in that, in the step 1, all of the S, T, G are reversible affine transformation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0044] FIG. 1 is a schematic diagram, showing the principle of the signature generation according to a preferred embodiment of the present invention.

[0045] FIG. 2 is a schematic diagram, showing the principle of the signature verification to according to a preferred embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

[0046] The preferred embodiments of the present invention are further described in detail with reference to the accompanying drawings and embodiments.

I. The Mathematical Theory Applied by the Present Invention

[0047] (1) Finite Field

[0048] A finite field is a set of finite elements that contain two operations of addition and multiplication, and that satisfies the properties of both addition and multiplication with the combined law, the exchange law, the inverse element of nonzero element, and the distribution rate of multiplication to addition. The number of elements in the field is called the order of the domain. The q-order finite field is often recorded as F=GF(q) or abbreviated as F. The operations on a finite field are modulo operations.

[0049] Transformation

[0050] F is a finite field, (y.sub.1, . . . , y.sub.n)=f(x.sub.1, . . . , x.sub.n), x.sub.i, y.sub.iεF is call a transformation, which refers to the existence of rules of changes which cause (x.sub.1, . . . , x.sub.n) to process through the rules of changes to become (y.sub.1, . . . , y.sub.n) the rules of changes is recorded as f and called transformation.

[0051] Multivariate Problem

[0052] Multivariate problems are also referred to as multivariable quadratic-difficult problems. Since the security of the multivariable public key cryptosystem is based on solving a set of multivariable nonlinear polynomial equations on a finite field:

p.sub.1(x.sub.1, . . . ,x.sub.n)=p.sub.2(x.sub.1, . . . ,x.sub.n)= . . . =p.sub.m(x.sub.1, . . . ,x.sub.n)=0,

[0053] the problem to be solved is an NP-C problem, wherein the coefficients and variables of p.sub.i are taken from the finite field F. Usually, the equation p.sub.i is quadratic. Based on the scheme of multivariable problem construction, the pre-security basis comes from the difficulty of direct cracking the public key quadratic equation, that is, the known public-key solution equations are a nondeterministic polynomial time-complete (NP-C) difficult problem.

II. Implementation Method

[0054] Step 1: Selecting System Parameters:

[0055] Taking a finite field F, positive integers n and m, a n-th extended field of F as F.sup.n, a m-th extended field of F as F.sup.m, taking a set of multivariable quadratic polynomial equations q.sub.1(x.sub.1, . . . , x.sub.n), . . . , q.sub.m (x.sub.1, . . . , x.sub.n) from F.sup.n to F.sup.m which is recorded as Q and then Q represents a center mapping of multivariate public key cryptographic system, where an input variable is n and an output variable is m, using (Q.sup.−1 for the inverse polynomial of polynomial Q, where Q.sup.−1 is held by a legitimate user, taking another reversible affine transformation S and T on F.sup.n and F.sup.m as a secret key and their inverse polynomials are recorded as S.sup.−1 and T.sup.−1 respectively, then randomly selecting a set of n number n-quaternary multivariable polynomial equations (g.sub.1(x.sub.1, . . . , x.sub.n), . . . , g.sub.n(x.sub.1, . . . , x.sub.n)) on F.sup.n, where its polynomial vector is recorded as G, that is G(x.sub.1, . . . , x.sub.n)=(g.sub.1(x.sub.1, . . . , x.sub.n), . . . , g.sub.n(x.sub.1, . . . , x.sub.n)), and two unidirectional irreversible polynomial equations set H and {tilde over (H)}, wherein a user secret key consists of three parts, S, T and G, wherein H and H are secret selection of a credible third party which is only used for generating public key, where the inverse polynomial of G is expressed as G.sup.−1, the corresponding public key consists of five polynomials, which are: P=T∘S, H∘G.sup.−1∘S, H∘S, {tilde over (H)}∘Q∘G.sup.−1∘S, {tilde over (H)}∘T.sup.−1 respectively, where the operator ∘ represents a synthesis of operation, which is, processing substituting calculation from left to right in order.

[0056] Step 2: Generating Signature

[0057] a coding of a known message M is vector (u.sub.1, . . . , u.sub.m) which is recorded as u, a signature is generated by the following steps:

[0058] (2.1) generating a forward signature:

[0059] (2.1a) substituting u=(u.sub.1, . . . , u.sub.m) which is the coding of message M into T.sup.−1 by the secret key T.sup.−1, obtaining (y.sub.1, . . . , y.sub.m), which is recorded as y;

[0060] (2.1b) substituting the obtained result y from the above step (2.1a) into the inverse polynomial Q.sup.−1 of the center mapping Q, obtaining (x.sub.1, . . . , x.sub.n), which is recorded as x;

[0061] (2.1c) substituting the obtained result x from the above step (2.1b) into the inverse polynomial S′ of the secret key S, obtaining (v.sub.1, . . . , v.sub.n), which is recorded as v, then v is the forward signature of the coding u of the message M.

[0062] (2.2) generating a backward signature

[0063] (2.2a) substituting the obtained result x from the above step (2.1b) into the secret key G, obtaining G(x.sub.1, . . . , x.sub.n)=(g.sub.1(x.sub.1, . . . , x.sub.n), . . . , g.sub.n(x.sub.1, . . . , x.sub.n))=(g.sub.1, . . . , g.sub.n), which is recorded as g;

[0064] (2.2b) substituting the obtained result g from the above step (2.2a) into the inverse polynomial S.sup.−1 of the secret key S, obtaining S′ (g)=S.sup.−1∘G(x)=(v.sub.g1, . . . , v.sub.gn), which is recorded as v.sub.g, then v.sub.g is the backward signature of the coding u of the message M;

[0065] (2.3) processing a cascade of the forward signature and the back signature v∥v.sub.g, which is the signature of the coding u of the message M.

[0066] Referring to FIG. 2 of the drawings, the implementation of signature verification according to the present invention is as follows:

[0067] Step 3, Verifying the Signature:

[0068] (3.1) using public key P to process verification.

[0069] (3.1a) substituting the forward signature v=(v.sub.1, . . . , v.sub.n) into the public key P, obtaining P(v.sub.1, . . . , v.sub.n)=(p.sub.1(v.sub.1, . . . , v.sub.n), . . . , p.sub.m(v.sub.1, . . . , v.sub.n)), obtaining and recording results as u′=(u′.sub.1, . . . , u′.sub.n).

[0070] (3.1 b) determining if u′ equals to the coding u of the original message M.

[0071] (3.2) using public key H∘S and H∘G.sup.−1∘S to process verification.

[0072] (3.2a) substituting the forward signature v=(v.sub.1, . . . , v.sub.n) into the public key H∘S, obtaining H∘S(v)=H∘S(v.sub.1, . . . , v.sub.n)=H(S(v.sub.1, . . . , v.sub.n)), and recording obtained results as h=(h.sub.1, . . . , h.sub.n);

[0073] (3.2b) substituting the backward signature v.sub.g=(v.sub.g1, . . . , v.sub.gn) into the public key H∘G.sup.−1∘S, obtaining H∘G.sup.−1∘S(v.sub.g)=H∘G.sup.−1∘S(v.sub.g1, . . . , v.sub.gn)=H(G.sup.−1(S(v.sub.g1, . . . , v.sub.gn))), and recording obtained results as h′=(h′.sub.1, . . . , h′.sub.n);

[0074] (3.2c) determining if h and h′ are equal.

[0075] (3.3) using public key {tilde over (H)}∘Q∘G.sup.−1∘S and {tilde over (H)}∘T.sup.−1 to process verification.

[0076] (3.3a) for the coding u of the message M, substituting u into the public key {tilde over (H)}∘T.sup.−1, obtaining {tilde over (H)}∘T.sup.−1(u)={tilde over (H)}(T.sup.−1(u)), and recording obtained results as {tilde over (h)}=({tilde over (h)}.sub.1, . . . , {tilde over (h)}.sub.n);

[0077] (3.3b) for the backward signature v.sub.g, substituting v.sub.g into the public key {tilde over (H)}∘Q∘G.sup.−1∘S, obtaining {tilde over (H)}∘Q∘G.sup.−1∘S(v.sub.g)={tilde over (H)}(Q(G.sup.−1(S(v.sub.g)))), recording obtained results as {tilde over (h)}′=({tilde over (h)}′.sub.1, . . . , {tilde over (h)}′.sub.n);

[0078] (3.3c) determining if {tilde over (h)} and {tilde over (h)}′ are equal.

[0079] If(3.1b), (3.2c) and (3.3c) are true, then v∥v.sub.g is a legitimate signature of the coding u of the message M, otherwise, the signature is invalid and rejected.

[0080] The present invention provides a signature scheme based on a finite field, which is a correct scheme and is capable of resisting a key recovery attack.

[0081] The Correctness of the Signature

[0082] Let the recipient receives the signature v∥v.sub.g, If the signature is progressively generated as described above and does not change during transmission, then due to:

[0083] (1) Since the forward signature v is generated by sequentially processing the coding of message M by private key T.sup.−1, center mapping Q.sup.−1 and private key S.sup.−1, that is v=(v.sub.1, . . . , v.sub.n)=S.sup.−1∘Q.sup.−1∘T.sup.−1(u.sub.1, . . . , u.sub.m), then obviously, by substituting the resulting forward signature v into the public key P, we have established

[00001]$\begin{array}{c}P\left(v\right)=.Math.P\left(S^{-1}\circ Q^{-1}\circ T^{-1}\left(u_1,\mathrm{.Math.}.Math.,u_m\right)\right)\\ =.Math.P\circ S^{-1}\circ Q^{-1}\circ T^{-1}\left(u\right)\\ =.Math.T\circ Q\circ S\circ S^{-1}\circ Q^{-1}\circ T^{-1}\left(u\right)=0,\end{array}$

[0084] i.e. the verification formula (3.1b) is established.

[0085] (2) From the backward signature v.sub.g=S.sup.−1∘G(x.sub.1, . . . , x.sub.n) and the forward signature v=S.sup.−1(x.sub.1, . . . , x.sub.n), then obviously, S(v)=(x.sub.1, . . . , x.sub.n)=G.sup.−1∘S(v.sub.g), and then we obtain H∘S(v) and H∘G.sup.−1∘S(v.sub.g) are equal, i.e. the verification formula (3.2c) is established.

[0086] (3) From the backward signature v.sub.g=S.sup.−1∘G(x.sub.1, . . . , x.sub.n) and the coding u of message M, then Q∘G.sup.−1∘S(v.sub.g)=y=T.sup.−1(u), and then we have H∘G.sup.−1S(v.sub.g)=H∘S(v) established, i.e. the verification formula (3.3c) is established.

[0087] Anti-Forgery of the Signature

[0088] The present invention provides a signature scheme, which is based on a multivariable polynomial, is unforgeable to the signature forgery attack of known public key. In the following, it is theoretically proven from the cryptographic theory that the digital signature scheme of the present invention can resist signature forgery attacks, and in particular, key recovery attacks against multivariable cryptographic systems.

[0089] Proof: It is well known that the multivariable system has an “equivalent key” characteristic, that is, the same public key corresponds to multiple private keys, which is also known as “Key Redundancy”, and is reflected as follows: for two different private keys (T,Q,S) and (T′,Q,S′), we have T∘Q∘S=P=T′∘Q∘S′. Therefore, key recovery attack refers to as long as the attacker in attacking a multi-variable system gets an equivalent private key (T′,Q,S′), even if the correct private key is not obtained (T,Q,S), the attack can also success. The model provided by the present invention can effectively defend against the attack. The proof is provided as follows:

[0090] If an attacker wants to successfully forge a signature, there must be a forward signature v and a backward signature v.sub.g, that can be established through (3.1b), (3.2c) and (3.3c). However, even if the forger (the attacker) can obtain an equivalent key (T′,Q,S′) through a key recovery attack to obtain a forward signature, which is recorded as {circumflex over (v)}, and a backward signature which is recorded as {circumflex over (v)}.sub.g, the verification of (3.1c) and (3.2c) cannot be established. This is because the public keys H∘G.sup.−1∘S and H∘S set a limitation that the private key for generating the signature must be S and cannot be the equivalent key, such as Ŝ; the public keys {tilde over (H)}∘Q∘G.sup.−1∘S and {tilde over (H)}∘T.sup.−1 then set a limitation that the private key for generating the signature must be T and cannot be the equivalent key, such as {circumflex over (T)}. Accordingly, in the absence of the correct private keys S and T, even if the forger can generate a signature by key recovery attack through equivalent key, the signature cannot be validated by the verification of (3.2c) and (3.3c) because the signature is not generated by the correct private keys S and T. If the attacker randomly guesses a forward signature v and a backward signature v.sub.g, then since both {circumflex over (v)} and {circumflex over (v)}.sub.g are n-vector derived from the q-order finite field, so the probability of success is only

[00002]$\frac{1}{q^{2.Math.n.Math.}}->0$

(q is the order of the finite field).

[0091] From above, the present invention is effective against an equivalent key recovery attack against a multivariate signature system.

III. Preferred Embodiment

[0092] Select center mapping of HFE (Hidden Field Equations) multi-variable system as an example, the signature scheme is as follows:

[0093] (1) HFE Embodiment

[0094] Let be a q-order finite field, be the n-order extension of , π: .fwdarw..sup.n be the isomorphic mapping of the extended domain to the vector space, where π(a.sub.0+a.sub.1x+ . . . +a.sub.n-1x.sup.n-1)=(a.sub.0, . . . , a.sub.n-1). Center mapping:

[00003]$\tilde{Q}\left(X\right):=\underset{\underset{q^i+q^j\le d}{0\le i,j\le d}}{.Math.}.Math.C_{i,j}.Math.X^{q^i+q^j}+\underset{\underset{q^k\le d}{0\le k\le d}}{.Math.}.Math.B_k.Math.X^{q^i}+A,$

[0095] where i,jε, frequency is dε, (dε is the degree, is integer) C.sub.i,jεE is quadratic coefficient, B.sub.kεE is a monomial coefficient, AεE is a constant, that these coefficients are randomly selected and the degree must be less than the parameter d.

[0096] Q is a reversible transformation which can be obtained by a variant of the Berlekamp algorithm on the domain, the complexity of this step is O(nd.sup.2 log d+d.sup.3), therefore the parameter d cannot be too large. The center mapping Q(x.sub.1, . . . , x.sub.n) is the mapping from to , which is:

Q(x.sub.1, . . . ,x.sub.n)=(q.sub.1(x.sub.1, . . . ,x.sub.n), . . . ,q.sub.n(x.sub.1, . . . ,x.sub.n))=π∘∘π.sup.−1(x.sub.1, . . . ,x.sub.n),

[0097] Wherein q.sub.1(x.sub.1, . . . , x.sub.n), i=1, . . . , m is the quadratic polynomial equation of n variables. Let S and T be two random reversible affine transformation on .sup.n, then define P(x.sub.1, . . . , x.sub.n)=p.sub.1(x.sub.1, . . . , x.sub.n), . . . ,p.sub.n(x.sub.1, . . . , x.sub.n))=T∘Q∘S(x.sub.1, . . . , x.sub.n). Here, all of the polynomials is a second-degree polynomial.

[0098] The system is used as a signature algorithm and the process is as follows.

[0099] Alice wants to send Bob a message (v.sub.1, . . . , v.sub.n) signed by herself. First, she uses her private key S.sub.Alice,T.sub.Alice for the coding (u.sub.1, . . . , u.sub.m) of message M to carry out signature: (I) calculate (y.sub.1, . . . , y.sub.m)=T.sub.Alice.sup.−1(u.sub.1, . . . , u.sub.m); (II) calculate (x.sub.1, . . . , x.sub.n)=Q.sup.−1(y.sub.1, . . . , y.sub.m)=π∘{tilde over (Q)}.sup.−1∘π.sup.−1(y.sub.1, . . . , y.sub.m); (III) calculate (v.sub.1, . . . , v.sub.n)=S.sub.Alice.sup.−1 (x.sub.1, . . . x.sub.n); then send the message (u.sub.1, . . . , u.sub.m) and signature (v.sub.1, . . . , v.sub.n) together to Bob through communication network.

[0100] Bob receives the message (u.sub.1, . . . , u.sub.m) and the signature (v.sub.1, . . . , v.sub.n) together through public channel from Alice and wants to determine whether the signature is really come from Alice. So Bob found Alice's public key in the public to verify. Bob uses P.sub.Alice to calculate P.sub.Alice(v.sub.1, . . . , v.sub.n) for the signature (v.sub.1, . . . , v.sub.n), the results is recorded as (u′.sub.1, . . . , u′.sub.m), then determines if the value (u′.sub.1, . . . , u′.sub.m) is equal to the original message (u.sub.1, . . . , u.sub.m), if they are equal, then the signature (v.sub.1, . . . , v.sub.n) is accepted, if not then rejected.

[0101] When multivariate system is used as a signature scheme, as with the traditional multivariate signature model, only the public key authentication is required and whether the user has a valid private key is not verified. The original HFE system has been cracked: in 1999, Kipins and Shamir use a recalculation method to provide an effective key recovery attack.

[0102] (2) In the followings, take Q as the center mapping of the HFE system.

[0103] Alice gives a secure signature by selecting a reversible quadratic polynomial polynomial G.sub.Alice as a private key and two random unidirectional irreversible polynomials H and {tilde over (H)} as auxiliary functions.

[0104] When Alice wants to send Bob a message (u.sub.1, . . . , u.sub.m) signed by herself, (I) use her private key T.sub.Alice, calculate (y.sub.1, . . . , y.sub.m)=T.sub.Alice.sup.−1 (u.sub.1, . . . , u.sub.m); (II) calculate (x.sub.1, . . . , x.sub.n)=Q.sup.−1(y.sub.1, . . . , y.sub.m)=π∘{tilde over (Q)}.sup.−1∘π.sup.−1(y.sub.1, . . . , y.sub.m); (III) use private key S.sub.Alice, calculate (v.sub.1, . . . , v.sub.n)=S.sub.Alice.sup.−1(x.sub.1, . . . , x.sub.n); (IV) use private key G.sub.Alice, calculate G.sub.Alice=G(x.sub.1, . . . , x.sub.n)=(g.sub.1(x.sub.1, . . . , x.sub.n), . . . , g.sub.n(x.sub.1, . . . , x.sub.n))=(g.sub.1, . . . , g.sub.n); (V) use private key S.sub.Alice, calculate (v.sub.g1, . . . , v.sub.gn)=S.sup.−1(g)=S.sup.−1∘G(x); (VI) cascade (v.sub.1, . . . , v.sub.n) and (v.sub.g1, . . . , v.sub.gn) to obtain v.sub.1, . . . , v.sub.n∥v.sub.g1, . . . , v.sub.gn, which is the signature of the message (u.sub.1, . . . , u.sub.n).

[0105] Bob receives the message (u.sub.1, . . . , u.sub.m) and the signature v.sub.1, . . . , v.sub.n∥v.sub.g1, . . . , v.sub.gn through public channel from Alice. Bob wants to determine whether the signature is really come from Alice. Bob found Alice's public key P.sub.Alice, H∘S.sub.Alice, H∘G.sup.−1∘S.sub.Alice, {tilde over (H)}∘Q∘G.sup.−1∘S.sub.Alice and {tilde over (H)}∘T.sub.Alice.sup.−1, in the public, then process verification of the signature v.sub.1, . . . , v.sub.n∥v.sub.g1, . . . , v.sub.gn:

[0106] (I) Bob uses Alice's public key P.sub.Alice, substitute forward signature v=(v.sub.1, . . . , v.sub.n) into P.sub.Alice, obtain the results and record as (u′.sub.1, . . . , u′.sub.m), determine whether the value (u′.sub.1, . . . , u′.sub.m) is equal to the original message (u.sub.1, . . . , u.sub.m), if they are the same, then step (II) determination is carried out, otherwise rejected the signature.

[0107] (II) Bob substitute backward signature (v.sub.g1, . . . , v.sub.gn) into {tilde over (H)}∘Q∘G.sup.−1∘S.sub.Alice, to obtain {tilde over (H)}∘Q∘G.sup.−1∘S.sub.Alice (v.sub.g1, . . . , v.sub.gn), the results obtained is recorded as ({tilde over (h)}′.sub.1, . . . , {tilde over (h)}′.sub.m); substitute the message (u.sub.1, . . . , u.sub.m) into public key {tilde over (H)}∘T.sub.Alice.sup.−1, obtain the result {tilde over (H)}∘T.sub.Alice.sup.−1(u.sub.1, . . . , u.sub.n), record as ({tilde over (h)}.sub.1, . . . , {tilde over (h)}.sub.m), then determine whether ({tilde over (h)}′.sub.1, . . . , {tilde over (h)}′.sub.m) and ({tilde over (h)}′.sub.1, . . . , {tilde over (h)}.sub.m) are equal, if they are equal, then Bob will accept the signature of the message, if not, the signature is invalid and rejected.

[0108] Obviously, in the application of the new model on HFE, for the same message (u.sub.1, . . . , u.sub.m), the signature is change from the original (v.sub.1, . . . , v.sub.n) to v.sub.1, . . . , v.sub.n∥v.sub.g1, . . . , v.sub.gn. During verification, in addition to the original verification by using public key P, to verify whether P(v.sub.1, . . . , v.sub.n) is equal to (u.sub.1, . . . , u.sub.n), addition verification which is related to private key is required to determine whether H∘G.sup.−1∘S.sub.Alice (v.sub.1, . . . , v.sub.n) is equal to H∘S.sub.Alice(v.sub.g.sub.1, . . . , v.sub.g.sub.n), and {tilde over (H)}∘T.sub.Alice.sup.−1(u.sub.1, . . . , u.sub.n) is equal to {tilde over (H)}∘Q∘G.sup.−1∘S.sub.Alice(v.sub.g1, . . . , v.sub.gn).

[0109] All three equations must be verified in order to obtain that v.sub.1, . . . , v.sub.n∥v.sub.g1, . . . , v.sub.gn is a correct signature. The scheme can effectively resist the key recovery attack, and has increased security level when compared to the original scheme.

[0110] One skilled in the art will understand that the embodiment of the present invention as shown in the drawings and described above is exemplary only and not intended to be limiting. It will thus be seen that the objects of the present invention have been fully and effectively accomplished. It embodiments have been shown and described for the purposes of illustrating the functional and structural principles of the present invention and is subject to change without departure from such principles. Therefore, this invention includes all modifications encompassed within the spirit and scope of the following claims.