CN102710757B - Distributed cloud storage data integrity protection method - Google Patents

Abstract

A distributed cloud storage data integrity protection method, the method has seven steps: Step 1: Data segmentation and encoding {F→M}; Step 2: Generation of homomorphic label HVTs {(sk,F)→HVTs} ; Step 3: Remote storage of data {(M ^(j) ,HVT)→S _j }; Step 4: User initiates a challenge {chal}; Step 5: Server responds {R}; Step 6: Verification {(R, sk)→("success", "failure")}; Step 7: Data repair {(M ^* ,P)→F}. In the present invention, the user adopts random data block sampling to reduce communication overhead, adopts linear coding to realize data error location and error recovery, and the number of times of data possession verification is not limited, the verification confidence is high, and it is safe and reliable. It has good practical value and broad application prospects in the field of cloud computing security technology.

Description

A distributed cloud storage data integrity protection method

(1) Technical field

The invention relates to a distributed cloud storage data integrity protection method, which is also a method for verifying the integrity of user data stored in a cloud server and performing data error correction, and belongs to the field of cloud computing security.

(2) Background technology

The rapid development and popularization of Internet network application technology, coupled with the development of Web2.0 has led to the rapid growth of network users and network data volume, and users have put forward higher requirements for data processing capabilities. The characteristics of cloud computing cater to these needs. Cloud computing provides great convenience for user storage, and users no longer need to care about complicated hardware management.

Although cloud computing has these attractive advantages, it also brings new security challenges and threats to data protection: First, because users no longer physically own their data, traditional encryption for data protection cannot be directly use. Therefore, a method that can verify the correct storage of data is needed. Considering a large number of users and a large amount of data in the cloud, how to effectively verify the correctness of outsourced data is a huge challenge for data storage security in cloud computing. Secondly, although cloud computing facilities are more powerful and reliable than personal computing devices, they still face internal and external data integrity threats. A large number of hackers coveting cloud data are constantly digging for loopholes in service providers' Web applications. Open the gap with expectations and get valuable data. Finally, it is not the users themselves who have priority access to data, but the cloud computing service provider. Due to interest issues, cloud service providers may act dishonestly with user data.

Therefore, in the practical application of cloud computing, it is particularly important to design a robust and secure solution that can ensure the correct storage of data. For mass data storage such as cloud storage, on the one hand, we must consider the high efficiency and low overhead of data possession verification, and on the other hand, we must consider the countermeasures that can be taken in case of data storage errors. Based on this consideration, we invented this method. The main technologies involved are Goppa error correction coding, signature technology based on elliptic curve, and Paillier additive homomorphic encryption algorithm.

First, Goppa codes are a class of rational fractional codes constructed by the Russian scholar Goppa system in the early 1970s. It is an important class of linear error-correcting codes, and its main advantage is that some of its subclasses can achieve the performance given by Shannon's channel coding theorem, and it has a fast decoding algorithm. In particular, the number of its unequal codes is very large, so, in 1978, McElice used Goppa codes to construct a class of public-key cryptosystems, and since then began to use error-correcting codes to construct cryptosystems and various authentication codes. Therefore, no matter in practice or theory, and no matter in error control system or in cipher, Goppa code is of great significance. Its definition is as follows: Suppose 0<n≤q ^m , L={a ₀ ,a ₁ ,…a _n-1 } is an ordered set, a _i ∈GF(q ^m ) and not equal to each other, and let GF( In the n-dimensional space GF ⁿ (q) on q), the code word C=[c _n-1 c _n-2 ...c ₀ ]∈GF ⁿ (q), and C on GF(q ^m ) The rational expression of z is At this point, the generator polynomial g(z) of the Goppa code satisfies: {C; R _c (z)=0modg(z)}.

Secondly, the Paillier cryptographic algorithm satisfies the property of additive homomorphism, that is, for data m∈Z _n , the encrypted result with public key n and generator g is: ε(m)=g ^m r ⁿ mod n ² , where r is random number, its homomorphic properties are:

$\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; g</span>}}^{{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{\mathrm{<span\; class="notranslate">\; r</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; g</span>}}^{{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; r</span>}}^{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; g</span>}}^{{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span>$

Finally, Elliptic curve cryptography (ECC for short) is the most widely used public key cryptosystem in cryptography. The main advantage of ECC is that in some cases it uses smaller keys than other methods (such as the RSA encryption algorithm), providing an equivalent or higher level of security. Its security is based on the discrete logarithm problem on the elliptic curve, that is, the equation Q=kP is considered on the Abel group E _p (a, b) composed of the elliptic curve, where P, Q∈E _p (a, b), k < p, then it is easy to find Q from k and P, but it is difficult to find k from P and Q.

(3) Contents of the invention

(1) Purpose of the invention

The purpose of the present invention is to provide a distributed cloud storage data integrity protection method, which overcomes the shortcomings of the prior art. It can be used to solve the protection and control of remote data by users in the cloud storage environment. It realizes the verification of the integrity and ownership of the data stored in the cloud server by the user. The invention has an unlimited number of verifications. Using random data block extraction, error location and error recovery functions when data storage errors.

(2) Technical solution

In order to achieve the above object, the present invention combines Goppa error correction coding technology, elliptic curve cryptographic technology and Paillier homomorphic encryption technology, and its technical scheme is as follows.

The present invention includes two entities, a user (User) and a cloud service provider (CSP). The technical solution for possession verification will be described below in conjunction with the accompanying drawings. Figure 1 is a flow chart of the present invention; Figure 2 is a schematic diagram of distributed storage after data preprocessing; Figure 3 is a challenge-response mechanism interaction diagram.

As shown in Fig. 1, the present invention includes 7 steps in total, which can be divided into three stages of initialization, challenge-response and interactive operation according to the execution stage.

The present invention is a distributed cloud storage data integrity protection method, the specific steps of the method are as follows:

Phase 1: Initialization: including steps (1)~(3), the owner of the data block F performs data segmentation and encoding {F→M} operations, and the generation of homomorphic tags (HVTs) {(sk,F)→HVTs } operation, and then outsource the coded data M and homomorphic label HVTs to the cloud server for storage and management, and the user must strictly ensure the security of the private key.

Step 1: Data segmentation and encoding {F→M}: User first preprocesses the original data F (existing in the form of files) to generate storage data M. F is divided into m data blocks of equal size {F ₁ , F ₂ ,...,F _m }, and each data block is further divided into l parts Then we encode it. In the scheme, the Goppa code encoding scheme is used to encode the original data F to generate the encoded data M. Finally, the user (User) outsources the encoded data M to the cloud CSP for storage and management;

Step 2: Generation of Homomorphic Verifiable Tags (HVTs) {(sk,F)→HVTs}: For each data block Based on the homomorphic encryption algorithm, we calculate the homomorphic label for it according to the set security parameters, and the homomorphic label we generate has the property of additive homomorphism;

Step 3: Remote storage of data {(M ^(j) ,HVT)→S _j }: the user assigns the homomorphic label It is stored in the jth server together with the data block M ^(j) , and similarly, other databases are stored in other n servers. Users store private keys and some random numbers themselves.

Phase 2: Challenge-Response: Including steps (4)~(6), the user generates a challenge and specifies the random data block to be detected. According to the user challenge, the cloud server executes GenProof {(chal, HVTs, M)→R} operation to respond. Finally, the user makes the final data detection result judgment by performing the verification {(R, sk)→("success","failure")} operation.

Step 4: The user initiates a challenge {chal}: when the user wants to verify whether the server S _j holds data correctly, the user sends a challenge to it: the user generates a challenge chal and sends it to the server S _j ;

Step 5: The server responds: GenProof (GenProof) {(chal, HVTs, M)→R}: When the server receives the challenge chal, the server storing the data block M ^(j) needs to generate a proof R=(T, ρ). After that, the server returns R to the user;

Step 6: Verification {(R,sk)→("success","failure")}: When the user receives the R returned by the server, he uses his private key sk to perform calculations, thereby performing an operation on the data state stored in the server Judgment, the result is "success" or "failure".

Phase 3: Interactive operation: including step (7), if the output result of the verification {(R,sk)→("success","failure")} operation is "failure", the user requires the CSP to perform data recovery operations, This may require interaction between the two parties. Under normal circumstances, the user can download the data M, and then perform repair {(M ^* ,P)→F} to restore the original data.

Step 7: Data repair {(M ^* ,P)→F}: If data corruption is detected, we can determine the storage error occurred on the server S _j storing the data block, at this time, the error correction adopted in preprocessing can be used The original data F can be restored by decoding the damaged data M ^* and P.

(3) Advantages and effects

The present invention is a distributed cloud storage data integrity protection method, the method involves data encoding, data verification and data recovery, its advantages and effects are: 1) the user's local storage is small, and the user only needs to store the code to generate The matrix and the private key can verify the possession of the data; 2) The amount of interactive data is small, the communication volume of the challenge sent by the user and the response made by the server is fixed, and has nothing to do with the size of the stored data; 3) The user can initiate the holding The number of verification challenges is not limited; 4) The method of calculating the check block by random sampling can ensure the high confidence of the check while reducing the computing cost of the server; 5) The linear error correction coding technology is used to preprocess the stored data Data error location and error correction are realized.

(4) Description of drawings

Fig. 1 is a flow chart of the present invention;

Figure 2 Data preprocessing and distribution storage diagram;

Figure 3 Challenge-response mechanism flow chart;

The symbols in the figure are explained as follows:

In Figure 1, numbers 1, 2, 3, 4, 5, 6, and 7 represent the serial numbers of each step, F represents the original file, and M represents the encoded file;

In Fig. 2, M ^(j) represents the encoded data, Indicates each block of data after M ^(j) is divided into blocks, S _i represents the i-th server, chal represents the challenge generated by the user, and R ^(j) represents the response of server S _j ;

(5) Specific implementation methods

The integrity protection method described below will be described in detail with reference to the accompanying drawings. Fig. 1 is a flow chart of the present invention; Fig. 2 is a schematic diagram of distributed storage after data preprocessing in the present invention; Fig. 3 is an interactive diagram of the challenge-response mechanism of the present invention.

Main symbols and algorithm explanations:

(1) F represents the user's original data, and M represents the encoded data, including n×l data blocks. is the i-th block of the j-th data vector, it will be stored in the server S _j G ^* = (I _(nr)×(nr) |P ^T ) represents the generation matrix of the Goppa code, where P is the redundancy check Block generation matrix; M ^* represents the data blocks stored in the server with errors.

(2) E() and D() are the encryption algorithm and decryption algorithm of the Paillier encryption algorithm respectively, k ₁ is its public key, k ₂ is its private key, N is the modulus, and the Paillier encryption algorithm satisfies the additive homomorphism nature.

(3) G is the generator of the elliptic curve E _P (a,b), where the large prime number p<N, P=yG, P represents the public parameters in the challenge, and y is the confidential parameter generated by the user;

(4) π( ) is a pseudorandom permutation (PRP) function, which satisfies $\mathrm{\&pi;}:{\left\{\mathrm{0,1}\right\}}^{k_3}\&times;{\left\{\mathrm{0,1}\right\}}^{{\log }_2\left(\mathrm{no}\right)}\&Right\; Arrow;{\left\{\mathrm{0,1}\right\}}^{{\log }_2\left(\mathrm{no}\right)};$ Among them, k ₃ is its key, which is used to determine the position of the data block randomly drawn each time.

(5) is a confidential random number, p is a large prime number set in (3), It can be generated by a pseudo-random generator with a key, which is the user's confidentiality parameter;

The present invention can be divided into three stages of initialization, challenge-response, and interactive operation. See Fig. 1, a kind of distributed cloud storage data integrity protection method of the present invention, the concrete steps of this method are as follows:

1. Initialization phase

In this stage, data segmentation, encoding and distributed storage are shown in Figure 2.

Step 1: Data chunking and encoding:

(1) The user divides the data file F to be stored in the cloud into l×m blocks, and each block can be expressed as an element GF(p) in the Galois field, where p is a large prime number. Using a matrix table is:

(2) Use the Goppa code to encode the original data, and after encoding, it becomes l×n blocks, and its minimum code distance is d _min ≥ r+1, that is, its error detection ability is r, and its error correction ability is (d _min -1 )/2. The encoded data is:

Among them, G ^* is the generating matrix of Goppa code.

Step 2: Generation of homomorphic label HVT:

(1) Set relevant parameters. The user selects an elliptic curve E _p (a,b), and takes its generator as G; sets the public key of the Paillier encryption algorithm as k ₁ =(n,g), and the private key as k ₂ =(λ,μ); choose Pseudorandom permutation function π( ); generates random integers And users need to keep it confidential.

(2) The user codes each data block Generate homomorphic tags $T_i^{\left(j\right)}={\mathrm{E.}}_{k_1}(x_i^{\left(j\right)}+f_i^{\left(j\right)})\mathrm{mod}{N}^2,$ in, Indicates that the public key k ₁ =(n,g) of the Paillier cryptographic algorithm is used for encryption. Therefore, the homomorphic label of each column of data in the encoding matrix is $(T_1^{\left(j\right)},T_2^{\left(j\right)},\&Center\; Dot;\&CenterDot;\&CenterDot;,T_l^{\left(j\right)}).$

Step 3: Remote storage of data:

As shown in Figure 2, the user assigns the homomorphic label It is stored in the jth server S _j together with the data block M ^(j) , and the user stores the private key and random number by himself

2. Challenge-response phase

In this stage, the interactive operation process between the user and the server is shown in Figure 3.

Step 4: User initiates a challenge:

When the user wants to verify whether the server S _j holds data correctly, the user sends a challenge to it: the user generates a challenge chal=(c,k ₃ ) and sends it to the server S _j . Among them, 1≤c≤l, k ₃ is the key of the pseudo-random permutation function π(·), P=yG.

Step 5: The server responds:

(1) Server S _j performs the following calculation for each 1≤r≤c according to the challenge chal:

${\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&pi;</span>}}_{{\mathrm{<span\; class="notranslate">\; k</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; )</span>$

Then according to the obtained i _r , perform the following calculation:

${\mathrm{<span\; class="notranslate">\; T</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{{\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; ic</span>}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}\mathrm{<span\; class="notranslate">\; mod</span>}{\mathrm{<span\; class="notranslate">\; N</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}$

${\mathrm{<span\; class="notranslate">\; \&rho;</span>}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>{{\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; +</span>{{\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; +</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; +</span>{{\mathrm{<span\; class="notranslate">\; f</span>}}_{{\mathrm{<span\; class="notranslate">\; i</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}}}^{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; P</span>}\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; N</span>}$

(2) The server S _j returns the calculated evidence (T ^(j) , ρ ^(j) ) to the user.

Step 6: The user verifies the evidence returned by the server:

(1) After receiving the evidence (T ^(j) ,ρ ^(j) ) returned by the server S _j , the user performs the following operations: use the private key k ₂ =(n,g ⁾ to perform Decrypt to get For every 1≤r≤c compute Then select according to i _r Execute c times ${\mathrm{\&tau;}}^{\left(j\right)}={\mathrm{\&tau;}}^{\left(j\right)}-x_{i_r}^{\left(j\right)}\mathrm{mod}N,$ get ${\mathrm{\&tau;}}^{\left(j\right)}={\mathrm{\&tau;}}^{\left(j\right)}-x_{i_r}^{\left(j\right)}\mathrm{mod}N.$

(2) Verify that n·τ ^(j) ·G=ρ ^(j) , if the equation is established, the verification is successful, indicating that the server S _j correctly holds the user's data; otherwise, it indicates that the data storage of the server S _j has errors .

3. Interactive operation stage

Step 7: Data Recovery

When the user detects a data storage error, the user can request to download all the data from the server, and correct the downloaded data through the parity check matrix P corresponding to the Goppa code generation matrix G ^* , restore the data, and then restore the data The data is relocated to the corresponding location on each server.

Claims (1)

1. A distributed cloud storage data integrity protection method is characterized in that:

the notation and algorithm are explained as follows:

(1) f represents original user data, M is coded data and comprises n multiplied by l data blocks;is the ith block of the jth data vector, which is to be stored to the server S_j.G^*＝(I_(n-r)×(n-r)|P^T) Representing Goppa codesGenerating a matrix, wherein P is a redundancy check block generating matrix; m^*Representing the data block with error stored in the server;

(2) e () and D () are the encryption and decryption algorithms, respectively, of the paillier cipher algorithm, k₁For its public key, k₂The special encryption algorithm is a private key, N is a modulus, and the paillier encryption algorithm meets the property of addition homomorphism;

(3) g is an elliptic curve E_PA generator of (a, b), wherein a large prime number P < N, P ═ yG, P denotes a public parameter in the challenge, and y is a secret parameter generated by the user;

(4) π (-) is a pseudo-random permutation function, i.e., satisfiesWherein k is₃For its key, to determine the position of each randomly drawn data block;

(5)p is a large prime number set in (3) as a secret random number,generated by a pseudorandom generator with a secret key, which is a secret parameter of a user;

the method comprises the following specific steps:

1. initialization phase

Step 1: data blocking and encoding:

(1) a user divides a data file F to be stored in a cloud into l x m blocks, wherein each block is represented as an element GF (p) in a Galois field, and p is a large prime number; the matrix table is used as follows:

(2) the original data is coded by using Goppa code and becomes l multiplied by n blocks after being coded, and the minimum code distance is d_minR +1, i.e. the error detection capability is r, anderror capability is (d)_min-1)/2; the encoded data is:

wherein G is^*Generating a matrix for the Goppa code;

step 2: generation of homomorphic tag HVT:

(1) setting related parameters; the user selects an elliptic curve E_p(a, b), taking the generator as G; setting the public key of the Paillier encryption algorithm as k₁K as the private key (n, g)₂(λ, μ); selecting a pseudo-random permutation function pi (·); generating random integersAnd the user needs to keep his privacy;

(2) user is each data block after being codedGenerating homomorphic tagsWherein,public key k representing the use of the Paillier cryptographic algorithm₁Encrypting (n, g); therefore, the homomorphic label of each column of data in the coding matrix is

And step 3: remote storage of data:

as shown in FIG. 2, the user tags homomorphismAnd a data block M^(j)Stored together in the jth server S_jThe user thenSelf-storing private key and random number

2. Challenge-response phase

And 4, step 4: the user initiates a challenge:

when the user wants to authenticate the server S_jWhen the data is held correctly, the user challenges it: the user generates a challenge chal ═ (c, k)₃) Is sent to the server S_j(ii) a Wherein c is more than or equal to 1 and less than or equal to l, k₃A secret key that is a pseudo-random permutation function pi (·), P ═ yG;

and 5: the server responds:

(1) server S_jFrom the challenge chal, the following calculation is made for each 1 ≦ r ≦ c:

<math> <mrow> <msub> <mi>i</mi> <mi>r</mi> </msub> <mo>=</mo> <msub> <mi>&pi;</mi> <msub> <mi>k</mi> <mn>3</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>r</mi> <mo>)</mo> </mrow> </mrow> </math>

then according to the obtained i_rThe following calculation is performed:

<math> <mrow> <msup> <mi>T</mi> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msup> <mo>&equiv;</mo> <msubsup> <mi>T</mi> <msub> <mi>f</mi> <msub> <mi>i</mi> <mn>1</mn> </msub> </msub> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msubsup> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <msubsup> <mi>T</mi> <msub> <mi>f</mi> <mi>ic</mi> </msub> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msubsup> <mi>mod</mi> <msup> <mi>N</mi> <mn>2</mn> </msup> </mrow> </math>

<math> <mrow> <msup> <mi>&rho;</mi> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msup> <mo>=</mo> <mrow> <mo>(</mo> <msubsup> <mi>f</mi> <msub> <mi>i</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msubsup> <mo>+</mo> <msubsup> <mi>f</mi> <msub> <mi>i</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msubsup> <mo>+</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>+</mo> <msubsup> <mi>f</mi> <msub> <mi>i</mi> <mi>c</mi> </msub> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msubsup> <mo>)</mo> </mrow> <mi>P</mi> <mi>mod</mi> <mi>N</mi> </mrow> </math>

(2) server S_jEvidence to be calculated (T)^(j),ρ^(j)) Returning to the user;

step 6: evidence returned by the user authentication server:

(1) user receives server S_jReturned evidence (T)^(j),ρ^(j)) Then, the following operations are performed: using a private key k₂Pair T (n, g) according to Paillier cipher algorithm^(j)Carry out decryption to obtainFor each 1 ≦ r ≦ c calculationThen according to i_rSelectingIs executed c times <math> <mrow> <msup> <mi>&tau;</mi> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msup> <mo>=</mo> <msup> <mi>&tau;</mi> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msup> <mo>-</mo> <msubsup> <mi>x</mi> <msub> <mi>i</mi> <mi>r</mi> </msub> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msubsup> <mi>mod</mi> <mi>N</mi> <mo>,</mo> </mrow> </math> To obtain <math> <mrow> <msup> <mi>&tau;</mi> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msup> <mo>=</mo> <msup> <mi>&tau;</mi> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msup> <mo>-</mo> <msubsup> <mi>x</mi> <msub> <mi>i</mi> <mi>r</mi> </msub> <mrow> <mo>(</mo> <mi>j</mi> <mo>)</mo> </mrow> </msubsup> <mi>mod</mi> <mi>N</mi> <mo>;</mo> </mrow> </math>

(2) Verification of n.tau^(j)·G＝ρ^(j)If the equality is established, the verification is successful, which indicates the server S_jCorrectly holding the data of the user; otherwise, the server S is indicated_jAn error occurs in data storage;

3. interaction phase

And 7: data recovery

When the user detects that the data storage is wrong, the user requests to download all data from the server, and a matrix G is generated through the Goppa code^*The corresponding check matrix P corrects the downloaded data and recoversAnd then, the recovered data is placed in the corresponding position of each server again.