CN113505396B - Forward security ring signature method based on identity - Google Patents

Abstract

The invention discloses a forward security ring signature method based on identity, which comprises the following steps: 1. parameter setting: inputting a security parameter n, and generating a public parameter pp and a main private key MSK by the system; 2. private key extraction: inputting a public parameter pp, and user identity id epsilon {0,1}^* And a master private key MSK outputting a private key sk corresponding to the identity id_id The method comprises the steps of carrying out a first treatment on the surface of the 3. Updating the key: inputting public parameter pp, private key sk of a user in time period t_id,t And a new time period t+1, outputting the private key sk of the user in the time period t+1_id,t+1 The method comprises the steps of carrying out a first treatment on the surface of the 4. Signature: inputting a time period t, a system maximum ring S, a message m to be signed, a ring R and a private key sk_id,t The corresponding identity id E R outputs the signature sigma of the corresponding time period t_t The method comprises the steps of carrying out a first treatment on the surface of the 5. And (3) verification: input message signature pairs (m, sigma_t ) Time period t and loop R, output 1 if signature verification passes, otherwise output 0. The invention can improve the efficiency of user signature and resist the attack of the quantum computer on the premise of realizing the forward security of the signature, thereby solving the problem of certificate management in the traditional forward security ring signature.

Description

Forward security ring signature method based on identity

Technical Field

The invention relates to an information security technology, in particular to a forward security ring signature method based on identity.

Background

The forward security ring signature is a special ring signature, and can realize the forward security of a user private key besides the non-counterfeitability and anonymity of a common ring signature, namely, after the user private key is revealed at a certain moment, the security of the user signature before the moment is not affected, so that the forward security ring signature can be applied to the anonymity authentication of an ad hoc network. In addition, the forward security ring signature based on the identity can also eliminate the problems of extra storage overhead and calculation overhead caused by the public key certificate, and has better efficiency. Currently, forward secure ring signature schemes are based on the traditional difficult problem, so that the schemes cannot resist the attack of a quantum computer, and the security is not high.

Disclosure of Invention

The invention aims to solve the defects in the prior art, and provides a forward security ring signature method based on identity for resisting quantum attack, so that the efficiency of user signature can be improved on the premise of realizing forward security of signature, and the attack of a quantum computer can be resisted, thereby solving the problem of certificate management in the traditional forward security ring signature.

In order to achieve the aim of the invention, the invention adopts the following technical scheme:

the invention discloses a forward security ring signature method based on identity, which is characterized by comprising the following steps:

step 1, setting parameters;

step 1.1, setting a safety parameter n, and selecting a prime number q more than or equal to 2 and a first integerThe second integer m > 5nlogq and the Gaussian parameter +.>ω represents a lower bound parameter;

step 1.2, generating a random matrix by using trapdoor generation function TrapGen (q, n)And base B thereof_A ∈Z^m×m ；Representing that the values in the set {0,1, 2..q-1 } constitute a set of matrices of dimension n x m; z is Z^m×m Representing a set of non-negative integer constituent matrices of dimension m x m;

step 1.3, constructing common parametersAnd master private key msk=b_A ；H₁ 、H₂ Representing twoA collision-resistant hash function for transforming an arbitrary length input into a fixed length output by a hash algorithm,/->Representing a message space;

step 2, initial private key sk_id,0 Is extracted from the above;

step 2.1, defining user identity id E {0,1}^* ，{0,1}^* Representing a set of strings of arbitrary length consisting of 0,1, a tag matrix q=h for user id is calculated₁ (id) and constructing a user identity matrix A_id ＝[A|Q]The method comprises the steps of carrying out a first treatment on the surface of the The I represents the matrix A and Q connections;

step 2.2 Using a lattice randomization function RandBasis (ExtBusis (B)_A ,A_id ) S) generating a base R of user identities_id ∈Z^(m+1)×(m+1) ；Z^(m+1)×(m+1) Representing a set of non-negative integer matrices of dimensions (m+1) × (m+1);

