CN102006165A - Ring signature method for anonymizing information based on multivariate public key cryptography - Google Patents

Abstract

The invention discloses a ring signature method for anonymizing information based on multivariate public key cryptography, comprising the following steps: generating system parameters, generating a secret key, generating the ring signature and verifying the ring signature. The ring signature method based on the traditional cryptosystem is subjected to security threat under the quantum computer while the ring signature method based on the multivariate public key cryptosystem solves the problem that the existing ring signature systems are insecure under the quantum computation. The method has the advantages of security and high computing efficiency.

Description

Based on the method for multivariable public key cryptography to the anonymous ring signature of message

Technical field

The invention belongs to field of information security technology, relate to a kind of based on the method for multivariable public key cryptography to the anonymous ring signature of message.

Background technology

Calendar year 2001, how under the anonymous background that betrays a secret, people such as Rivest have proposed a kind of novel signature technology, are called ring signature (ring signature).The ring signature can be regarded as a kind of special group's signature, and it does not have trusted party, does not have group's the process of setting up, and the group here is meant the set of being made up of a plurality of possible signers, is also referred to as ring.The foundation of this ring has spontaneity, and promptly ring is not needed to set up under the situation of discussing with other people by a signer.Ring signature to electronic document is signed by all members in the signer representative ring, but signer is anonymous fully for the signature verifier.The ingenious method that the ring signature provides a kind of anonymity to betray the pot to the roses.This unconditional anonymity of ring signature is very useful in some particular surroundingss to the long-term protection of informational needs.The ring signature can be realized unconditional anonymity, promptly can't follow the trail of signer's identity.This unconditional anonymity of ring signature is applicable to some particular surroundingss of the long-term protection of informational needs.The ring signature has caused extensive concern, has proposed various ring signature schemes.2002, people such as Abe proposed first ring signature scheme based on discrete logarithm on the finite field.Recently, bilinearity is encircled signature scheme to being used to design, yet the operation efficiency that bilinearity is right is very low.

The ring signature is because of its distinctive character, as spontaneity, anonymity etc., make it can be widely used in the issue of anonymity of the anonymity leakage of anonymous electronic voting, confidential information, E-Government, ecommerce, highlight and the anonymous authentication in the wireless sensor network.Briefly introduce several application below:

1) is used for anonymous leakage information.The Official corruption that for example reports an offender anonymously, in order to prevent official's reprisal, protection informant's privacy, the informant can encircle signature to the report electronic document.Anti-Corruption Bureau can also not expose informant's true identity in the authenticity that obtains report information.At this moment just can use the ring signature scheme.

2) be used for the anonymous authentication of ad-hoc, wireless sensor network.Characteristics such as the no center of ad-hoc and wireless sensor network, self-organizing and a lot of similarities that are configured with of encircling signature.So for the problems in the ad-hoc network, as: member's anonymous authentications etc., often a side of requirement participation entity can keep the privacy of own identity in application process, can use the ring signature and solve.

Along with the appearance of quantum computer, utilize quantum computer can in polynomial time, solve the factor and decompose and discrete logarithm problem, and then serious threat is to existing fail safe of signing based on the ring of conventional cipher system.Construct new public-key cryptosystem, make it can substitute cryptographic system, resist following extremely urgent based on the attack of quantum computer based on number theory.The multivariable public-key cryptosystem can be resisted the attack of quantum computer, and more effective on calculating than the scheme based on number theory, and therefore, the research of multivariable public key cryptography becomes very active problem in the cryptography development.

The multivariable public-key cryptosystem has experienced the development course in 20 years so far, occurred MIA family, OV family, HFE family, TTM family, MFE family, _lSystems such as IC family.Because the fail safe and the efficient of multivariable public-key cryptosystem are higher, so obtained people's extensive concern recently.

The research that develops into the ring signature of multivariable cryptographic system provides new thinking, because up at present, does not also find the found the solution any advantage of quantum computer to secondary multivariable equation group.

Up to the present, proposed various ring signature schemes, but these schemes all are based on the conventional cipher system, for example RSA etc.In the face of the appearance of quantum computer, the conventional cipher system is on the hazard, and therefore, existing ring signature system will be no longer safe under quantum calculation.

Summary of the invention

