CN102006167B

CN102006167B - Ring signature method for anonymizing information based on algebra

Info

Publication number: CN102006167B
Application number: CN 201010544635
Authority: CN
Inventors: 王尚平; 马瑞
Original assignee: Xian University of Technology
Current assignee: Xian University of Technology
Priority date: 2010-11-11
Filing date: 2010-11-11
Publication date: 2013-03-13
Anticipated expiration: 2030-11-11
Also published as: CN102006167A

Abstract

本发明公开了一种基于代数的对消息匿名环签名的方法，该方法按照以下步骤实施，生成系统参数，密钥生成，环签名生成，环签名的验证。基于传统密码体制的环签名方法，在量子计算机下其安全性受到威胁，而本发明基于多变量公钥密码体制的环签名方法解决了现有的环签名体制在量子计算下不安全的缺陷。本发明的方法既具有安全性又具有计算效率高的优点。The invention discloses an algebra-based method for signing anonymous rings of messages. The method is implemented according to the following steps: generating system parameters, generating keys, generating ring signatures, and verifying ring signatures. The security of the ring signature method based on the traditional cryptographic system is threatened under the quantum computer, but the ring signature method based on the multivariable public key cryptosystem of the present invention solves the defect that the existing ring signature system is not safe under the quantum computing. The method of the invention has the advantages of both safety and high calculation efficiency.

Description

Algebra-Based Method for Signing Anonymous Rings of Messages

技术领域 technical field

本发明属于信息安全技术领域，涉及一种基于代数的对消息匿名环签名的方法。The invention belongs to the technical field of information security, and relates to an algebra-based method for signing a message anonymous ring.

背景技术 Background technique

2001年，在如何匿名泄漏秘密的背景下，Rivest等人提出了一种新型签名技术，称为环签名(ring signature)。环签名可以被视为一种特殊的群签名，它没有可信中心，没有群的建立过程，这里的群是指由多个可能的签名者组成的集合，也称为环。该环的建立具有自发性，即环是由一个签名者在不需要和其它人商量的情况下建立的。对电子文档的环签名是由一个签名者代表环中全体成员签署的，但对于签名验证者来说签名者是完全匿名的。环签名提供了一种匿名泄露秘密的巧妙方法。环签名的这种无条件匿名性在对信息需要长期保护的一些特殊环境中非常有用。环签名可以实现无条件匿名，即无法追踪签名人的身份。环签名的这种无条件匿名性适用于信息需要长期保护的一些特殊环境。环签名引起了广泛关注，提出了各种环签名方案。2002年，Abe等人提出了第一个基于有限域上离散对数的环签名方案。最近，双线性对被用来设计环签名方案，然而，双线性对的运算效率很低。In 2001, under the background of how to disclose secrets anonymously, Rivest et al. proposed a new type of signature technology called ring signature. Ring signature can be regarded as a special group signature, which has no trusted center and no group establishment process. The group here refers to the set composed of multiple possible signers, also known as the ring. The establishment of the ring is spontaneous, that is, the ring is established by a signer without consulting with others. A ring signature on an electronic document is signed by a signer on behalf of all members of the ring, but the signer is completely anonymous to the signature verifier. Ring signatures provide a neat way to reveal secrets anonymously. The unconditional anonymity of ring signatures is very useful in some special environments where long-term protection of information is required. Ring signatures can achieve unconditional anonymity, that is, the identity of the signer cannot be traced. The unconditional anonymity of ring signatures is suitable for some special environments where information needs to be protected for a long time. Ring signatures have attracted widespread attention, and various ring signature schemes have been proposed. In 2002, Abe et al. proposed the first ring signature scheme based on discrete logarithms over finite fields. Recently, bilinear pairings have been used to design ring signature schemes, however, bilinear pairings are computationally inefficient.

环签名因其特有的性质，如自发性、匿名性等，使得它可以广泛地应用在匿名电子选举、机密信息的匿名泄漏、电子政务、电子商务、重要新闻的匿名发布及无线传感器网络中的匿名认证。下面简要介绍几种应用：Because of its unique properties, such as spontaneity and anonymity, ring signatures can be widely used in anonymous electronic elections, anonymous disclosure of confidential information, e-government, e-commerce, anonymous release of important news, and wireless sensor networks. Anonymous authentication. A few applications are briefly described below:

1)用于匿名泄漏信息。例如匿名举报一个官员腐败，为了防止官员的报复行为，保护举报者的隐私，举报者可以对举报电子文档进行环签名。反贪局在获得举报信息的真实性的同时还能不暴露举报者的真实身份。这时就可以使用环签名方案。1) Used to disclose information anonymously. For example, to anonymously report an official’s corruption, in order to prevent the official’s retaliation and protect the privacy of the whistleblower, the whistleblower can ring-sign the electronic file of the report. While obtaining the authenticity of the reported information, the Anti-Corruption Bureau can also not reveal the true identity of the whistleblower. At this time, the ring signature scheme can be used.

2)用于ad-hoc、无线传感器网络中的匿名认证。ad-hoc和无线传感器网络的无中心、自组织等特点与环签名的构造有很多相似之处。因此对于ad-hoc网络中的诸多问题，如：成员的匿名认证等，往往要求参与实体的一方在应用过程中能够保持自己身份的隐私性，都可以应用环签名来解决。2) It is used for anonymous authentication in ad-hoc and wireless sensor networks. There are many similarities between ad-hoc and wireless sensor networks, such as centerlessness and self-organization, and the construction of ring signatures. Therefore, for many problems in the ad-hoc network, such as anonymous authentication of members, etc., it is often required that the party participating in the application process can maintain the privacy of its own identity, and ring signatures can be used to solve them.

随着量子计算机的出现，利用量子计算机可以在多项式时间内解决因子分解和离散对数问题，进而严重威胁到现有基于传统密码体制的环签名的安全性。构造新的公钥密码体制，使其能够替代基于数论的密码体制，抵御未来基于量子计算机的攻击已经迫在眉睫。多变量公钥密码体制可以抵御量子计算机的攻击，而且比基于数论的方案在计算上更有效，因此，多变量公钥密码学的研究成为密码学发展中很活跃的课题。With the emergence of quantum computers, the use of quantum computers can solve factorization and discrete logarithm problems in polynomial time, which seriously threatens the security of existing ring signatures based on traditional cryptosystems. It is imminent to construct a new public key cryptosystem so that it can replace the cryptosystem based on number theory and resist future attacks based on quantum computers. Multivariate public-key cryptography can resist the attack of quantum computers and is more computationally efficient than schemes based on number theory. Therefore, the research on multivariate public-key cryptography has become a very active topic in the development of cryptography.