step 2.3, for any node z, determining a set of Nodes (0→T-1), z∈Nodes (0→T-1), where Nodes (t→T-1) represents the smallest set of all ancestors in the binary tree that contain leaf Nodes { t..times, T-1} but do not contain { 0..times, T-1} and 0→T-1 represents the time period starting from 0 to T-1;

step 2.3.1, if z is E, T represents an empty set without substantial node, let user id correspond to private key sk at node z_id [z]= t; otherwise, executing the step 2.3.2;

step 2.3.2, use d_z Representing the length of the binary vector z, where d_z D is less than or equal to d, d represents the depth of the binary tree;

step 2.3.3 constructing a matrix of user ids at the corresponding node zWherein Bin (z) is a binary representation of node z, bin (z) [ d ]_z ]Represents the d_z A bit of->Representation sectionThe path of point z from root to node z is at depth d_z Matrix of places->The number of dimensions representing the values in the set {0,1, 2..q-1 } is n× ((d)_z +1) a matrix set of m+1);

step 2.3.4, calculating the base of the user id at the corresponding node zMake sk_id [z]＝R_id,z The method comprises the steps of carrying out a first treatment on the surface of the The expression generation, random () represents the randomization of the basis, extBasis () represents the extraction of the basis, s_dz A Gaussian parameter randomly selected when the base is randomized is represented;

step 2.3.5, let the initial private key corresponding to the user identity id be sk_id,0 ＝{sk_id [z],z∈Nodes(0→T-1)}；

Step 3, private key sk of time period t_id,t Is updated according to the update of (a);

step 3.1, let the private key sk of the known time period t_id,t ＝{sk_id [z]z.epsilon.Nodes (t.fwdarw.T-1) }, the key evolution process for the new binary vector z'.epsilon.Nodes (t+1.fwdarw.T-1) is as follows:

step 3.1.1, if z 'E' T, enabling the user id to correspond to the private key sk at the node z_id [z′]＝⊥；

If there is a prefix where z.epsilon.Nodes (t.fwdarw.T-1) is z':

if z' =z, let sk_id [z′]＝sk_id [z]；

If z '=z||y, y represents a non-null binary bit string, |represents z and y are connected, then the base of the user at the corresponding node z' is calculatedMake sk_id [z']＝R_id,z' ；A_id,z' Represents the matrix used in extracting the basis at node z' and +.>A Gaussian parameter randomly selected when the base is randomized is represented;

step 3.1.2, calculating the private key sk for time period t+1_id,t+1 ＝{sk_id [z′],z′∈Nodes(t+1→T-1)}；

Step 4, signing;

step 4.1, defining the maximum ring as S, the message to be signed as mu, the current ring as R, and the private key sk of the time period t_id,t The corresponding identity id E R;

step 4.2, defining the current ring R as the identity set of all usersWherein, id_s Representing the s-th user identity->Representing the number of users, the s-th user identity id in the time period t_s Is +.>Message mu epsilon {0,1}^* ；

Step 4.3, assume the s-th user identity id_s If the signature is a signer, the private key of the signer in the time period t is analyzedAcquiring the base of the signer at node z>Wherein z ε Nodes (t→T-1), z=bin (T), bin represents a binary representation corresponding to an integer time T, and the length of Bin (T) is d_t ；

Step 4.4, constructing a verification matrix required by the user s to sign the ringWherein Q is_s+1 Identity tag matrix representing the s+1th user,>identity matrix representing user s, B_t Represents a path matrix from the root to node t, andrepresenting that the path of node t from the root to node t is at depth d_t A matrix of places;

step 4.5, selecting a random number τ e {0,1}^ω(logn) ，{0,1}^ω(logn) Representing a set of strings of length ω (logn) consisting of 0 or 1, calculating a hash value u=h₂ (R,μ,t,τ)；

Step 4.6, utilizing trapdoor sampling functionGenerating a vector +.>Wherein e satisfies the Gaussian distribution->r represents a gaussian parameter chosen randomly,/->Representing a q-mode lattice;

step 4.6, obtaining signature sigma of time period t_t ＝(e,R,t,τ)；

Step 5, signature sigma according to the message mu_t Time period t and loopVerifying message signature pairs (mu, sigma)_t ) Outputting 1 if the verification is passed, otherwise outputting 0;