The purpose of this invention is to provide a kind of method of the anonymous ring of message being signed, solve existing ring signature system unsafe defective under quantum calculation based on the multivariable public key cryptography.

The technical solution adopted in the present invention is that based on the method for multivariable public key cryptography to the anonymous ring signature of message, this method is implemented according to following steps:

Step 1. generation system parameter

1) k=GF (q) being set is the finite field that is characterized as p, wherein q=p ^l, l is a positive integer;

2) make K Be n the expansion of finite field k, n is a positive integer here, and g (x) is n irreducible function on the finite field k;

3) make that m is the number of equation in the multivariable equation group, n is the number of variable;

4) select H:{0,1} ^*→ k ^mBe the unidirectional irreversible hash function of the anti-collision of cryptography safety, system parameters be (k, q, p, l, m, n, H);

Step 2. key generates

1) supposes in the ring t user arranged, be made as U={u, u ₁..., u _T-1;

2) according to the multivariable public-key cryptosystem, each user u _i(0≤i≤t-1) selection Fi is from k ⁿTo k ^mBut inverse mapping, F _iSatisfy:

A) F _i(x ₁..., x _n)=(f _I1..., f _Im), f wherein _Ij∈ k[x ₁..., x _n], j=1 ..., m;

B) any equation

F _i(x ₁，…，x _n)＝(y′ ₁，…，y′ _m)

All be easy to find the solution;

3) each user u _i(0≤i≤t-1) selects wherein L _1iBe from k ^mTo k ^mA reversible affine transformation of selecting at random,

L _1i(x ₁，…，x _m)＝M _1i·(x ₁，…，x _m) ^T+a _1i，

M wherein _1iBe the invertible matrix of a m * m on the finite field k, a _1iIt is the column vector of m * 1 on the finite field k;

4) each user u _i(0≤i≤t-1) selects L _2iBe from k ⁿTo k ⁿA reversible affine transformation of selecting at random

L _2i(x ₁，…，x _n)＝M _2i·(x ₁，…，x _n) ^T+a _2i，

M wherein _2iBe the invertible matrix of a n * n on the finite field k, a _2iIt is the column vector of n * 1 on the finite field k;

5) each user u _i(0≤i≤t-1) announces its PKI

${\stackrel{\‾}{F}}_i(x_1,...,x_n)=({\stackrel{\‾}{f}}_{i1},...,{\stackrel{\‾}{f}}_{\mathrm{im}})$

Wherein each

All be k[x ₁..., x _n] in multinomial;

6) each user u _i(its private key SK that maintains secrecy of 0≤i≤t-1) _i={ L _1i, F _i, L _2i;

7) public key sets of t user in the ring is designated as

Step 3. ring signature generates

Suppose member u _π(0≤π≤t-1) represents all member U={u in the ring members ₀, u ₁..., u _T-1To message M ∈ 0,1} ^*Sign, the user's of the t in the ring public key sets is designated as

u _πPKI be

Private key is SK _π={ L _{1 π}, F _π, L _{2 π}, signer u _πThe step of ring signature is as follows:

1) for i=0,1 ..., t-1 and i ≠ π, picked at random r _i∈ k ⁿ, calculate

$R_i={\stackrel{\‾}{F}}_i\left(r_i\right),$

If R _iIn have identically, then reselect r _i

2) calculate

h＝H(M||L)；

3) calculate

$R_{\mathrm{\π}}=h-\underset{i\≠\mathrm{\π}}{\mathrm{\Σ}}{R}_i,$

If R _πAnd R _iIdentical, then reselect r;

4) calculate

5) output message M is about ring

Ring signature sigma=(r ₀, r ₁... r _T-1);

The checking of step 4. ring signature

Given ring

The signature sigma about message M=(r ₀, r ₁... r _T-1), any verifier's checking

$\underset{i=0}{\overset{t-1}{\mathrm{\Σ}}}{\stackrel{\‾}{F}}_i\left(r_i\right)=H\left(M\right|\left|L\right)$

Whether set up.If equation is set up, then accept the ring signature, otherwise refuse this ring signature.

Characteristics of the present invention also are,

Wherein in the step 3, signer calculates

Thereby make message M about ring

Ring signature sigma=(r ₀, r ₁... r _T-1) constituted the closed-loop that can verify and satisfy