多变量公钥密码体制至今已经经历了20年的发展历程，出现了MIA族、OV族、HFE族、TTM族、MFE族、lIC族等体制。由于多变量公钥密码体制的安全性和效率更高，所以最近得到了人们的广泛关注。Multivariate public key cryptosystems have gone through 20 years of development, and MIA family, OV family, HFE family, TTM family, MFE family, IIC family and other systems have emerged. Because of its higher security and efficiency, multivariate public-key cryptosystems have recently received widespread attention.

多变量密码体制的发展为环签名的研究提供了新的思路，因为直到目前，还没有发现量子计算机对二次多变量方程组的求解有任何优势。The development of multivariate cryptosystems provides new ideas for the research of ring signatures, because until now, no quantum computer has been found to have any advantages in solving quadratic multivariate equations.

到目前为止，已经提出了各种环签名方案，但这些方案都是基于传统密码体制，例如RSA等。面对量子计算机的出现，传统密码体制受到威胁，因此，现有的环签名体制在量子计算下将不再安全。So far, various ring signature schemes have been proposed, but these schemes are all based on traditional cryptosystems, such as RSA and so on. Facing the emergence of quantum computers, the traditional cryptographic system is threatened. Therefore, the existing ring signature system will no longer be safe under quantum computing.

发明内容 Contents of the invention

本发明的目的是提供一种基于代数的对消息匿名环签名的方法，解决现有的环签名体制在量子计算下不安全的缺陷。The purpose of the present invention is to provide an algebra-based method for signing anonymous rings of messages, which solves the defect that the existing ring signature system is insecure under quantum computing.

本发明所采用的技术方案是，基于代数的对消息匿名环签名的方法，该方法按照以下步骤实施：The technical solution adopted in the present invention is an algebra-based method for signing an anonymous ring of messages, which is implemented according to the following steps:

步骤1.生成系统参数Step 1. Generate System Parameters

1)设置k＝GF(q)是有限域，其中q＝p^l，p是一个素数，l是一个正整数；1) Setting k=GF(q) is a finite field, where q=p ^l , p is a prime number, and l is a positive integer;

2)令m为多变量方程组中方程的个数，n为变量的个数；2) Let m be the number of equations in the multivariate equation system, and n be the number of variables;

3)选择H：{0，1}^*→kⁿ为密码学安全的哈希函数，3) Select H: {0, 1} ^* →k ⁿ is a cryptographically secure hash function,

系统参数为(k，q，p，l，n，m，H)；The system parameters are (k, q, p, l, n, m, H);

步骤2.密钥生成Step 2. Key generation

1)假设环中有t个用户，设为U＝{u₀，u₁，…，u_t-1}；1) Suppose there are t users in the ring, set U={u ₀ , u ₁ ,...,u _t-1 };

2)选择一个安全的多变量公钥密码签名体制，根据该体制，每个用户u_i(0≤i≤t-1)选择F_i是从kⁿ到k^m的可逆映射，F_i满足：2) Choose a secure multi-variable public key cryptographic signature system. According to this system, each user u _i (0≤i≤t-1) chooses F _i as a reversible mapping from k ⁿ to k ^m , and F _i satisfies:

a)F_i(x₁，…，x_n)＝(f_i1，…，f_im)，其中f_ij∈k[x₁，…，x_n]，j＝1，…，m；a) F _i (x ₁ ,...,x _n )=(f _i1 ,...,f _im ), where f _ij ∈ k[x ₁ ,...,x _n ], j=1,...,m;

b)任何方程b) any equation

F_i(x₁，…，x_n)＝(y′₁，…，y′_m)F _i (x ₁ ,...,x _n )=(y' ₁ ,...,y' _m )

都易于求解；are easy to solve;

3)每个用户u_i(0≤i≤t-1)随机选择L_1i是从k^m到k^m的一个可逆仿射变换3) Each user u _i (0≤i≤t-1) randomly selects L _1i is an invertible affine transformation from k ^m to k ^m

L_1i(x₁，…，x_m)＝M_1i·(x₁，…，x_m)^T+a_1i，L _1i (x ₁ ,...,x _m )=M _1i ·(x ₁ ,...,x _m ) ^T +a _1i ,

其中M_1i是有限域k上的一个m×m的可逆矩阵，a_1i是有限域k上的一个m×1的列向量；Where M _1i is an m×m invertible matrix on finite field k, and a _1i is an m×1 column vector on finite field k;

4)每个用户u_i(0≤i≤t-1)随机选择L_2i是从kⁿ到kⁿ的一个可逆仿射变换4) Each user u _i (0≤i≤t-1) randomly selects L _2i is a reversible affine transformation from k ⁿ to k ⁿ

L_2i(x₁，…，x_n)＝M_2i·(x₁，…，x_n)^T+a_2i，L _2i (x ₁ ,...,x _n )=M _2i ·(x ₁ ,...,x _n ) ^T +a _2i ,

其中M_2i是有限域k上的一个n×n的可逆矩阵，a_2i是有限域k上的一个n×1的列向量；Where M _2i is an n×n invertible matrix on finite field k, and a _2i is an n×1 column vector on finite field k;

5)每个用户u_i(0≤i≤t-1)公布其公钥

5) Each user u _i (0≤i≤t-1) publishes its public key

${\overset{&OverBar; &OverBar;}{F f}}_{i i} (({x x}_{11},, \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot,, {x x}_{n no})) = = (({\overset{&OverBar; &OverBar;}{f f}}_{i i 11},, \cdot \cdot \cdot \cdot \cdot &Center Dot;,, {\overset{&OverBar; &OverBar;}{f f}}_{im im}))$

其中每一个

都是k[x₁，…，x_n]中的多项式；each of them

are all polynomials in k[x ₁ ,...,x _n ];

6)每个用户u_i(0≤i≤t-1)保密其私钥SK_i＝{L_1i，F_i，L_2i}；6) Each user u _i (0≤i≤t-1) keeps its private key SK _i ={L _1i , F _i , L _2i } secret;

7)环中的t个用户的公钥集记为

7) The public key sets of t users in the ring are denoted as

步骤3.环签名生成Step 3. Ring signature generation