step 5.1. Signature σ_t Resolving into (e, R, t, tau);

step 5.2, according to the hash value u and the verification matrix A_R If and only if (A_R ·e)modq＝H₂ (R, μ, t, τ) andwhen the verification is passed, otherwise, the verification is failed, wherein O represents the time complexity, and I e I represents l of the vector e₂ Norms.

Compared with the prior art, the invention has the beneficial effects that:

1. the invention adopts an identity-based method, a user does not need a traditional public key certificate to verify the identity, but directly uses the self identity as a self private key, and utilizes a system main private key MSK to extract and randomize a base through identity information by a private key extraction algorithm, thereby deriving a private key for a corresponding user, and eliminating the additional storage expenditure and calculation expenditure brought by the public key certificate in traditional public key cryptography.

2. The invention adopts the lattice cryptography technology to design the forward safe ring signature scheme, the whole life cycle of the cryptosystem is divided into T time periods, the current time period T is ended, and when the next time period t+1 is started, a signer can realize secret key updating by extracting and randomizing the current secret key, and the process is a one-way process, so that the problem that secret key information in the past time period can be exposed when the secret key is leaked in the current time period can be solved, and the validity of the signature in the past time period can not be influenced even if the current secret key is leaked is ensured. The whole process is based on the assumption of difficulty in solving small integers on a grid, so that the scheme can resist the attack of a quantum computer.

Drawings

FIG. 1 is a diagram of a binary tree structure of the present invention;

FIG. 2 is a flow chart of the main steps of the present invention;

Detailed Description

In this embodiment, as shown in fig. 2, a forward security ring signature method based on identity is to use a lattice cryptographic technique, first define two sets, where n, m, q are positive integers,

defining parameters on the set lambda as s > 0 and the center as c E R^m The discrete gaussian distribution of (2) is:

when c=0, note ρ_s,0 Andp respectively_s And->

Secondly, the invention adopts a binary tree structure to evolve the user key. In this binary tree, each node except the leaf node has two branches, the left branch being denoted by 0 and the right branch being denoted by 1. For simplicity, in the scheme, the life cycle of the scheme is divided into t=2^d A time period, where d is a positive integer. Each time period T e {0,1,.. The T-1} is associated with a leaf Bin (T), where Bin (T) is a bit decomposition of T, which can be understood to be the path from the root to the node. For j=1..d+1, the "right sibling at depth j" for time period t is defined as:

define node set nodeb (t→t-1) = { sibling (1, T),...

Fig. 1 shows a time period of t=2³ Is a binary tree of (c). To populate the collective node (t→T-1), it starts first from leaf Bin (T) and adds it to the Nodes (t→T-1), and if its sibling exists, we also add it to the collective node Nodes (t→T-1). And then recursively up, adding siblings of all parent Nodes on the path (if any) to the set Nodes (t→T-1) until the root node is reached. And then stopping, and outputting a corresponding list Nodes (T-T-1). Taking node (001) as an example, there are Nodes (1→7) = { (1), (01), ∈ (001) } on the path from node ε to leaf node (001).

In a specific implementation, the forward security ring signature method includes the following steps:

step 1, setting parameters;

step 1.1, setting a safety parameter n, and selecting a prime number q more than or equal to 2 and a first integerThe second integer m > 5nlogq and the Gaussian parameter +.>Omega represents a lower bound parameter, i.e. greater than but not equal to +.>

Step 1.2, generating a random matrix by using trapdoor generation function TrapGen (q, n)And base B thereof_A ∈Z^m×m ；The values in the set {0,1, 2..q-1 } are shown to constitute a matrix set of dimension n m. Z is Z^m×m Representing a set of non-negative integers making up a matrix of dimension m x m. The TrapGen (q, n) algorithm refers to: the algorithm outputs a matrix which is approximately uniform and random, wherein the given integer n is more than or equal to 1, q is more than or equal to 2, and m is more than or equal to 5nlogq>And lattice lambda^⊥ (A) Is a group B of (2)_A ∈Z^m×m And satisfy +.>And B_A O (nlogq) wherein +.>Is B_A Is used for the orthogonalization of the (c).

Step 1.3, constructing common parametersAnd master private key msk=b_A ；H₁ 、H₂ A collision-resistant hash function representing two inputs of arbitrary length transformed into outputs of fixed length by a hash algorithm, < ->Representing a message space;

step 2, initial private key sk_id,0 Is extracted from the above;

step 2.1, defining user identity id E {0,1}^* ，{0,1}^* Representing a set of strings of arbitrary length consisting of 0,1, a tag matrix q=h for user id is calculated₁ (id) and constructing a user identity matrix A_id ＝[A|Q]The method comprises the steps of carrying out a first treatment on the surface of the The I represents the matrix A and Q connections;

step 2.2 Using a lattice randomization function RandBasis (ExtBusis (B)_A ,A_id ) S) generating a base R of user identities_id ∈Z^(m+1)×(m+1) ；Z^(m+1)×(m+1) Representing a set of non-negative integer matrices of dimensions (m+1) × (m+1). Wherein, randBasis (A, S, r) algorithm refers to: input matrixLattice lambda^⊥ (A) Is a radix S and Gaussian parameter +.>The algorithm outputs a lattice Λ^⊥ (A) Is satisfied with +.>And S' does not reveal any information about the base S.

Step 2.3, for any node z, determining a set of Nodes (0→T-1), z∈Nodes (0→T-1), where Nodes (t→T-1) represents the smallest set of all ancestors in the binary tree that contain leaf Nodes { t..times, T-1} but do not contain { 0..times, T-1} and 0→T-1 represents the time period starting from 0 to T-1;

step 2.3.1, if z is E, T represents an empty set without substantial node, let user id correspond to private key sk at node z_id [z]= t; otherwise, executing the step 2.3.2;

step 2.3.2, use d_z Representing the length of the binary vector z, where d_z D is less than or equal to d, d represents the depth of the binary tree;

step 2.3.3 constructing a matrix of user ids at the corresponding node zWherein Bin (z) is a binary representation of z, bin (z) [ d ]_z ]Represents the d_z A bit of->Representing that the path of node z from root to node z is at depth d_z Matrix of places->The number of dimensions representing the values in the set {0,1, 2..q-1 } is n× ((d)_z +1) a matrix set of m+1);

step 2.3.4, calculating the base of the user id at the corresponding node zMake sk_id [z]＝R_id,z The method comprises the steps of carrying out a first treatment on the surface of the The expression of generation, randBasis) Representing the randomization of the basis, extbussis () represents the extraction of the basis,a Gaussian parameter randomly selected when the base is randomized is represented; wherein ExtBusis (S)₀ ,A＝A₀ ||A₁ ) The algorithm is as follows: input matrix->Lattice lambda^⊥ (A₀ ) Is a radical S of (2)₀ A matrix->The algorithm outputs a lattice Λ^⊥ (A) Is a base S epsilon Z of (2)^m×m Satisfy->Wherein m=m₀ +m₁ 。

Step 2.3.5, let the initial private key corresponding to the user identity id be sk_id,0 ＝{sk_id [z],z∈Nodes(0→T-1)}；

Step 3, private key sk of time period t_id,t Is updated according to the update of (a);