$\underset{i=0}{\overset{t-1}{\mathrm{\Σ}}}{\stackrel{\‾}{F}}_i\left(r_i\right)=H\left(M\right|\left|L\right).$

Ring endorsement method based on the conventional cipher system, its fail safe is on the hazard under quantum computer, and the ring endorsement method that the present invention is based on the multivariable public-key cryptosystem is safe under quantum calculation, and method of the present invention not only has fail safe but also have the high advantage of computational efficiency.

Embodiment

The technical solution adopted in the present invention is that based on the method for multivariable public key cryptography to the anonymous ring signature of message, this method is implemented according to following steps:

Step 1. generation system parameter

1) k=GF (q) being set is the finite field that is characterized as p, wherein q=p ^l, l is a positive integer;

2) order

Be n the expansion of finite field k, n is a positive integer here, and g (x) is n irreducible function on the finite field k;

3) make that m is the number of equation in the multivariable equation group, n is the number of variable;

4) select H:{0,1} ^*→ k ^mBe the unidirectional irreversible hash function of the anti-collision of cryptography safety, system parameters be (k, q, p, l, m, n, H).

Step 2. key generates

1) supposes in the ring t user arranged, be made as U={u ₀, u ₁..., u _T-1;

2) according to the multivariable public-key cryptosystem, each user u _i(0≤i≤t-1) selects F _iBe from k ⁿTo k ^mBut inverse mapping, F _iSatisfy:

A) F _i(x ₁..., x _n)=(f _I1..., f _Im), f wherein _Ij∈ k[x ₁..., x _n], j=1 ..., m;

B) any equation

F _i(x ₁，…，x _n)＝(y′ ₁，…，y′ _m)

All be easy to find the solution;

3) each user u _i(0≤i≤t-1) selects L at random _1iBe from k ^mTo k ^mA reversible affine transformation,

L _1i(x ₁，…，x _m)＝M _1i·(x ₁，…，x _m) ^T+a _1i，

M wherein _1iBe the invertible matrix of a m * m on the finite field k, a _1iIt is the column vector of m * 1 on the finite field k;

4) each user u _i(0≤i≤t-1) selects L at random _2iBe from k ⁿTo k ⁿA reversible affine transformation

L _2i(x ₁，…，x _n)＝M _2i·(x ₁，…，x _n) ^T+a _2i，

M wherein _2iBe the invertible matrix of a n * n on the finite field k, a _2iIt is the column vector of n * 1 on the finite field k;

5) each user u _i(0≤i≤t-1) announces its PKI

${\stackrel{\‾}{F}}_i(x_1,...,x_n)=({\stackrel{\‾}{f}}_{i1},...,{\stackrel{\‾}{f}}_{\mathrm{im}})$

Wherein each

All be k[x ₁..., x _n] in multinomial;

6) each user u _i(its private key SK that maintains secrecy of 0≤i≤t-1) _i={ L _1i, F _i, L _2i;

7) public key sets of t user in the ring is designated as

Step 3. ring signature generates

Suppose member u _π(0≤π≤t-1) represents all member U={u in the ring members ₀, u ₁..., u _T-1To message M ∈ 0,1} ^*Sign, the user's of the t in the ring public key sets is designated as

u _πPKI be

Private key is SK _π={ L _{1 π}, F _π, L _{2 π}.Signer u _πThe step of ring signature is as follows:

1) for i=0,1 ..., t-1 and i ≠ π, picked at random r _i∈ k ⁿ, calculate

$R_i={\stackrel{\‾}{F}}_i\left(r_i\right),$

If R _iIn have identically, then reselect r _i

2) calculate

h＝H(M||L)；

3) calculate

$R_{\mathrm{\π}}=h-\underset{i\≠\mathrm{\π}}{\mathrm{\Σ}}{R}_i,$

If R _πAnd R _iIdentical, then reselect r;

4) calculate

5) output message M is about ring

Ring signature sigma=(r ₀, r ₁... r _T-1).

The checking of step 4. ring signature

Given ring The signature sigma about message M=(r ₀, r ₁... r _T-1), any verifier's checking

$\underset{i=0}{\overset{t-1}{\mathrm{\Σ}}}{\stackrel{\‾}{F}}_i\left(r_i\right)=H\left(M\right|\left|L\right)$

Whether set up.If equation is set up, then accept the ring signature, otherwise refuse this ring signature.