设签名者u_π(0≤π≤t-1)代表环中所有成员U＝{u₀，u₁，…，u_t-1}对消息M∈{0，1}^*进行环签名，环中的t个用户的公钥集记为利用其私钥SK_i＝{L_1i，F_i，L_2i}，签名步骤如下：Let the signer u _π (0≤π≤t-1) represent all members in the ring U={u ₀ , u ₁ ,...,u _t-1 } to sign the message M∈{0, 1} ^* , the ring The public key set of t users in is denoted as Using its private key SK _i ={L _1i , F _i , L _2i }, the signature steps are as follows:

1)签名者u_π随机选取u∈kⁿ，计算1) The signer u _π randomly selects u∈k ⁿ , and calculates

${c c}_{π π + + 11 ((mod mod t t))} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{π π} ((u u))));;$

2)对于i＝π+1，π+2，…，t-1，0，1，…，π-1，依次随机选取s_i∈kⁿ，计算2) For i=π+1, π+2, ..., t-1, 0, 1, ..., π-1, randomly select s _i ∈ k ⁿ sequentially, and calculate

${c c}_{i i + + 11 ((mod mod t t))} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{i i} (({c c}_{i i})) + + {\overset{&OverBar; &OverBar;}{F f}}_{i i} (({s the s}_{i i}))));;$

3)计算3) calculate

4)输出消息M关于环

的环签名为4) Output message M about the ring

The ring signature of is

σ＝(c₀，s₀，s₁，…，s_t-1)；σ=(c ₀ , s ₀ , s ₁ ,..., s _t-1 );

步骤4.环签名的验证Step 4. Verification of the ring signature

给定消息M关于环

的环签名σ＝(c₀，s₀，s₁，…，s_t-1)，任何验证者对该签名正确性的验证如下：Given a message M about the ring

The ring signature σ=(c ₀ , s ₀ , s ₁ ,…, _st-1 ), any verifier can verify the correctness of the signature as follows:

1)对于i＝0，1，…，t-1，计算1) For i=0,1,...,t-1, calculate

${c c}_{i i + + 11} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{i i} (({c c}_{i i})) + + {\overset{&OverBar; &OverBar;}{F f}}_{i i} (({s the s}_{i i}))));;$

2)验证c_t＝c₀是否成立，2) Verify whether c _t =c ₀ holds true,

如果成立，则接受该环签名，否则，拒绝该环签名。If true, the ring signature is accepted, otherwise, the ring signature is rejected.

本发明的特点还在于，The present invention is also characterized in that,

其中步骤3中，签名者u_π随机选取u∈kⁿ，计算

In step 3, the signer u _π randomly selects u∈k ⁿ , and calculates

其中步骤3中，对于i＝π+1，π+2，…，t-1，0，1，…，π-1，依次随机选取s_i∈kⁿ，计算In step 3, for i=π+1, π+2, ..., t-1, 0, 1, ..., π-1, randomly select s _i ∈ k ⁿ sequentially, and calculate

${c c}_{i i + + 11 ((mod mod t t))} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{i i} (({c c}_{i i})) + + {\overset{&OverBar; &OverBar;}{F f}}_{i i} (({s the s}_{i i})))) . .$

其中步骤3中，计算Among them, in step 3, the calculation

从而使得消息M关于环

的环签名σ＝(c₀，s₀，s₁，…，s_t-1)构成了一个可以验证的封闭环。so that the message M about the ring

The ring signature σ=(c ₀ , s ₀ , s ₁ ,..., _st-1 ) constitutes a verifiable closed ring.

基于传统密码体制的环签名方法，在量子计算机下其安全性受到威胁，而本发明基于代数的对消息匿名环签名的方法在量子计算下是安全的，本发明的方法既具有安全性又具有计算效率高的优点。The security of the ring signature method based on the traditional cryptographic system is threatened under the quantum computer, and the method of the present invention based on the algebraic anonymous ring signature of the message is safe under the quantum calculation, and the method of the present invention has both security and The advantages of high computational efficiency.

具体实施方式 Detailed ways

本发明所采用的技术方案是，基于代数的对消息匿名环签名的方法，该方法按照以下步骤实施：The technical scheme adopted in the present invention is an algebra-based method for signing the anonymous ring of messages, which is implemented according to the following steps:

步骤1.生成系统参数Step 1. Generate System Parameters

系统参数为(k，q，p，l，n，m，H)。The system parameters are (k, q, p, l, n, m, H).

步骤2.密钥生成Step 2. Key Generation

b)任何方程b) any equation

都易于求解；are easy to solve;

5)每个用户u_i(0≤i≤t-1)公布其公钥

5) Each user u _i (0≤i≤t-1) publishes its public key

${\overset{&OverBar; &OverBar;}{F f}}_{i i} (({x x}_{11},, \cdot \cdot \cdot \cdot \cdot \cdot,, {x x}_{n no})) = = (({\overset{&OverBar; &OverBar;}{f f}}_{i i 11},, \cdot \cdot \cdot \cdot \cdot \cdot,, {\overset{&OverBar; &OverBar;}{f f}}_{im im}))$

其中每一个

都是k[x₁，…，x_n]中的多项式；each of them

are all polynomials in k[x ₁ ,...,x _n ];

7)环中的t个用户的公钥集记为

7) The public key sets of t users in the ring are denoted as

步骤3.环签名生成Step 3. Ring signature generation

设签名者u_π(0≤π≤t-1)代表环中所有成员U＝{u₀，u₁，…，u_t-1}对消息M∈{0，1}^*进行环签名，环中的t个用户的公钥集记为

利用其私钥SK_i＝{L_1i，F_i，L_2i}，签名步骤如下：Let the signer u _π (0≤π≤t-1) represent all members in the ring U={u ₀ , u ₁ ,...,u _t-1 } to sign the message M∈{0, 1} ^* , the ring The public key set of t users in is denoted as

Using its private key SK _i ={L _1i , F _i , L _2i }, the signature steps are as follows:

3)计算3) calculate

4)输出消息M关于环

的环签名为4) Output message M about the ring

The ring signature of is

σ＝(c₀，s₀，s₁，…，s_t-1)。σ=(c ₀ , s ₀ , s ₁ , . . . , _st-1 ).

步骤4.环签名的验证Step 4. Verification of the ring signature

给定消息M关于环

1)对于i＝0，1，…，t-1，计算1) For i=0, 1, ..., t-1, calculate

2)验证c_t＝c₀是否成立。2) Verify whether c _t =c ₀ holds true.