step 3.1, let the private key sk of the known time period t_id,t ＝{sk_id [z]z.epsilon.Nodes (t.fwdarw.T-1) }, the key evolution process for the new binary vector z'.epsilon.Nodes (t+1.fwdarw.T-1) is as follows:

step 3.1.1, if z 'E' T, enabling the user id to correspond to the private key sk at the node z_id [z′]＝⊥；

If there is a prefix where z.epsilon.Nodes (t.fwdarw.T-1) is z':

if z' =z, let sk_id [z′]＝sk_id [z]；

If z '=z||y, y represents a non-null binary bit string, |represents z and y are connected, then the base R of the user at the corresponding node z' is calculated_id,z' ←RandBasis(ExtBasis(R_id,z ,A_id,z' ),s_dz' ) Make sk_id [z']＝R_id,z' ；A_id,z' Representation A_id,z' Represents the matrix used in extracting the basis at node z', anA Gaussian parameter randomly selected when the base is randomized is represented;

step 3.1.2, calculating the private key sk for time period t+1_id,t+1 ＝{sk_id [z′],z′∈Nodes(t+1→T-1)}；

Step 4, signing;

step 4.1, defining the maximum ring as S, the message to be signed as mu, the current ring as R, and the private key sk of the time period t_id,t The corresponding identity id E R;

step 4.2, defining the current ring R as the identity set of all usersWherein, id_s Representing the s-th user identity->Representing the number of users, the s-th user id in the time period t_s Is +.>Message mu epsilon {0,1}^* ；

Step 4.3, assume the s-th user identity id_s If the signature is a signer, the private key of the signer in the time period t is analyzedAcquiring the base of the signer at node z>Wherein z ε Nodes (t→T-1), z=bin (T), bin represents a binary representation corresponding to an integer time T, and the length of Bin (T) is d_t ；

Step 4.4, constructing a verification matrix required by the user s to sign the ringWherein Q is_s+1 Identity tag matrix representing the s+1th user,>identity matrix representing user s, B_t Represents a path matrix from the root to node t, andrepresenting that the path of node t from the root to node t is at depth d_t A matrix of places;

step 4.5, selecting a random number τ e {0,1}^ω(logn) ，{0,1}^ω(logn) Representing a set of strings of length ω (logn) consisting of 0 or 1, calculating a hash value u=h₂ (R,μ,t,τ)；

Step 4.6, utilizing trapdoor sampling functionGenerating a vector +.>Wherein e satisfies the Gaussian distribution->r represents a randomly selected Gaussian parameter, whereSamplePre(A,B_A The u, r) algorithm refers to: input matrix->And lattice lambda^⊥ (A) Is a group B of (2)_A Vector->Parameter->The algorithmOutput statistics close to discrete Gaussian distribution>Is a vector e E Z^m Ae=ymodq and +.>

Step 4.6, obtaining signature sigma of time period t_t ＝(e,R,t,τ)；

Step 5, signature sigma according to the message mu_t Time period t and loopVerifying message signature pairs (mu, sigma)_t ) Outputting 1 if the verification is passed, otherwise outputting 0;

step 5.1. Signature σ_t Resolving into (e, R, t, tau);

step 5.2, according to the hash value u and the verification matrix A_R If and only if (A_R ·e)modq＝H₂ (R, μ, t, τ) andwhen the verification is passed, otherwise, the verification is failed, wherein O represents the time complexity, and I e I represents l of the vector e₂ Norms.

Scheme analysis:

correctness: first assume a ring signature sigma_t = (e, R, t, τ) is generated strictly according to the scheme described above. Assuming that the signature is performed within the t time period, the private key sk is extracted according to the private key extraction and key updating algorithm in the scheme_id,t ＝{sk_id [z]Obtained from z.epsilon.Nodes (t.fwdarw.T-1)Where z.epsilon.Nodes (t.fwdarw.T-1), z=bin (T), length d_t . Wherein,according to the property of the algorithm ExtBusis and RandBasis, the +.>Due toFor u=h₂ (R, μ, t, τ), u=a according to the nature of the algorithm SamplePre_R e modq is true and will satisfy +.>Thus, the identity-based forward security ring signature scheme is correct.

Safety: mu and ring for the same messageDifferent signed user ids during the same time period t_b Two signatures sigma generated_0,t Sum sigma_1,t Is statistically indistinguishable, so this scheme satisfies anonymity. The above-mentionedIn the construction, as the base is the private key in the scheme, the forward security is satisfied by continuously randomizing by calling the algorithm, even if the adversary is +.>The private key for the current time period t is acquired, and the signature key before that cannot be acquired. Furthermore, find a short vector e such that A_R emodq=0 can be reduced to a small integer to solve the difficult problem, so the present solution satisfies the non-counterfeitability.

In summary, the forward security ring signature method based on identity is based on the difficult problem of lattice correlation, so that the attack of a quantum computer is expected to be resisted, and meanwhile, a binary tree structure is adopted to carry out user key evolution, so that better efficiency is provided on the premise of realizing forward security of signature. In addition, the invention introduces an identity-based cryptosystem, so that the problem of certificate management in the traditional forward security ring signature is solved, and the efficiency of the scheme is further improved.

Claims (1)

1. The forward security ring signature method based on the identity is characterized by comprising the following steps of:

step 1, setting parameters;

step 1.1, setting a safety parameter n, and selecting a prime number q more than or equal to 2 and a first integerThe second integer m > 5nlogq and the Gaussian parameter +.>ω represents a lower bound parameter;

step 1.2, generating a random matrix by using trapdoor generation function TrapGen (q, n)And base B thereof_A ∈Z^m×m ；/>Representing that the values in the set {0,1, 2..q-1 } constitute a set of matrices of dimension n x m; z is Z^m×m Representing a set of non-negative integer constituent matrices of dimension m x m;

step 1.3, constructing common parametersAnd master private key msk=b_A ；H₁ 、H₂ Representing two collision-resistant hash functions transforming arbitrary length inputs into fixed length outputs by a hash algorithm, < >>Representing a message space;

step 2, initial private key sk_id,0 Is extracted from the above;

step 2.1, defining user identity id E {0,1}^* ，{0,1}^* Representing a set of strings of arbitrary length consisting of 0,1, a tag matrix q=h for user id is calculated₁ (id) and constructing a user identity matrix A_id ＝[A|Q]The method comprises the steps of carrying out a first treatment on the surface of the The I represents the matrix A and Q connections;

step 2.2 Using a lattice randomization function RandBasis (ExtBusis (B)_A ,A_id ) S) generating a base R of user identities_id ∈Z^(m+1)×(m+1) ；Z^(m+1)×(m+1) Representing a set of non-negative integer matrices of dimensions (m+1) × (m+1);

step 2.3, for any node z, determining a set of Nodes (0→T-1), z∈Nodes (0→T-1), where Nodes (t→T-1) represents the smallest set of all ancestors in the binary tree that contain leaf Nodes { t..times, T-1} but do not contain { 0..times, T-1} and 0→T-1 represents the time period starting from 0 to T-1;

step 2.3.1, if z is E, T represents an empty set without substantial node, let user id correspond to private key sk at node z_id [z]= t; otherwise, executing the step 2.3.2;

step 2.3.2, use d_z Representing the length of the binary vector z, where d_z D is less than or equal to d, d represents the depth of the binary tree;

step 2.3.3 constructing a matrix of user ids at the corresponding node zWherein Bin (z) is a binary representation of node z, bin (z) [ d ]_z ]Represents the d_z A bit of->Representing that the path of node z from root to node z is at depth d_z Matrix of places->The number of dimensions representing the values in the set {0,1, 2..q-1 } is n× ((d)_z +1) a matrix set of m+1);