Respectively correctness, anonymity and unforgeable of signing based on the ring of multivariable public-key cryptosystem of the present invention analyzed below:

Here we are from the correctness of cipher theory proof digital signature method of the present invention.

● correctness

Proposed by the invention is correct based on multivariable ring signature.

If the recipient receives that message M is about ring

Signature sigma=(r ₀, r ₁... r _T-1), if this signature is to be undertaken by as above signature step, and in the process of transmission, do not change, then because

Obtain

${\stackrel{\‾}{F}}_{\mathrm{\π}}\left(r_{\mathrm{\π}}\right)=R_{\mathrm{\π}}$

Again because

$R_{\mathrm{\π}}=h-\underset{i\≠\mathrm{\π}}{\mathrm{\Σ}}{R}_i,$ h＝H(M||L)， $R_i{=\stackrel{\‾}{F}}_i\left(r_i\right),i=\mathrm{0,1},...,t-1,$

So

$\underset{i=0}{\overset{t-1}{\mathrm{\Σ}}}{\stackrel{\‾}{F}}_i\left(r_i\right)=H\left(M\right|\left|L\right)$

Set up, so the checking formula is set up.

● the signer anonymity

Proposed by the invention satisfies the unconditional anonymity of signer based on multivariable ring signature.

If signature sigma=(r ₀, r ₁... r _T-1) be the effective signature of message M, according to the generative process of signature, all u _iBe a member in the ring, u _iBy the process that generates the ring signature message M is encircled signature, according to the generative process of signature, all r _i∈ k ⁿ(i=0,1 ..., π-1, π+1 ..., t-1) all be picked at random, and It also is picked at random.Because h=H (M||U) can be regarded as k ^mOn a random value, therefore

Be k ^mA value of last completely random,

Be k ⁿA value of last completely random.Therefore encircle signature sigma=(r ₀, r ₁... r _T-1) middle r _i∈ k ⁿ(i=0,1 ..., t-1) all be k ⁿA value of last completely random.So σ=(r ₀, r ₁... r _T-1) probability that occurs equates, all be

And it is irrelevant with signer.Even if therefore external attacker has illegally obtained the private key of all possible signer, element is a t element in the ring, and the probability that it can determine real signer is no more than

● the signature unforgeable

The present invention propose based on the ring signature scheme of multivariable polynomial about multivariable public-key cryptosystem (MPKC) known attack can not forge, if in MPKC under the known attack, selected multivariable signature system is safe in the ring signature scheme.Here known attack comprises the algebraically attack among the MPKC, and linearisation is attacked, order attack and differential attack etc.

Proof: suppose that the key that is generated by generating algorithm is right

And public key sets

Send to assailant A.A can utilize known attack among the MPKC, attacks as algebraically, and linearisation is attacked, and order is attacked, differential attack or the like.A exports (R ^*, M ^*, σ ^*), if Vrfy _R*(M ^*, R ^*Set up)=1, success attack.In this process, A can not inquire (*, M ^*, σ ^*), and We analyze the ring signature (R that A output is forged now ^*, M ^*, σ ^*) computation complexity.We suppose assailant A imitation signer u _πForgery is about ring R ^*Ring signature (R ^*, M ^*, σ ^*), not general, suppose

Step 1) during assailant A generates according to the ring signature, 2), 3) calculate, but in order to forge the signature of certain message M, need be by trying to achieve r _π, satisfy

${\stackrel{\‾}{F}}_{\mathrm{\π}}\left(r_{\mathrm{\π}}\right)=R_{\mathrm{\π}}$

Forge ring signature sigma=(r ₀, r ₁... r _T-1).This problem find the solution the problem of finding the solution that belongs to multivariable quadratic polynomial equation group on the finite field, also be the multivariable public-key cryptosystem based on difficult problem.Attack to the multivariable public-key cryptosystem at present has following method:

1) algebraically is attacked: attack at the algebraically of multivariable public-key cryptosystem and be meant and do not knowing under the situation of private key directly from quadratic equation

In find the solution ciphertext r _π

Base algorithm and XL algorithm are the most effective algebraically attack methods.If selected actual multivariable public-key cryptosystem can be resisted direct algebraically attack in this programme, the ring signature among the present invention also can be resisted direct algebraically and attack.