下面分别对本发明的基于多变量公钥密码体制的环签名的正确性、匿名性和不可伪造性进行分析：The correctness, anonymity and unforgeability of the ring signature based on the multivariable public key cryptosystem of the present invention are analyzed respectively below:

●正确性●Correctness

本发明提出的基于多变量多项式的环签名是正确的。The multivariate polynomial-based ring signature proposed by the present invention is correct.

接收方收到消息M关于环

的签名σ＝(c₀，s₀，s₁，…，s_t-1)，若该签名是按照上述步骤生成，并且在传输过程中没有改变，则有c_t＝c₀成立。The receiver receives a message M about the ring

The signature σ=(c ₀ , s ₀ , s ₁ ,..., _st-1 ), if the signature is generated according to the above steps and has not changed during transmission, then c _t =c ₀ holds.

证明：接收方收到消息M关于环

的签名σ＝(c₀，s₀，s₁，…，s_t-1)，若该签名是由步骤3中的环签名生成算法产生的，并且在传输过程中没有改变，则有：Proof: The receiver receives the message M about the ring

The signature σ=(c ₀ , s ₀ , s ₁ ,..., _st-1 ), if the signature is generated by the ring signature generation algorithm in step 3 and has not changed during transmission, then:

${c c}_{π π + + 11 ((mod mod t t))} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{π π} ((u u))))$

${c c}_{π π + + 22 ((mod mod t t))} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{π π + + 11 ((mod mod t t))} (({c c}_{π π + + 11 ((mod mod t t))})) + + {\overset{&OverBar; &OverBar;}{F f}}_{π π + + 11 ((mod mod t t))} (({s the s}_{π π + + 11 ((mod mod t t))}))))$

${c c}_{00} = = {c c}_{t t} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{t t - - 11} (({c c}_{t t - - 11})) + + {\overset{&OverBar; &OverBar;}{F f}}_{t t - - 11} (({s the s}_{t t - - 11}))))$

${c c}_{11} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{00} (({c c}_{00})) + + {\overset{&OverBar; &OverBar;}{F f}}_{00} (({s the s}_{00}))))$

${c c}_{π π} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{π π - - 11} (({c c}_{π π - - 11})) + + {\overset{&OverBar; &OverBar;}{F f}}_{π π - - 11} (({s the s}_{π π - - 11}))))$

因为

根据签名验证过程，我们有because

According to the signature verification process, we have

${c c}_{π π + + 11 ((mod mod t t))} = = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{π π} (({c c}_{π π})) + + {\overset{&OverBar; &OverBar;}{F f}}_{π π} (({s the s}_{π π}))))$

$= = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{π π} (({c c}_{π π})) + + {\overset{&OverBar; &OverBar;}{F f}}_{π π} ((u u)) - - {\overset{&OverBar; &OverBar;}{F f}}_{π π} (({c c}_{π π}))))$

$= = H h ((L L | | | | M m | | | | {\overset{&OverBar; &OverBar;}{F f}}_{π π} ((u u)))),,$

由此，依据签名验证过程所求的{c_i}(i＝0，1，…，t-1)序列与签名生成过程所得结果一致，所以c_t＝c₀成立。Therefore, the sequence of {c _i } (i=0, 1, . . . , t-1) obtained in the signature verification process is consistent with the result obtained in the signature generation process, so c _t =c ₀ is established.

●签名者匿名性● Signer anonymity

本发明提出的基于多变量多项式的环签名满足签名人无条件匿名性。The multivariable polynomial-based ring signature proposed by the present invention satisfies the unconditional anonymity of the signer.

证明：设攻击者得到消息M关于环

的签名为σ＝(c₀，s₀，s₁，…，s_t-1)，由于s_i∈kⁿ是随机选取的，随机选取s_i的概率是1/qⁿ；

而u是随机选取的，随机选取u的概率也是1/qⁿ，因而s_π也可看作是随机的，并且随机选取的概率是1/qⁿ。因此环签名σ＝(c₀，s₀，s₁，…，s_t-1)中s_i(i∈0，1，…，t-1)的值被签名生成算法以相等的概率1/qⁿ进行选择，且与签名者无关。因此即便是外部攻击者非法获得了所有可能的签名者的私钥，它能确定出真正的签名者的概率不超过1/t。Proof: Let the attacker get the message M about the ring

The signature of σ=(c ₀ , s ₀ , s ₁ ,..., s _t-1 ), since s _i ∈ k ⁿ is randomly selected, the probability of randomly selecting s _i is 1/q ⁿ ;

And u is randomly selected, and the probability of randomly selecting u is also 1/q ⁿ , so s _π can also be regarded as random, and the probability of randomly selecting is 1/q ⁿ . Therefore, the value of s _i (i∈0, ₁ , …, _t-1 ) in the ring signature σ=(c ₀ , s ₀ , s 1 ,…, st-1) is generated by the signature generation algorithm with equal probability 1/ q ⁿ makes the choice, independent of the signer. Therefore, even if an external attacker illegally obtains the private keys of all possible signers, the probability that it can determine the real signer does not exceed 1/t.

●签名不可伪造性●Signature unforgeability

本发明提出的基于多变量多项式的环签名方案关于多变量公钥密码体制(MPKC)已知攻击是不可伪造的，如果在MPKC中已知攻击下，环签名方案中所选的多变量签名体制是安全的。这里MPKC中已知攻击包括代数攻击，线性化攻击，秩攻击和差分攻击等。The multivariable polynomial-based ring signature scheme proposed by the present invention is unforgeable with respect to known attacks on the multivariate public key cryptosystem (MPKC). is safe. The known attacks in MPKC include algebraic attacks, linearization attacks, rank attacks and differential attacks.

证明：假设由生成算法生成的密钥对

和公钥集发送给攻击者A。A可以利用MPKC中已知攻击，如代数攻击，线性化攻击，秩攻击，差分攻击等等。A输出(R^*，M^*，σ^*)，如果

成立，攻击成功。在这个过程中，A不能询问(*，M^*，σ^*)，并且

我们现在分析A输出伪造的环签名(R^*，M^*，σ^*)的计算复杂度。我们假设攻击者A模仿签名者u_π伪造关于环R^*的环签名(R^*，M^*，σ^*)，不是一般性，假设

攻击者A按照环签名生成中步骤1)，2)进行计算，但是为了伪造某个消息M的签名，需要通过求得s_π，满足Proof: Assume the key pair generated by the generation algorithm

