Multivariate Signature Method for Resisting Key Recovery Attack

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 Fn, a m-th extended field of F as Fm, taking a set of multivariable quadratic polynomial equations q1(x1, . . . , xn), . . . , qm(x1, . . . , xn) from Fn to Fm 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−1 for the inverse polynomial of polynomial Q, where Q−1 is held by a legitimate user, taking another reversible affine transformation S and T on Fn and Fm as a secret key and their inverse polynomials are recorded as S−1 and T−1 respectively, then randomly selecting a set of n number n-quaternary multivariable polynomial equations (g1(x1, . . . , xn), . . . , gn(x1, . . . , xn)) on Fn, where its polynomial vector is recorded as G, that is G(x1, . . . , xn)=(g1(x1, . . . , xn), . . . , gn(x1, . . . , xn)), 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−1, the corresponding public key consists of five polynomials, which are:
• P=T∘Q∘S, H∘G−1∘S, H∘S, {tilde over (H)}∘Q∘G−1∘S, {tilde over (H)}∘T−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 (u1, . . . , um) which is recorded as u, a signature is generated by the following steps:
• (2.1) generating a forward signature:
• (2.1a) substituting u=(u1, . . . , um) which is the coding of message M into T−1 by the secret key T−1, obtaining (y1, . . . , ym), which is recorded as y;
• (2.1 b) substituting the obtained result y into the inverse polynomial Q−1 of the center mapping Q, obtaining (x1, . . . , xn), which is recorded as x;
• (2.1c) substituting the obtained result x into the inverse polynomial S−1 of the secret key S, obtaining (v1, . . . , vn), 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(x1, . . . , xn)=(g1(x1, . . . , xn), . . . , gn(x1, . . . , xn))=(g1, . . . , gn), which is recorded as g;
• (2.2b) substituting the obtained result g into the inverse polynomial S−1 of the secret key S, obtaining S−1(g)=S−1∘G(x)=(vg1, . . . , vgn), which is recorded as vg, then vg 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∥vg, 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=(v1, . . . , vn) into the public key P, obtaining P(v1, . . . , vn)=(p1(v1, . . . , vn), . . . , pm(v1, . . . , vn)), obtaining and recording results as u′=(u′1, . . . , u′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−1∘S to process verification:
• (3.2a) substituting the forward signature v=(v1, . . . , vn) into the public key H∘S, obtaining H∘S(v)=H∘S(v1, . . . , vn)=H(S(v1, . . . , vn)), and recording obtained results as h=(h1, . . . , hn);
• (3.2b) substituting the backward signature vg=(vg1, . . . , vgn) into the public key H∘G−1∘S, obtaining H∘G−1∘S(vg)=H∘G−1∘S(vg1, . . . , vgn)=H(G−1(S(vg1, . . . , vgn))), and recording obtained results as h′=(h′1, . . . , h′n);
• (3.2c) determining if h and h′ are equal;
• (3.3) using public key {tilde over (H)}∘Q∘G−1∘S and {tilde over (H)}∘T−1 to process verification:
• (3.3a) for the coding u of the message M, substituting u into the public key {tilde over (H)}∘T−1, obtaining {tilde over (H)}∘T−1(u)={tilde over (H)}(T−1(u)), and recording obtained results as {tilde over (h)}=(h1, . . . , {tilde over (h)}n);
• (3.3b) for the backward signature vg, substituting vg into the public key {tilde over (H)}∘Q∘G−1∘S, obtaining {tilde over (H)}∘Q∘G−1∘S(vg)={tilde over (H)}(Q(G−1(S(vg)))), recording obtained results as {tilde over (h)}′=({tilde over (h)}′1, . . . , {tilde over (h)}′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∥vg is a legitimate signature of the coding u of the message M, otherwise, the signature is invalid and rejected.