2) lienarized equation is attacked: a lienarized equation is meant given PKI

Always have following equation to set up:

$\underset{i,j}{\mathrm{\Σ}}{a}_{\mathrm{ij}}{r}_{\mathrm{\π},i}{R}_{\mathrm{\π},j}+\underset{i}{\mathrm{\Σ}}{b}_i{r}_{\mathrm{\π},i}+\underset{j}{\mathrm{\Σ}}{c}_j{R}_{\mathrm{\π},j}+d=0$

R _π∈ k ^mOccurrence substitution following formula, we obtain r _πOne affine (linearity) relation.If selected actual multivariable public-key cryptosystem can be resisted and utilize lienarized equation to attack attacking in this programme, the ring signature among the present invention also can be resisted lienarized equation and attack.

3) order is attacked: Goubin and Courtois point out that minimum order is attacked and are applicable to triangle-Jia-subtract system.The complexity that order is attacked is about

Wherein k is F _πMinimum order is the number of the linear combination of r in the component.

If selected actual multivariable public-key cryptosystem can be resisted and utilize minimum order to attack in this programme, then the signature of the ring among the present invention also can be resisted minimum order attack.

4) differential attack: the PKI that provides a multivariable public-key cryptosystem

One group of quadratic polynomial, its difference

Be defined as This is one group of function about x.Key is to utilize the concealed structure in the difference to attack the multivariable public-key cryptosystem.If actual multivariable public-key cryptosystem selected in this programme can be resisted differential attack, then the signature of the ring among the present invention also can be resisted differential attack.

Know by above proof, if our selected multivariable public-key cryptosystem existing be safe under MPKC is attacked, ring signature then of the present invention existing also be safe under MPKC is attacked.

Embodiment

Anonymity ring signature scheme step 1. generation system parameter based on multivariable public key cryptography TTS (20,28) system

1) k=GF (q)=GF (2 is set ⁸) be the finite field that is characterized as p=2;

2) make that m=20 is the number of equation in the multivariable equation group, n=28 is the number of variable;

3) select H:{0,1} ^*→ k ^mBe the unidirectional irreversible hash function of the anti-collision of cryptography safety,

System parameters be (k, q, p, l, m, n, H).

Step 2. key generates

1) supposes in the ring t user arranged, be made as U={u ₀, u ₁..., u _T-1;

2) according to the multivariable public-key cryptosystem, each user u _i(0≤i≤t-1) selection F is from k ⁿTo k ^mBut inverse mapping, F is the mappings of following central authorities

$y_i=x_i+{\mathrm{\Σ}}_{j=1}^7{p}_{i,j}{x}_j{x}_{8+(i+j\mathrm{mod}9)},i=8...16;$

y ₁₇＝x ₁₇+p _17，1x ₁x ₆+p _17，2x ₂x ₅+p _17，3x ₃x ₄+p _17，4x ₉x ₁₆+p _17，5x ₁₀x ₁₅+p _17，6x ₁₁x ₁₄+p _17，7x ₁₂x ₁₃；y ₁₈＝x ₁₈+p _18，1x ₂x ₇+p _18，2x ₃x ₆+p _18，3x ₄x ₅+p _18，4x ₁₀x ₁₇+p _18，5x ₁₁x ₁₆+p _18，6x ₁₂x ₁₅+p _18，7x ₁₃x ₁₄；

$y_i=x_i+p_{i,0}{x}_{i-11}{x}_{i-9}+{\mathrm{\Σ}}_{j=19}^i{p}_{i,j-18}{x}_{2(i-j)}{x}_j+{\mathrm{\Σ}}_{j=i+1}^{27}{p}_{i,j-18}{x}_{i-j+19}{x}_j,i=19...27.$

The F here is called as central authorities' mapping of TTS (20,28);

3) each user u _i(0≤i≤t-1) selects wherein L _1iBe from k ^mTo k ^mA reversible affine transformation of selecting at random,

L _1i(x ₁，…，x _m)＝M _1i·(x ₁，…，x _m) ^T+a _1i，

M wherein _1iBe the invertible matrix of a m * m on the finite field k, a _1iThe column vector of m * 1 on the finite field k;

4) each user u _i(0≤i≤t-1) selects L _2iBe from k ⁿTo k ⁿA reversible affine transformation of selecting at random