and public key set sent to attacker A. A can use known attacks in MPKC, such as algebraic attack, linearization attack, rank attack, differential attack and so on. A outputs (R ^* , M ^* , σ ^* ), if

Established, the attack was successful. During this process, A cannot ask (*, M ^* , σ ^* ), and

We now analyze the computational complexity of A outputting the forged ring signature (R ^* , M ^* , σ ^* ). We assume that the attacker A imitates the signer u _π to forge the ring signature (R ^* ^, M ^* , σ ^* ) on the ring R*, not general, assuming

Attacker A calculates according to steps 1) and 2) in ring signature generation, but in order to forge the signature of a message M, it needs to obtain s _π to satisfy

${\overset{&OverBar; &OverBar;}{F f}}_{π π} (({s the s}_{π π})) = = (({\overset{&OverBar; &OverBar;}{F f}}_{π π} ((u u)) - - {\overset{&OverBar; &OverBar;}{F f}}_{π π} (({c c}_{π π}))))$

来伪造环签名σ＝(c₁，s₁，s₂，…，s_t)，其中u为攻击者自己选取的。这个问题的求解属于有限域上多变量二次多项式方程组的求解问题，也是多变量公钥密码体制所基于的困难问题。目前对多变量公钥密码体制的攻击有以下几个方法：To forge the ring signature σ=(c ₁ , s ₁ , s ₂ ,..., st _t ), where u is chosen by the attacker himself. The solution of this problem belongs to the problem of solving multivariable quadratic polynomial equations over finite fields, and it is also a difficult problem on which multivariable public key cryptosystems are based. At present, there are several ways to attack the multivariate public key cryptosystem:

1)代数攻击：针对多变量公钥密码体制的代数攻击是指在不知道私钥的情况下直接从二次方程中求解密文s_π。基算法和XL算法是最有效的代数攻击方法。假如本方案中所选取的实际多变量公钥密码体制可以抵抗直接代数攻击，本发明中的环签名也可以抵抗直接代数攻击。1) Algebraic attack: The algebraic attack on the multivariate public key cryptosystem refers to directly from the quadratic equation without knowing the private key Find the decrypted text s _π in . Base algorithm and XL algorithm are the most effective algebraic attack methods. If the actual multivariable public key cryptosystem selected in this scheme can resist direct algebraic attack, the ring signature in the present invention can also resist direct algebraic attack.

2)线性化方程攻击：一个线性化方程是指对给定的公钥

总有下面的等式成立：2) Linearized equation attack: A linearized equation means that for a given public key

The following equation always holds:

$\underset{i i,, j j}{Σ Σ} {a a}_{ij ij} {s the s}_{π π,, i i} {v v}_{π π,, j j} + + \underset{i i}{Σ Σ} {b b}_{i i} {s the s}_{π π,, i i} + + \underset{j j}{Σ Σ} {c c}_{j j} {v v}_{π π,, j j} + + d d = = 00$

把

的具体值代入上式，我们得到s_π和v_π的一个仿射(线性)关系。假如本方案中所选取的实际多变量公钥密码体制可以抵抗利用线性化方程攻击对进行攻击，本发明中的环签名也可以抵抗线性化方程攻击。Bundle

The specific value of is substituted into the above formula, and we get an affine (linear) relationship between s _π and v _π . If the actual multi-variable public key cryptosystem selected in this scheme can resist the attack by using the linearization equation attack, the ring signature in the present invention can also resist the linearization equation attack.

3)秩攻击：Goubin和Courtois指出最小秩攻击适用于三角-加-减体制。秩攻击的复杂度大约

其中k是F_π分量中最小秩为r的线性组合的数目。3) Rank attack: Goubin and Courtois pointed out that the minimum rank attack is applicable to the triangle-addition-subtraction scheme. The complexity of the rank attack is about

where k is the number of linear combinations of minimum rank r in the components of F _π .

假如本方案中所选取的实际多变量公钥密码体制可以抵抗利用最小秩攻击，则本发明中的环签名也可以抵抗最小秩攻击。If the actual multivariate public key cryptosystem selected in this scheme can resist the minimum rank attack, then the ring signature in the present invention can also resist the minimum rank attack.

4)差分攻击：给出一个多变量公钥密码体制的公钥

一组二次多项式，它的差分

定义为

这是一组关于x的函数。关键是利用差分中的隐藏结构来攻击多变量公钥密码体制。假如本方案中所选取的实际多变量公钥密码体制可以抵抗差分攻击，则本发明中的环签名也可以抵抗差分攻击。4) Differential attack: given the public key of a multivariate public key cryptosystem

A set of quadratic polynomials whose difference

defined as

This is a set of functions on x. The key is to exploit the hidden structure in the difference to attack the multivariate public key cryptosystem. If the actual multi-variable public key cryptosystem selected in this scheme can resist differential attack, then the ring signature in the present invention can also resist differential attack.

由以上证明知，如若我们所选取多变量公钥密码体制在现有的对MPKC攻击下是安全的，则本发明的环签名在现有的对MPKC攻击下也是安全的。From the above proofs, if the multivariate public key cryptosystem we choose is safe under existing attacks on MPKC, then the ring signature of the present invention is also safe under existing attacks on MPKC.

实施例1Example 1

基于多变量公钥密码oil-vinegar签名体制的匿名环签名方案：Anonymous ring signature scheme based on multi-variable public key cryptography oil-vinegar signature system:

步骤1.生成系统参数Step 1. Generate System Parameters

1)设置k＝GF(q)是特征为p＝2的有限域，其中q＝2⁸；1) Set k=GF(q) to be a finite field characterized by p=2, where q=2 ⁸ ;

2)令o＝30，v＝64，m＝30为多变量方程组中方程的个数，n＝o+v＝94为变量的个数；2) make o=30, v=64, m=30 is the number of equations in the multivariate equation system, and n=o+v=94 is the number of variables;

3)选择H：{0，1}^*→k³⁰为密码学安全的抗碰撞单向不可逆哈希函数。系统参数为(k，q，p，l，m，n，H)。3) Select H: {0, 1} ^* →k ³⁰ to be a cryptographically secure anti-collision one-way irreversible hash function. The system parameters are (k, q, p, l, m, n, H).

步骤2.密钥生成Step 2. Key Generation

1)假设环中有t个用户，设为U＝{u₀，u₁，..，u_t-1}，1) Suppose there are t users in the ring, set U={u ₀ , u ₁ ,.., u _t-1 },