step 2.3.4, calculating the base of the user id at the corresponding node zMake sk_id [z]＝R_id,z The method comprises the steps of carrying out a first treatment on the surface of the The expression "generation," randbisis () represents the randomization of the base, extBasis () represents the extraction of the base,a Gaussian parameter randomly selected when the base is randomized is represented;

step 2.3.5, let the initial private key corresponding to the user identity id be sk_id,0 ＝{sk_id [z],z∈Nodes(0→T-1)}；

Step 3, private key sk of time period t_id,t Is updated according to the update of (a);

step 3.1, let the private key sk of the known time period t_id,t ＝{sk_id [z]z.epsilon.Nodes (t.fwdarw.T-1) }, the key evolution process for the new binary vector z'.epsilon.Nodes (t+1.fwdarw.T-1) is as follows:

step 3.1.1, if z 'E' T, enabling the user id to correspond to the private key sk at the node z_id [z′]＝⊥；

If there is a prefix where z.epsilon.Nodes (t.fwdarw.T-1) is z':

if z' =z, let sk_id [z′]＝sk_id [z]；

If z '=z||y, y represents a non-null binary bit string, |represents z and y are connected, then the base R of the user at the corresponding node z' is calculated_id,z' ←RandBasis(ExtBasis(R_id,z ,A_id,z' ),s_dz' ) Make sk_id [z']＝R_id,z' ；A_id,z' Represents the matrix used in extracting the basis at node z', anA Gaussian parameter randomly selected when the base is randomized is represented;

step 3.1.2, calculating the private key sk for time period t+1_id,t+1 ＝{sk_id [z′],z′∈Nodes(t+1→T-1)}；

Step 4, signing;

step 4.1, defining the maximum ring as S, the message to be signed as mu, the current ring as R, and the private key sk of the time period t_id,t The corresponding identity id E R;

step 4.2, defining the current ring R as an identity set r= { id of all users₁ ,…,id_s ,…,id_l "wherein id_s Represents the s-th user identity, l represents the number of users, and the s-th user identity id is in the time period t_s Is the private key of (2)Message mu epsilon {0,1}^* ；

Step 4.3, assume the s-th user identity id_s If the signature is a signer, the private key of the signer in the time period t is analyzedAcquiring the base of the signer at node z>Wherein z ε Nodes (t→T-1), z=bin (T), bin represents a binary representation corresponding to an integer time T, and the length of Bin (T) is d_t ；

Step 4.4, constructing a verification matrix required by the user s to sign the ringWherein Q is_s+1 Identity tag matrix representing the s+1th user,>identity matrix representing user s, B_t Representation ofA path matrix from the root to node t, and +.>Representing that the path of node t from the root to node t is at depth d_t A matrix of places;

step 4.5, selecting a random number τ e {0,1}^ω(logn) ，{0,1}^ω(logn) Representing a set of strings of length ω (logn) consisting of 0 or 1, calculating a hash value u=h₂ (R,μ,t,τ)；

Step 4.6, utilizing trapdoor sampling functionGenerating a vector +.>Wherein e satisfies the Gaussian distribution->r represents a gaussian parameter chosen randomly,/->Representing a q-mode lattice;

step 4.6, obtaining signature sigma of time period t_t ＝(e,R,t,τ)；

Step 5, signature sigma according to the message mu_t Time period t and loop r= { id₁ ,…,id_l Verifying message signature pairs (μ, σ)_t ) Outputting 1 if the verification is passed, otherwise outputting 0;

step 5.1. Signature σ_t Resolving into (e, R, t, tau);

step 5.2, according to the hash value u and the verification matrix A_R If and only if (A_R ·e)modq＝H₂ (R, μ, t, τ) andwhen the verification is passed, otherwise, the verification is failed, wherein O represents the time complexity, and I e I represents l of the vector e₂ Norms.