L _2i(x ₁，…，x _n)＝M _2i·(x ₁，…，x _n) ^T+a _2i，

M wherein _2iBe the invertible matrix of a n * n on the finite field k, a _2iThe column vector of n * 1 on the finite field k, a _2iChoose feasible

There is not constant component;

5) each user u _i(0≤i≤t-1) announces its PKI

${\stackrel{\‾}{F}}_i(x_1,...,x_n)=({\stackrel{\‾}{f}}_{i1},...,{\stackrel{\‾}{f}}_{\mathrm{im}})$

Wherein each

All be k[x ₁..., x _n] in multinomial;

6) each user u _i(its private key SK that maintains secrecy of 0≤i≤t-1) _i={ L _1i, F _i, L _2i;

7) public key sets of t user in the ring is designated as

Step 3. ring signature generates

If suppose member u _π(0≤π≤t-1) represents all member U={u in the ring members ₀, u ₁..., u _T-1Message M is signed, the user's of the t in the ring public key sets is designated as u _πPKI be

Private key is SK _π={ L _{1 π}, F _π, L _{2 π}.Signer u _πThe step of ring signature is as follows:

1) for i=0,1 ..., t-1 and i ≠ π, picked at random r _i∈ k ⁿ, calculate

$R_i={\stackrel{\‾}{F}}_i\left(r_i\right),$

If R _iIn have identically, then reselect r _i

2) calculate

h＝H(M||L)；

3) calculate

$R_{\mathrm{\π}}=h-\underset{i\≠\mathrm{\π}}{\mathrm{\Σ}}{R}_i,$

If R _πAnd R _iIdentical, then reselect r;

4) calculate

Concrete process is as follows:

At first calculate Calculate a possible x=F then ^-1(y) ∈ k ⁿAs follows:

A) assigned at random x ₁..., x ₇∈ k attempts finding the solution x ₈..., x ₁₆Utilize preceding 9 equations.Because the determinant of this system of linear equations (to x arbitrarily ₂X ₇) be one about x ₁Number of times is 9 multinomial, x ₁There are 9/256ths kinds of selections to make first system degradation at most.Do not separate if having, again assigned at random x ₁..., x ₇∈ k finds x up to us ₈..., x ₁₆One separate;

B) the continuous x that finds the solution ₁₇And x ₁₈, use to meet following two equation (x ₁₇And x ₁₈);

C) assign an x at random ₀, attempt from last 9 equation solution x ₁₉..., x ₂₇Do not separate if having, again selection x at random ₀Separate x up to one ₁₉..., x ₂₇Found;

D) the above-mentioned institute of note tries to achieve and separates (the x into x= ₀, x ₁..., x ₂₇)=F ^-1(y) ∈ k ⁿ, calculate

$r_{\mathrm{\π}}=L_{2\mathrm{\π}}^{-1}x\∈k^n$

5) output message M is about ring

Ring signature sigma=(r ₀, r ₁... r _T-1).

The checking of step 4 ring signature

Given ring

The signature sigma about message M=(r ₀, r ₁... r _T-1), any verifier can the certifying signature correctness, by checking:

$\underset{i=0}{\overset{t-1}{\mathrm{\Σ}}}{\stackrel{\‾}{F}}_i\left(r_i\right)=H\left(M\right|\left|L\right)$

Whether set up.If equation is set up, then accept the ring signature, otherwise refuse this ring signature.

Method of the present invention provides the number of rings word signature of electronic document, can be used for protecting the integrality of electronic document in issue, storage or transmission, the safeguard protection of authenticity; Simultaneously; can protect the anonymity of signer again; do not expose with the information that guarantees the signature user; under the situation of this signature by checking; make certain member's signature in the ring that the verifier of signature can be sure of that this signature is made up of a plurality of users; but the verifier can not confirm this signature on earth by which member's signature, and the probability of each member's signature equates.

The present invention is directed to the appearance of quantum computer, the conventional cipher system is on the hazard, and utilizes the advantage based on multivariable public key cryptography safety under quantum calculation, and solving existing ring signature system will no longer safe defective under quantum calculation.The ring signature scheme based on the multivariable public-key cryptosystem of invention satisfies the unconditional anonymity and the unforgeable of signer, is better than the conventional cipher system on efficient.

Claims (2)