根据多变量公钥密码体制，每个用户u_i(0≤i≤t-1)随机选择F_i是从kⁿ到k^m的可逆Oil-Vinegar多项式映射，Oil-Vinegar多项式具有如下形式：According to the multivariate public-key cryptosystem, each user u _i (0≤i≤t-1) randomly selects F _i as the reversible Oil-Vinegar polynomial mapping from k ⁿ to k ^m , and the Oil-Vinegar polynomial has the following form:

${F f}_{i i} = = {Σ Σ}_{l l = = 11}^{o o} {Σ Σ}_{j j = = 11}^{v v} {a a}_{ilj ilj} {x x}_{l l} {\overset{^^}{x x}}_{j j} + + {Σ Σ}_{l l = = 11}^{v v} {Σ Σ}_{j j = = 11}^{v v} {b b}_{ilj ilj} {\overset{^^}{x x}}_{l l} {\overset{^^}{x x}}_{j j} + + {Σ Σ}_{l l = = 11}^{o o} {c c}_{il il} {x x}_{l l} + + {Σ Σ}_{j j = = 11}^{v v} {d d}_{ij ij} {\overset{^^}{x x}}_{j j} + + {e e}_{i i}$

其中a_ilj，b_ilj，c_il，d_ij，e_i∈k；where a _ilj , b _ilj , c _il , d _ij , e _i ∈ k;

2)每个用户u_i(0≤i≤t-1)随机选择L_i是从kⁿ到kⁿ的一个可逆仿射变换2) Each user u _i (0≤i≤t-1) randomly selects L _i as an invertible affine transformation from k ⁿ to k ⁿ

${L L}_{i i} (({\overset{^^}{x x}}_{11},, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, {\overset{^^}{x x}}_{v v},, {x x}_{11},, \cdot &Center Dot; \cdot \cdot \cdot \cdot,, {x x}_{o o})) = = {M m}_{i i} {(({\overset{^^}{x x}}_{11},, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, {\overset{^^}{x x}}_{v v},, {x x}_{11},, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, {x x}_{o o}))}^{T T} + + {a a}_{i i},,$

其中M_i是有限域k上的一个n×n的可逆矩阵，a_i有限域k上的一个n×1的列向量；Among them, M _i is an n×n invertible matrix on finite field k, and a column vector of n×1 on _{a i} finite field k;

3)每个用户u_i(0≠i≤t-1)公布其公钥 3) Each user u _i (0≠i≤t-1) publishes its public key

${\overset{&OverBar; &OverBar;}{F f}}_{i i} (({x x}_{11},, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, {x x}_{n no})) = = (({\overset{&OverBar; &OverBar;}{f f}}_{i i 11},, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, {\overset{&OverBar; &OverBar;}{f f}}_{im im}))$

其中每一个都是k[x₁，…，x_n]中的多项式；each of them are all polynomials in k[x ₁ ,...,x _n ];

4)每个用户u_i(0≤i≤t-1)保密其私钥SK_i＝{F_i，L_i}；4) Each user u _i (0≤i≤t-1) keeps its private key SK _i ={F _i , L _i } secret;

5)环中的t个用户的公钥集记为

5) The public key sets of t users in the ring are denoted as

步骤3.环签名生成Step 3. Ring signature generation

设假设成员u_π(0≤π≤t-1)代表环对消息M∈{0，1}^*进行签名，u_π的公钥为

私钥为SK_π＝{F_π，L_π}。签名者u_π计算环签名的步骤如下：Suppose the hypothetical member u _π (0≤π≤t-1) represents the ring To sign a message M ∈ {0, 1} ^* , the public key of u _π is

The private key is SK _π ={F _π , L _π }. The steps for the signer u _π to calculate the ring signature are as follows:

3)计算3) calculate

${R R}_{π π} = = {L L}_{11 π π}^{- - 11} (({\overset{&OverBar; &OverBar;}{F f}}_{π π} ((u u)) - - {\overset{&OverBar; &OverBar;}{F f}}_{π π} (({c c}_{π π})))),,$

随机选择

以(x₁，…，x_o)为变量求解线性方程组random selection

Solve a system of linear equations with (x ₁ ,...,x _o ) as variables

${F f}_{π π} (({\overset{^^}{x x}}_{11}^{' '},, \cdot &Center Dot; \cdot \cdot \cdot &Center Dot;,, {\overset{^^}{x x}}_{v v}^{' '},, {x x}_{11},, \cdot \cdot \cdot &Center Dot; \cdot \cdot,, {x x}_{o o})) = = {R R}_{π π},,$

若该方程组无解，另外选取一个

重新求解，If the system of equations has no solution, choose another

re-solve,

令所求得的解为

记为Let the obtained solution be

recorded as

4)输出消息M关于环

的环签名为4) Output message M about the ring

The ring signature of is

步骤4.环签名的验证Step 4. Verification of the ring signature

给定消息M关于环

的环签名σ＝(c₀，s₀，s₁，…，s_t-1)，任何验证者对签名正确性的验证如下：Given a message M about the ring

The ring signature σ=(c ₀ , s ₀ , s ₁ ,..., _st-1 ), any verifier can verify the correctness of the signature as follows:

1)对于i＝0，1，…，t-1，计算1) For i=0,1,...,t-1, calculate

2)验证2) Verify

c_t＝c₀ c _t =c ₀

是否成立。如果成立，则接受该环签名，否则，拒绝该环签名。Whether it is established. If true, the ring signature is accepted, otherwise, the ring signature is rejected.

实施例2Example 2

基于多变量公钥密码Square+签名体制的匿名环签名方案：Anonymous ring signature scheme based on multivariable public key cryptography Square+ signature system:

square+体制是基于奇特征域上的多变量多项式体制，安全性比较高，可以抵抗量子计算机的攻击，并且加密解密具有较高的效率。我们结合square+体制，提出一个基于square+体制的环签名方案。The square+ system is a multivariate polynomial system based on a singular characteristic field, which has relatively high security and can resist quantum computer attacks, and has high encryption and decryption efficiency. We combine the square+ system and propose a ring signature scheme based on the square+ system.

1.Squaare+体制的构造1. The structure of Squaare+ system

令k是一个阶为q的有限域，其中q≡3mod4。

是k的n+l次扩张，其中l使得n+l为奇数。F是K到K的映射，F(X)＝X²，其中X∈K。Let k be a finite field of order q, where q≡3mod4.

is the n+l expansion of k, where l makes n+l odd. F is a mapping from K to K, F(X)=X ² , where X∈K.

随机选择一个单射仿射映射L₁：kⁿ→k^n+l；d个有n+l个变量的二次多项式Randomly select an injective affine map L ₁ : k ⁿ →k ^n+l ; d quadratic polynomials with n+l variables

g₁，…，g_d∈k[x₁，…，x_n+l]g ₁ ,...,g _d ∈ k[x ₁ ,...,x _n+l ]

以及一个可逆仿射映射L₂：k^n+l+d→k^n+l+d。φ：K→k^n+l，是向量空间的同构映射：and an invertible affine map L ₂ : k ^n+l+d → k ^n+l+d . φ: K→k ^n+l , is an isomorphic map of vector spaces:

由于φоFоφ^-1是一个n+l元的二次多项式组，通过附加g₁，…，g_d，我们可以产生映射：Since φоFоφ ^-1 is a quadratic polynomial group of n+l elements, by appending g ₁ ,...,g _d , we can generate the mapping:

F⁺：k^n+l-→k^n+l+d F ⁺ : k ^n+l -→k ^n+l+d

我们可以构造

为we can construct

for

私钥：private key:

映射L₁，L₂，F以及F⁺；Map L ₁ , L ₂ , F and F ⁺ ;

公钥：public key:

1)有限域k及其加法和乘法结构；1) Finite field k and its addition and multiplication structures;

2)n+l+d个多项式分量 2) n+l+d polynomial components

签名生成：Signature generation:

我们可以通过下面的步骤来对消息(或者消息摘要)(y′₁，y′₂…，y′_n+l+d)∈k^n+l+d进行签名：We can sign the message (or message digest) (y′ ₁ , y′ ₂ ..., y′ _n+l+d )∈k ^n+l+d through the following steps:

1)令(y₁，y₂，…y_n+l+d)＝L₂ ^-1(y′₁，y′₂，…，y′_n+l+d)；1) Let (y ₁ , y ₂ ,...y _n+l+d )=L ₂ ^-1 (y′ ₁ , y′ ₂ ,…,y′ _n+l+d );

2)移除无法混合的d个随机多项式g₁，…，g_d，得到(y₁，y₂，…，y_n+l)。令2) Remove d random polynomials g ₁ , ..., g _d that cannot be mixed to obtain (y ₁ , y ₂ , ..., y _n+l ). make

Y＝φ^-1(y₁，y₂，…，y_n+l)∈K；Y=φ ^-1 (y ₁ , y ₂ ,..., y _n+l )∈K;

3)求解X²＝Y，由于q≡3mod4且n+l是奇数，使得：|K|≡3mod4，我们可以利用以下公式来求解：3) To solve X ² =Y, since q≡3mod4 and n+l is an odd number, so that: |K|≡3mod4, we can use the following formula to solve:

$X x = = &PlusMinus; &PlusMinus; {Y Y}^{\frac{{q q}^{n no + + l l} + + 11}{44}},,$

这有两个解，但是由于L1是仿射的，一般来说，其中仅有一个是φ^-1оL₁的像，这个解在φ^-1оL₁下的原像就是签名(x′₁，…，x′_n)。There are two solutions, but since L1 is affine, in general, only one of them is the image of φ ^-1 оL ₁ , and the preimage of this solution under φ ^-1 оL ₁ is the signature (x′ ₁ , ..., x′ _n ).

签名验证：Signature Verification:

给定消息(y′₁，…，y′_n+l+d)的签名(x′₁，…，x′_n)，其中j＝1，…，n+l+d，计算Given a signature (x' ₁ , ..., x' n ) of a message (y' ₁ , ..., y' _n+l+d ₎ , where j=1, ..., n+l+d, compute

${y the y}_{j j}^{' '} = = {\overset{&OverBar; &OverBar;}{f f}}_{j j} (({x x}_{11}^{' '},, \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot,, {x x}_{n no}^{' '}))$

是否成立，如果成立，接受签名(x′₁，…，x′_n)，如果不成立，则拒绝签名(x′₁，…，x′_n)。Whether it is true, if true, accept the signature (x′ ₁ ,…,x′ _n ), if not, reject the signature (x′ ₁ ,…,x′ _n ).

2.基于多变量公钥密码Square+签名体制的匿名环签名方案2. Anonymous ring signature scheme based on multivariable public key cryptography Square+ signature system

步骤1.生成系统参数Step 1. Generate System Parameters

我们选择q＝31，n＝48，l＝3，d＝5，域k为F₃₁，K是k的51次扩张。仿射映射L₂：k⁴⁸→k⁵¹，可逆仿射映射L₁：k⁵⁶→k⁵⁶，因此，多变量方程组中方程的个数为m＝n+l+d＝56，变量的个数为n＝48。系统参数为(k＝F₃₁，q＝31，n＝48，r＝51，m＝56，H)，其中H：{0，1}^*→k⁴⁸为密码学安全的哈希函数。We choose q=31, n=48, l=3, d=5, field k is F ₃₁ , and K is the 51 expansion of k. Affine map L ₂ : k ⁴⁸ →k ⁵¹ , reversible affine map L ₁ : k ⁵⁶ →k ⁵⁶ , therefore, the number of equations in multivariate equations is m=n+l+d=56, the number of variables The number is n=48. The system parameters are (k=F ₃₁ , q=31, n=48, r=51, m=56, H), where H: {0, 1} ^* →k ⁴⁸ is a cryptographically secure hash function.

步骤2.密钥生成：Step 2. Key generation:

假设生成环中有t个用户，设为U＝{u₀，u₁，…，u_t-1}。设用户u_i的公私钥对为PK_i/SK_i，公钥：

是square+体制中的公钥，其中，F⁺：k⁵¹→k⁵⁶是square+体制中的映射，K是square+体制中的扩域，φ：K→k⁵¹，是向量空间的同构映射；私钥：SK_i＝{L_1i，F⁺，L_2i}，其中L_2i是从k⁴⁸到k⁵¹的单射仿射变换，L_1i是从k⁵⁶到k⁵⁶的可逆仿射变换，i＝0，1，…，t-1。环中的t个用户的公钥集记为

L = ({\overset{&OverBar;}{F}}_{0}, {\overset{&OverBar;}{F}}_{1}, \cdot \cdot \cdot, {\overset{&OverBar;}{F}}_{t - 1}) .

Assuming that there are t users in the generating ring, set U={u ₀ , u ₁ , . . . , u _t-1 }. Let the public-private key pair of user u _i be PK _i /SK _i , the public key:

is the public key in the square+ system, where F ⁺ : k ⁵¹ →k ⁵⁶ is the mapping in the square+ system, K is the extended domain in the square+ system, φ: K→k ⁵¹ is the isomorphic mapping of the vector space; Key: SK _i = {L _1i , F ⁺ , L _2i }, where L _2i is the injective affine transformation from k ⁴⁸ to k ⁵¹ , L _1i is the reversible affine transformation from k ⁵⁶ to k ⁵⁶ , i= 0, 1, ..., t-1. The public key set of t users in the ring is denoted as

L = ({\overset{&OverBar;}{f}}_{0}, {\overset{&OverBar;}{f}}_{1}, &Center Dot; &Center Dot; &Center Dot;, {\overset{&OverBar;}{f}}_{t - 1}) .

步骤3.环签名生成Step 3. Ring signature generation

设假设成员u_π(0≤π≤t-1)代表环

对消息M∈{0，1}^*进行签名，u_π的公钥为

私钥为SK_π＝{K_1i，F⁺，L_2i}。签名者u_π计算环签名的步骤如下：Suppose the hypothetical member u _π (0≤π≤t-1) represents the ring

To sign a message M ∈ {0, 1} ^* , the public key of u _π is

The private key is SK _π ={K _1i , F ⁺ , L _2i }. The steps for the signer u _π to calculate the ring signature are as follows:

3)计算时，参照square+体制的签名生成过程，求得消息m的签名为σ＝(c₀，s₀，s₁，…，s_t-1)；3) calculate , referring to the signature generation process of the square+ system, the signature of the message m is obtained as σ=(c ₀ , s ₀ , s ₁ ,..., _st-1 );