1. based on the method for multivariable public key cryptography, it is characterized in that this method is implemented according to following steps to the anonymous ring signature of message:

Step 1. generation system parameter

1) k=GF (q) being set is the finite field that is characterized as p, wherein q=p ^l, l is a positive integer;

2) order

Be n the expansion of finite field k, n is a positive integer here, and g (x) is n irreducible function on the finite field k;

3) make that m is the number of equation in the multivariable equation group, n is the number of variable;

4) select H:{0,1} ^*→ k ^mBe the unidirectional irreversible hash function of the anti-collision of cryptography safety, system parameters be (k, q, p, l, m, n, H);

Step 2. key generates

1) supposes in the ring t user arranged, be made as U={u ₀, u ₁..., u _T-1;

2) according to the multivariable public-key cryptosystem, each user u _i(0≤i≤t-1) selects F _iBe from k ⁿTo k ^mBut inverse mapping, F _iSatisfy:

A) F _i(x ₁..., x _n)=(f _I1..., f _Im), f wherein _Ij∈ k[x ₁..., x _n], j=1 ..., m;

B) any equation

F _i(x ₁，…，x _n)＝(y′ ₁，…，y′ _m)

All be easy to find the solution;

3) each user u _i(0≤i≤t-1) selects wherein L _1iBe from k ^mTo k ^mA reversible affine transformation of selecting at random,

L _1i(x ₁，…，x _m)＝M _1i·(x ₁，…，x _m) ^T+a _1i，

M wherein _1iBe the invertible matrix of a m * m on the finite field k, a _1iIt is the column vector of m * 1 on the finite field k;

4) each user u _i(0≤i≤t-1) selects L _2iBe from k ⁿTo k ⁿA reversible affine transformation of selecting at random

L _2i(x ₁，…，x _n)＝M _2i·(x ₁，…，x _n) ^T+a _2i，

M wherein _2iBe the invertible matrix of a n * n on the finite field k, a _2iIt is the column vector of n * 1 on the finite field k;

5) each user u _i(0≤i≤t-1) announces its PKI

${\stackrel{\‾}{F}}_i(x_1,...,x_n)=({\stackrel{\‾}{f}}_{i1},...,{\stackrel{\‾}{f}}_{\mathrm{im}})$

Wherein each

All be k[x ₁..., x _n] in multinomial;

6) each user u _i(its private key SK that maintains secrecy of 0≤i≤t-1) _i={ L _1i, F _i, L _2i;

7) public key sets of t user in the ring is designated as

Step 3. ring signature generates

Suppose member u _π(0≤π≤t-1) represents all member U={u in the ring members ₀, u ₁..., u _T-1To message M ∈ 0,1} ^*Sign, the user's of the t in the ring public key sets is designated as

The PKI of u π is

Private key is SK _π={ L _{1 π}, F _π, L _{2 π}, signer u _πThe step of ring signature is as follows:

1) for i=0,1 ..., t-1 and i ≠ π, picked at random r _i∈ k ⁿ, calculate

$R_i={\stackrel{\‾}{F}}_i\left(r_i\right),$

If R _iIn have identically, then reselect r _i

2) calculate

h＝H(M||L)；

3) calculate

$R_{\mathrm{\π}}=h-\underset{i\≠\mathrm{\π}}{\mathrm{\Σ}}{R}_i,$

If R _πAnd R _iIdentical, then reselect r;

4) calculate

5) output message M is about ring

Ring signature sigma=(r ₀, r ₁... r _T-1);

The checking of step 4. ring signature

Given ring The signature sigma about message M=(r ₀, r ₁... r _T-1), any verifier's checking

$\underset{i=0}{\overset{t-1}{\mathrm{\Σ}}}{\stackrel{\‾}{F}}_i\left(r_i\right)=H\left(M\right|\left|L\right)$

Whether set up,, then accept the ring signature, otherwise refuse this ring signature if equation is set up.

2. method according to claim 1 is characterized in that, in this method step 3, signer calculates

Thereby make message M about ring

Ring signature sigma=(r ₀, r ₁... r _T-1) constituted the closed-loop that can verify and satisfy

$\underset{i=0}{\overset{t-1}{\mathrm{\Σ}}}{\stackrel{\‾}{F}}_i\left(r_i\right)=H\left(M\right|\left|L\right).$