4)输出消息M关于环

的环签名为4) Output message M about the ring

The ring signature of is

σ＝(c₀，s₀，s₁，…s_t-1)。σ=(c ₀ , s ₀ , s ₁ , . . . _st-1 ).

步骤4.环签名的验证Step 4. Verification of the ring signature

给定消息M关于环

1)对于i＝0，1，…，t-1，计算1) For i=0,1,...,t-1, calculate

2)验证2) Verify

c_t＝c₀ c _t =c ₀

本发明的方法提供电子文档的环数字签名，可以用来保护电子文档在发布、存储或传输中的完整性、真实性；同时，又可以保护签名者的匿名性，以保证签名用户的信息不暴露，在该签名通过验证的情况下，使签名的验证者可以确信该签名是由多个用户组成的一个环中的某个成员签名的，但是验证者不能确认该签名到底是由哪一个成员签名的，每个成员签名的概率是相等的。The method of the present invention provides ring digital signatures of electronic documents, which can be used to protect the integrity and authenticity of electronic documents in publishing, storage or transmission; at the same time, it can protect the anonymity of signers to ensure that the information of signing users Exposure, when the signature is verified, the verifier of the signature can be sure that the signature is signed by a member of a ring composed of multiple users, but the verifier cannot confirm which member the signature is Signed, each member has an equal probability of signing.

本发明利用多变量公钥密码体制在量子计算下安全的优势来解决现有环签名体制在量子计算下将不再安全的缺陷。发明的基于多变量公钥密码体制的环签名方案，满足签名者的无条件匿名性和不可伪造性，在效率上优于传统密码体制。The invention utilizes the security advantage of the multi-variable public key cryptosystem under the quantum calculation to solve the defect that the existing ring signature system will no longer be safe under the quantum calculation. The invented ring signature scheme based on the multi-variable public key cryptosystem satisfies the unconditional anonymity and unforgeability of the signer, and is superior to the traditional cryptosystem in terms of efficiency.

Claims

1. The method for signing the anonymous ring of messages based on algebra is characterized in that the method is implemented according to the following steps:

Step 1. Generate System Parameters

1) Set k=GF(q) to be a finite field, where q=p ^l , p is a prime number, and l is a positive integer;

2) Let m be the number of equations in the multivariate equation system, and n be the number of variables;

3) Select H:{0,1}*→k ⁿ as a cryptographically secure hash function,

The system parameters are (k, q, p, l, n, m, H);

Step 2. Key generation

1) Suppose there are t users in the ring, set U={u ₀ ,u ₁ ,…,u _t-1 };

2) Choose a secure multi-variable public key cryptographic signature system. According to this system, each user u _i , where 0≤i≤t-1, chooses F _i as a reversible mapping from k ⁿ to k ^m , and F _i satisfies :

a) F _i (x ₁ ,…,x _n )=(f _i1 ,…,f _im ), where f _ij ∈ k[x ₁ ,…,x _n ], j=1,…,m;

b) any equation

F _i (x ₁ ,…,x _n )=(y ₁ ′,…,y _m ′)

are easy to solve;

3) For each user u _i , where 0≤i≤t-1, randomly select L _1i to be an invertible affine transformation from k ^m to k ^m

L _li (x ₁ ,…,x _m )=M _1i ·(x ₁ ,…,x _m ) ^T +a _1i ,

Where M _1i is an m×m invertible matrix on finite field k, and a _1i is an m×1 column vector on finite field k;

4) For each user u _i , where 0 ≤ i ≤ t-1, randomly select L _2i to be an invertible affine transformation from k ⁿ to k ⁿ

L _2i (x ₁ ,…,x _n )=M _2i ·(x ₁ ,…,x _n ) ^T +a _2i ,

Where M _2i is an n×n invertible matrix on finite field k, and a _2i is an n×1 column vector on finite field k;

5) Each user u _i , where 0≤i≤t-1, publishes its public key

each of them

are all polynomials in k[x ₁ ,…,x _n ];

6) Each user u _i , where 0≤i≤t-1, keeps its private key SK _i ={L _1i , F _i ,L _2i } secret;

7) The public key sets of t users in the ring are denoted as

Step 3. Ring signature generation

Suppose the signer u _π , where 0≤π≤t-1, represents that all members in the ring U={u ₀ ,u ₁ ,…,u _t-1 } perform ring signature on the message M ∈{0,1}*, The public key set of t users in the ring is denoted as Using its private key SK _i ={L _1i ,F _i ,L _2i }, the signature steps are as follows:

1) The signer u _π randomly selects u∈k ⁿ , and calculates

2) For i=π+1,π+2,…,t-1,0,1,…,π-1, randomly select s _i ∈ k ⁿ sequentially, and calculate