WO2018232554A1 - Pattern string matching verification method, device, device and storage medium - Google Patents

Abstract

The present invention is applicable to the technical field of computers and discloses a pattern string match verification method, device, apparatus, and storage medium. The method comprises: a cloud server acquiring a pattern string to be matched of a data access terminal, and matching the pattern string with a text string according to a suffix array (S101); the cloud server searching for verification data, corresponding to a match result, according to the text string, a random number set of the text string and the suffix array, a text evidence set, and a suffix evidence set, and sending the match result and the verification data to the data access terminal (S102); the data access terminal verifying the match result, according to the verification data, a text cumulative value and a suffix cumulative value of the text string, and a public key, generating and outputting a verification result, configuring a dynamic verifiable data structure from the text evidence set of a text string, the suffix evidence set, and the text cumulative value and the suffix cumulative value (S103), thereby increasing the efficiency of matching a pattern string, executing dynamic updates of data in pattern string match verification, and improving efficiency of pattern string match verification.

Description

Pattern string matching verification method, device, device and storage medium Technical field

The invention belongs to the technical field of computers, and in particular relates to a method, device, device and storage medium for pattern string matching verification.

Background technique

Pattern string matching means that the specified short string is found in a long string and can be widely used in practical applications such as intrusion detection, firewall filtering, database query and biometric calculation. In practical applications, due to the limited local computing resources and the rapid development of cloud computing, enterprises or individuals usually choose to outsource pattern string matching to cloud computing to save manpower and resources.

The method of outsourcing pattern string matching to cloud computing faces the problem of result authenticity and data update. When receiving the query result returned by the cloud server, the user cannot determine whether the matching result returned by the cloud server is true, when the cloud server is required to be updated. When the data is available, the user cannot determine if the cloud server has updated its own data.

The current solution is mainly that the cloud server generates verification evidence for verifying the authenticity of the matching result while calculating the matching result, and the user can use the pattern string and the evidence to verify whether the result returned by the cloud server is correct, that is, whether it is true. However, the existing solutions of this type have low verification efficiency and lack of dynamic update functions. For example, the universal solution for verifiable data structures proposed by Martel et al. and the verifiable pattern string matching SuffixTree proposed by Papadopoulos et al. The suffix tree scheme does not support efficient data update functions, and the verification result of matching results is not high. Among them, Papadopoulos et al.'s verifiable pattern string matching SuffixTree scheme has excellent search performance and evidence communication overhead, supports public verification, but does not support efficient data dynamic update, and only adopts data segmentation processing to reduce data update band. The refactoring cost comes from, and at the same time, the device side of the user needs to store a large amount of public key data during verification, and the verification efficiency is not high.

Summary of the invention

The object of the present invention is to provide a mode string matching verification method, device, device and storage medium, which aims to solve the problem that the effective verification of the mode string matching verification is not efficient because the prior art cannot provide an effective mode string matching verification method. And the problem of dynamic update of data is not possible.

In one aspect, the present invention provides a mode string matching verification method, the method comprising the following steps:

When the cloud server receives the pattern string matching verification request of the data access end, the cloud server acquires the to-be-matched pattern string sent by the data access end, and matches the to-be-matched pattern string with the pre-stored text string according to the pre-stored suffix array. Matching result

The cloud server searches for the verification evidence corresponding to the matching result according to the text string, the suffix array, and the pre-stored random number set of the text string, the text proof set, and the suffix proof set, and the matching result and the verification result. Evidence is sent to the data access end;

The data access end verifies the matching result according to the verification evidence, the text accumulated value and the suffix accumulated value of the text string stored in advance, and a pre-stored public key, and generates and outputs a verification result, The text proof set, the suffix proof set, the text accumulating value and the suffix accumulating value of the text string constitute a dynamic verifiable data structure obtained by the data possessor preprocessing the text string.

In another aspect, the present invention provides a mode string matching verification apparatus, the apparatus comprising:

And the mode string matching unit is configured to: when the cloud server receives the mode string matching verification request of the data access end, acquire the to-be-matched mode string sent by the data access end, and store the to-be-matched mode string and the pre-storage according to the pre-stored suffix array The text string is matched to obtain a matching result;

An evidence search unit, configured to search, according to the text string, the suffix array, the pre-stored random number set of the text string, the text proof set, and the suffix proof set, the verification evidence corresponding to the matching result, The matching result and verification evidence are sent to the data access end;

a matching verification unit, configured to: verify, according to the verification evidence, a text accumulated value and a suffix accumulated value of the text string stored in advance, and a pre-stored public key, verify the matching result, generate and Outputting a verification result, a text proof set of the text string, a suffix proof set, The text accumulated value and the suffix accumulated value constitute a dynamic verifiable data structure obtained by the data owner preprocessing the text string.

In another aspect, the present invention also provides a mode string matching verification device comprising a memory, a processor, and a computer program stored in the memory and operable on the processor, the processor executing the computer The program implements the steps as described in one of the pattern string matching verification methods described above.

In another aspect, the present invention provides a computer readable storage medium storing a computer program, the computer program being executed by a processor to implement the mode string matching verification method as described above A step of.

In the present invention, when the cloud server receives the pattern string matching verification request of the data access end, the cloud server acquires the to-be-matched pattern string sent by the data access end, and matches the pattern string to be matched with the pre-stored text string according to the pre-stored suffix array. Perform matching, obtain matching results, and according to the text string, the suffix array and the pre-stored random number set of the text string, the text proof set, the suffix proof set, find the verification evidence corresponding to the matching result, and the cloud server sends the matching result and the verification evidence to The data access end verifies the matching result according to the verification evidence, the text accumulated value of the pre-stored text string and the accumulated value of the suffix, and the pre-stored public key, and generates and outputs the verification result, wherein the text of the text string The verification set, the suffix proof set, the text accumulating value and the suffix accumulating value constitute a dynamic verifiable data structure obtained by preprocessing the text string by the data possession end, thereby effectively improving the search index data structure by using the suffix array as the pattern string matching. The efficiency of pattern string matching, Data access terminal of the storage of a fixed size can be realized where the user public key matching verification, verification efficiency effectively mentioned pattern matching, in addition, dynamic verifiable data structure enables dynamic update of the pattern matching verification.

DRAWINGS

1 is a flowchart of an implementation of a mode string matching verification method according to Embodiment 1 of the present invention;

2 is a diagram showing an example of a suffix array generation process in a pattern string matching verification method according to Embodiment 1 of the present invention;

3 is a schematic structural diagram of a mode string matching verification apparatus according to Embodiment 2 of the present invention;

4 is a schematic diagram of a preferred structure of a mode string matching verification apparatus according to Embodiment 2 of the present invention;

FIG. 5 is a schematic structural diagram of a mode string matching apparatus according to Embodiment 3 of the present invention.

Detailed ways

The present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It is understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention.

The specific implementation of the present invention is described in detail below in conjunction with specific embodiments:

Embodiment 1:

FIG. 1 is a flowchart showing an implementation process of a mode string matching verification method according to Embodiment 1 of the present invention. For convenience of description, only parts related to the embodiment of the present invention are shown, which are as follows:

In step S101, when the cloud server receives the mode string matching verification request of the data access end, the cloud server acquires the to-be-matched pattern string sent by the data access end, and matches the to-be-matched pattern string with the pre-stored text string according to the pre-stored suffix array. Get the match.

时，获取文本串所有后缀SFi，将所有后缀按照字符大小顺序进行排序，将排序后的后缀在文本串中的开始字符位置存储 在后缀数组SA[i]中。在匹配的过程中，根据后缀数组从文本串的相应位置处获取子串与待匹配模式串进行匹配，从而提高了云服务器中模式串匹配的效率。In the embodiment of the present invention, the mode string matching verification may include three execution entities: a cloud server, a data access end, and a data possession end, wherein the data access end may be the user's end, and the user hands over the pattern string matching work to the cloud. Calculated, the data owner can be a third-party server trusted by the user. When the user needs to perform the mode string matching and verify the result of the mode string matching, the data access end may send the mode string matching verification request and the to-be-matched mode string to the cloud server. The cloud server obtains the to-be-matched pattern string when receiving the pattern string matching verification request, and matches the to-be-matched pattern string with the pre-stored text string in the cloud server according to the suffix array. The suffix array is used to store the position of the start character of all suffixes in the text string in the text string. For the sake of brevity, the position is referred to as the position of the suffix in the text string, for example, as shown in FIG. 2, when the text string is

At the same time, all suffixes SFi of the text string are obtained, all suffixes are sorted in order of character size, and the starting suffixes of the sorted suffixes in the text string are stored in the suffix array SA[i]. In the matching process, the substring is obtained from the corresponding position of the text string according to the suffix array to match the pattern string to be matched, thereby improving the efficiency of pattern string matching in the cloud server.

Preferably, before the matching verification of the mode string is performed, the data owner needs to perform data processing, and the processed data is separately sent to the cloud server and the data access end to improve the efficiency of the matching verification. The step of data processing by the data owner may include:

(1) The data owner may first generate a public-private key pair according to the preset security parameters, and publicize the public key in the public-private key pair.

Specifically, the public-private key pair of the RSA Accumulator may be generated according to the security parameter, and the public-private key pair may include a private key and a public key, and the private key is sk={p, q, φ(N)}. The key is pk={N=pq,g← _R QR _N , PG(·)}, where p and q are large prime numbers, φ(N) is an Euler function of N, and φ(N)=(p-1 (q-1), QR is the quadratic residual group of modulo N, g is a random element in the quadratic residual group of modulo N, and PG(·) is a pre-defined prime number generating function of the data possession end.

(2) The data owner generates a suffix array and a random number set of the text string according to the text string.

Specifically, the process of generating the suffix array of the text string by the data owner may be as shown in FIG. 2 . In addition, a random number r _{i is} bound to each character T[i] of the text string, thereby obtaining a random number set R={r _i |1≤i≤n} of the text string, where n is the length of the text string.

(3) The data owner generates a dynamic verifiable data structure according to the text string, the suffix array, the random number set of the text string, the random number set of the suffix array, and the public key.

计算每个文本素数的文本证明

得到文本串的文本证明集合

同样地，生成后缀元组s_j＝('neb',T[SA[j]],r_SA[j],T[SA[j+1]],r_SA[j+1])，计算每个后缀元组对应的后缀素数ps_j＝PG(s_j)，得到后缀素数集合PS＝{ps_j,1≤j＜n}，计算文本串的后 缀累加值

计算每个后缀素数的后缀证明

获得文本串的后缀证明集合

Specifically, performing pairwise association on all adjacent characters in the text string to obtain a corresponding text tuple t _i =<T[i], r _i , T[i+1], r _i+1 >, and calculating each The text prime of the text tuple pt _i = PG(t _i ), obtain the text prime number set PT={pt _i , 1≤i<n} of the text string, and calculate the text accumulated value of the text prime number set (for convenience of description, a text accumulating value called a text string)

Calculate text proof of each text prime

Get a text proof collection of text strings

Similarly, generate a suffix tuple s _j = ('neb', T[SA[j]], r _SA[j] , T[SA[j+1]], r _SA[j+1] ), calculate each The suffix tuple corresponds to the suffix prime number ps _j = PG(s _j ), and obtains the suffix prime number set PS={ps _j , 1≤j<n}, and calculates the suffix accumulated value of the text string.

Calculate the suffix proof of each suffix prime number

Get the suffix proof set of the text string

In the embodiment of the present invention, the text proof set, the suffix proof set, the text accumulated value and the suffix accumulated value of the text string constitute a dynamic verifiable data structure, so as to implement dynamic update of data in the pattern string matching query through the dynamically verifiable data structure. . The data owner sends the text string, the suffix array, and the random number set of the text string, the text proof set, and the suffix proof set to the cloud server, and sends the text accumulated value and the suffix accumulated value of the text string to the data access end, and the data possession end Retains the text string, the suffix array, and the random number set of the text string, the text accumulated value, and the suffix accumulated value.

In step S102, the cloud server searches for the verification evidence corresponding to the matching result according to the text string, the suffix array, the pre-stored random number set of the text string, the text proof set, and the suffix proof set, and sends the matching result and the verification evidence to the data access. end.

从而由该子串的随机数集合、文本证明集合构成匹配成功的验证证据。In the embodiment of the present invention, the verification evidence can be used by the data access end to verify whether the matching result of the cloud server is correct. When the matching result is that the matching is successful, the cloud server may obtain, from the suffix array, the location i of the matching pattern string to be successfully matched in the text string, according to which the substring P= in the text string that matches the to-be-matched pattern string is obtained. T[i]T[i+1]...T[i+m-1], T is a text string, and m is the length of the pattern string to be matched. Then, the random number set R'={r' _k =r _i+k-1 , 1≤k≤m} of the substring can be obtained from the random number set R of the text string, from the text proof set of the text string Find all text proofs for the substring, and generate a text proof set for the substring

Therefore, the set of random numbers and the set of text proofs of the substring constitute verification evidence of successful matching.

In the embodiment of the present invention, when the matching result is a matching failure, the first suffix and the second suffix satisfying the preset condition may be obtained according to the suffix array, and the preset condition may be SF _SA[j] <P<SF _{SA[j+ 1]} , SF _SA[j] is the first suffix, and SF _SA[j+1] is the second suffix. Therefore, it is necessary to find evidence for verifying that the first suffix is smaller than the to-be-matched mode string, the second suffix is greater than the to-be-matched mode string, and the first suffix is adjacent to the second suffix.

的随机数集合

文本证明集合

Specifically, when the identifier used to verify that the first suffix is smaller than the to-be-matched mode string is obtained, the length of the common prefix of the first suffix and the to-be-matched mode string, m ₁ =lcp(P, SF _SA[j] ), and A suffix character c ₁ =T[SA[j]+m ₁ ], find the common prefix in the random number set of the text string, the text proof set

Random number set

Text proof collection

字符c₂＝T[SA[j+1]+m₂]、公共前缀T[SA[j+1]]T[SA[j+1]+1]...T[SA[j+1]+m₂]的随机数集合

文本证明集合

Similarly, when searching for evidence for verifying that the first suffix is smaller than the pattern string to be matched, the length of the common prefix of the second suffix and the pattern string to be matched can be obtained.

The character c ₂ =T[SA[j+1]+m ₂ ], the common prefix T[SA[j+1]]T[SA[j+1]+1]...T[SA[j+1] +m ₂ ] random number set

Text proof collection

该后缀证明结合上对应的随机数和字符即可验证第一后缀和第二后缀在后缀数组的排序上是否相邻。将这些数据组合构成匹配失败的验证证据Γ＝{m₁,m₂,c₁,c₂,R¹,WT¹,R²,WT²,ws'}，将匹配结果和匹配失败的验证证据发送给数据访问端。Specifically, when searching for evidence for verifying that the first suffix is adjacent to the second suffix, obtaining a corresponding suffix certificate in the suffix proof set of the text string, that is,

The suffix proves that the first suffix and the second suffix are adjacent to each other in the order of the suffix array by combining the corresponding random number and character. Combine these data to form the proof of failure of the matching failure Γ={m ₁ , m ₂ , c ₁ , c ₂ , R ¹ , WT ¹ , R ² , WT ² , ws'}, and the matching result and the verification evidence of the matching failure Send to the data access side.

In step S103, the data access terminal verifies the matching result according to the verification evidence, the text accumulated value of the pre-stored text string and the suffix accumulated value, and the pre-stored public key, and generates and outputs the verification result.

即验证该公式中等号两端是否相等。当所有文本素数都被验证正确时，认为云服务器返回的匹配成功的匹配结果正确。In the embodiment of the present invention, when the matching result is successful, the corresponding text tuple t' _k =(P[k], r' _{k is first} calculated according to the random number set in the verification evidence of the matching success. , P[k+1], r' _k+1 ), 1≤k<m, calculate the text prime number pt' _k = PG(t' _k ) corresponding to these text tuples, and verify the set according to the text proof in the verification evidence Whether all of these text primes are correct, the verification formula is

That is, verify that the middle of the formula is equal. When all the text primes are verified to be correct, it is considered that the matching result returned by the cloud server is correct.

In the embodiment of the present invention, when the matching result is a matching failure, it may first determine whether the character c ₁ in the verification evidence of the first matching failure is less than P[m ₁ +1], and P[m ₂ + 1) Whether it is smaller than the character c ₂ , verify whether the first suffix is smaller than the pattern string to be matched, and whether the pattern string to be matched is smaller than the second suffix, and then verify whether the first suffix and the second suffix are correct.

1≤k＜m₁，当k＝m₁时对应的文本元组为

进而计算这些文本元组的文本素数

根据这些文本元组的文本素数、匹配失败的验证证据中的WT¹和数据访问端预先存储的文本累加值，验证第一后缀是否正确，验证公式为

即验证该公式中等号两端是否相等，若都相等，则可确定第一后缀正确。Specifically, when verifying whether the first suffix is correct, the corresponding text tuple may be generated according to the random number set R ¹ of the common prefix of the first suffix and the to-be-matched pattern string.

1≤k<m ₁ , when k=m ₁ the corresponding text tuple is

Then calculate the text primes of these text tuples

According to the text prime of the text tuple, the WT ¹ in the verification evidence of the matching failure, and the text accumulated value pre-stored by the data access end, verify whether the first suffix is correct, and the verification formula is

That is to verify whether the two ends of the formula are equal. If they are equal, the first suffix can be determined to be correct.

1≤k＜m₂，当k＝m₂时对应的文本元组为

进而计算这些文本元组的文本素数

根据这些文本元组的文本素数、匹配失败的验证证据中的WT²和数据访问端预先存储的文本累加值，验证第二后缀是否正确，验证公式为

即验证该公式中等号两端是否相等，若都相等，则可确定第二后缀正确。Similarly, when verifying whether the second suffix is correct, the corresponding text tuple may be generated by the second suffix and the random number set R ² of the common prefix of the pattern string to be matched.

1≤k<m ₂ , when k=m ₂ the corresponding text tuple is

Then calculate the text primes of these text tuples

According to the text prime of the text tuple, the WT ² in the verification evidence of the matching failure, and the text accumulated value pre-stored by the data access end, verify whether the second suffix is correct, and the verification formula is

That is, it is verified whether the two ends of the formula are equal, and if they are equal, it can be determined that the second suffix is correct.

计算该后缀元组的后缀素数ps'＝PG(s')，最后通过匹配失败的验证证据中的后缀证明对该后缀素数进行验证。In the embodiment of the present invention, it is also required to verify whether the first suffix and the second suffix are consecutive in the order of the suffix array. Specifically, when the length of the common prefix of the first suffix and the to-be-matched mode string is zero, the first character hc ₁ of the first suffix is the character c ₁ in the verification evidence of the failed match, otherwise the character P[1], when When the length of the common prefix of the second suffix and the pattern string to be matched is zero, the first character hc ₂ of the second suffix is the character c ₂ in the verification evidence of the failed match, otherwise the character P[1], and the suffix tuple is generated.

The suffix prime number ps'=PG(s') of the suffix tuple is calculated, and finally the suffix prime number is verified by the suffix proof in the verification evidence of the failed match.

In the embodiment of the present invention, when all the verifications in the matching failure are correct, it is determined that the matching result of the matching failure returned by the cloud server is correct. In the verification process of the pattern string matching result, the power operation of the large integer is used, which reduces the calculation amount of the matching process, and only needs to store the fixed-size public key and combine the mode. The string, the random number set, and the proof set can be verified, simplifying the verification step of the data access end.

Preferably, when the data possession end receives the data update instruction (including the insertion, deletion, and/or replacement update instruction) of the data access end, respectively, according to the character string to be inserted, the character string to be deleted in the text string, and/or Or the string to be replaced, and the public key, the text string of the data owner, the suffix array, and the random number set of the text string, the text accumulated value, the suffix accumulated value are updated, and the auxiliary information for the cloud server update is generated. . After the data ownership end is updated, the data owner sends the text accumulation value and the suffix accumulated value of the updated text string to the data access terminal, and sends the auxiliary information to the cloud server, thereby realizing dynamic update of the data of the data owner and the data. The computational overhead of owning end-of-data updates is small.

As an example, when the data owner receives the data insertion instruction, the insertion position in the text string, the length of the string to be inserted, and the character string to be inserted are obtained, and the following operations are performed:

T[i,j]＝T[i]T[i+1]...T[j]，i为插入位置。(1) Insert the string s to be inserted into the text string: T'=T[1:i-1]||s||T[i:n], where T' is obtained after inserting the string Text string,

T[i,j]=T[i]T[i+1]...T[j], where i is the insertion position.

(2) Add the random number corresponding to the character in the string to be inserted in the random number set R of the text string: R'={r ₁ ... r _i-1 , r' ₁ ... r' _l , r _i ... r _n }, where r' ₁ ... r' _l is a random number corresponding to the character in the string s to be inserted added to the random number set R, and l is the string s to be inserted length.

(3) Calculate a new prime number for the updated text string. The formula for calculating the new prime number can be: pt' ₀ = PG(T[i-1], r _i-1 , s[1], r' ₁ ), Pt' _i = PG(s[i],r' _i ,s[i+1],r' _i+1 ),pt' _l =PG(s[l],r' _l ,T[i],r _i ), where 1 ≤ _i < 1, aggregated into TIS = {pt' _j | 0 ≤ _j ≤ l}.

(4) Delete the prime number pt _i-1 associated with <T[i-1], T[i]>, assemble into TDS={pt _i-1 }, and obtain auxiliary information AuxData={r' ₁ ,... ,r' _l }.

其中，I_t＝∏_pt∈TISpt，D_t＝∏_pt∈TDSpt。文本辅助累加值的计算公式为：

其中，wit为witness 的简写，用来表示数据的辅助作用。(5) updating the text accumulated value of the text string and calculating the text auxiliary accumulated value of the text string, and the formula for updating the text accumulated value of the text string may be:

Where I _t = ∏ pt _{∈ TIS} pt, D _t = ∏ pt _{∈ TDS} pt. The text-assisted accumulated value is calculated as:

Among them, wit is shorthand for witness, used to represent the auxiliary role of data.

(6) generating an suffix array SA' of the updated text string T', comparing the difference between the suffix array SA of the text string before the update and the updated suffix array SA', determining the prime set SDS to be deleted, and Calculate the set of prime numbers SIS that need to be added.

其中，I_s＝∏_ps∈SISps，D_s＝∏_ps∈SDSps。后缀辅助累加值的计算公式为：

获得辅助信息

(7) Update the suffix accumulated value of the text string and calculate the suffix auxiliary accumulated value. The update formula for the suffix accumulated value is:

Where I _s = ∏ ps _{∈ SIS} ps, D _s = ∏ ps _{∈ SDS} ps. The formula for calculating the suffix auxiliary accumulated value is:

Access to auxiliary information

Preferably, when the cloud server receives the data update instruction, according to the character string to be inserted, the character string to be deleted in the text string, and/or the character string to be replaced, and the public key and the auxiliary information, the cloud server is pre- The stored text string, the suffix array, and the random number set of the text string, the text proof set, and the suffix proof set are updated to implement dynamic update of the cloud server data.

As an example, when the cloud server receives the data insertion instruction, it acquires the insertion position in the text string, the length of the character string to be inserted, and the character string to be inserted, and performs the following operations:

T[i,j]＝T[i]T[i+1]...T[j]，i为插入位置。(1) Insert the string s to be inserted into the text string: T'=T[1:i-1]||s||T[i:n], where T' is obtained after inserting the string Text string,

T[i,j]=T[i]T[i+1]...T[j], where i is the insertion position.

(2) Add the random number corresponding to the character in the string to be inserted in the random number set R of the text string: R'={r ₁ ... r _i-1 , r' ₁ ... r' _l , r _i ... r _n }, where r' ₁ ... r' _l is a random number corresponding to the character in the string s to be inserted added to the random number set R, and l is the string s to be inserted length.

(3) Calculate a new prime number for the updated text string. The formula for calculating the new prime number can be: pt' ₀ = PG(T[i-1], r _i-1 , s[1], r' ₁ ), Pt' _i = PG(s[i],r' _i ,s[i+1],r' _i+1 ),pt' _l =PG(s[l],r' _l ,T[i],r _i ), where 1 ≤ _i < 1, aggregated into TIS = {pt' _j | 0 ≤ _j ≤ l}.

(4) Delete the prime numbers pt _i-1 associated with <T[i-1], T[i]>, and assemble them into TDS={pt _i-1 }.

计算新的文本证明

并添加到WT中。根据文本证明集合WT中剩余的素数pt，对对应的文本证明进行更新：

其中，a*pt+b*D_t＝1。最后得到新的文本证明集合WT'。(5) Delete the text proof wt _pt corresponding to each prime number pt∈TDS from the text proof set WT of the text string. For each new prime pt'∈TIS, calculate

Calculate a new text proof

And added to the WT. Update the corresponding text proof according to the remaining prime number pt in the text proof set WT:

Where a*pt+b*D _t =1. Finally, a new text proof set WT' is obtained.

(6) generating an suffix array SA' of the updated text string T', comparing the difference between the suffix array SA of the text string before the update and the updated suffix array SA', determining the prime set SDS to be deleted, and Calculate the set of prime numbers SIS that need to be added.

并添加到后缀证明集合WS中，其中，I'_s＝∏_ps∈SIS-ps'ps。根据后缀证明集合WS中剩余的素数ps，对对应的后缀证明进行更新：

其中，a*pt+b*D_t＝1。最后得到新的后缀证明集合WS'。(7) Delete the ws _ps corresponding to each prime number ps∈SDS from the WS in the suffix proof set of the text string T, and calculate a new suffix proof for each prime number ps'∈SIS

And added to the suffix proof set WS, where I _'s = ∏ _{ps ∈ SIS-ps'} ps. The corresponding suffix proof is updated according to the remaining prime number ps in the set WS according to the suffix:

Where a*pt+b*D _t =1. Finally, a new suffix proof set WS' is obtained.

In the embodiment of the present invention, the cloud server, the data access end, and the data Owner cooperate to complete the matching verification of the pattern string, and the suffix array is used as the index of the cloud server matching process in the matching verification process, thereby improving the efficiency of the pattern string matching. The textual proof set and the suffix proof set in the dynamic verifiable data structure complete the verification of the evidence, and the verification result is completed by the text accumulating value and the suffix accumulating value in the dynamically verifiable data structure, and the data access end stores the fixed size. The public key makes the verification more concise. The dynamic verifiable structure generated by the data owner realizes the dynamic update of data on the data owner and the cloud server, and effectively reduces the calculation overhead of the data owner and the communication overhead between the data owner and the cloud server in the update process.

Embodiment 2:

FIG. 3 is a diagram showing the structure of a mode string matching verification apparatus according to Embodiment 2 of the present invention. For the convenience of description, only parts related to the embodiment of the present invention are shown, including:

The mode string matching unit 31 is configured to: when the cloud server receives the mode string matching verification request of the data access end, obtain the to-be-matched mode string sent by the data access end, and wait for the suffix array according to the pre-stored The matching pattern string is matched with the pre-stored text string to obtain a matching result.

In the embodiment of the present invention, when the cloud server receives the pattern string matching verification request, the cloud server acquires the to-be-matched pattern string, and matches the to-be-matched pattern string with the pre-stored text string in the cloud server according to the suffix array. In the matching process, the substring is obtained from the corresponding position of the text string according to the suffix array to match the pattern string to be matched, thereby improving the efficiency of pattern string matching in the cloud server.

The evidence searching unit 32 is configured to: the cloud server searches for the verification evidence corresponding to the matching result according to the text string, the suffix array, the random number set of the pre-stored text string, the text proof set, and the suffix proof set, and sends the matching result and the verification evidence to the verification evidence. Data access side.

从而由该子串的随机数集合、文本证明集合构成匹配成功的验证证据。In the embodiment of the present invention, when the matching result is that the matching is successful, the cloud server may obtain, from the suffix array, a position where the matching pattern string matches successfully in the text string, and according to the position, the text string can be matched with the to-be-matched pattern string. The successful substring P=T[i]T[i+1]...T[i+m-1], T is a text string, and m is the length of the pattern string to be matched. Then, the random number set R'={r' _k =r _i+k-1 , 1≤k≤m} of the substring can be obtained from the random number set R of the text string, from the text proof set of the text string Find all text proofs for the substring, and generate a text proof set for the substring

Therefore, the set of random numbers and the set of text proofs of the substring constitute verification evidence of successful matching.

In the embodiment of the present invention, when the matching result is a matching failure, the first suffix and the second suffix satisfying the preset condition may be obtained according to the suffix array, and the preset condition may be SF _SA[j] <P<SF _{SA[j+ 1]} , SF _SA[j] is the first suffix, and SF _SA[j+1] is the second suffix. Therefore, it is necessary to find evidence for verifying that the first suffix is smaller than the to-be-matched mode string, the second suffix is greater than the to-be-matched mode string, and the first suffix is adjacent to the second suffix.

文本证明集合

Specifically, when the identifier used to verify that the first suffix is smaller than the to-be-matched mode string is obtained, the length of the common prefix of the first suffix and the to-be-matched mode string, m ₁ =lcp(P, SF _SA[j] ), and A suffix character c ₁ =T[SA[j]+m ₁ ], find the common prefix T[SA[j]]T[SA[j]+1] in the random number set of the text string and the text proof set. a set of random numbers for ...T[SA[j]+m ₁ ]

Text proof collection

文本证明集合

Similarly, when searching for evidence for verifying that the first suffix is smaller than the pattern string to be matched, the length of the common prefix of the second suffix and the pattern string to be matched, m ₂ = lcp (P, SF _SA[j+1] ), The character c ₂ =T[SA[j+1]+m ₂ ], the common prefix T[SA[j+1]]T[SA[j+1]+1]...T[SA[j+1] +m ₂ ] random number set

Text proof collection

该后缀证明结合上对应的随机数和字符即可验证第一后缀和第二后缀在后缀数组的排序上是否相邻。将这些数据组合构成匹配失败的验证证据Γ＝{m₁,m₂,c₁,c₂,R¹,WT¹,R²,WT²,ws'}，将匹配结果和匹配失败的验证证据发送给数据访问端。Specifically, when searching for evidence for verifying that the first suffix is adjacent to the second suffix, obtaining a corresponding suffix certificate in the suffix proof set of the text string, that is,

The suffix proves that the first suffix and the second suffix are adjacent to each other in the order of the suffix array by combining the corresponding random number and character. Combine these data to form the proof of failure of the matching failure Γ={m ₁ , m ₂ , c ₁ , c ₂ , R ¹ , WT ¹ , R ² , WT ² , ws'}, and the matching result and the verification evidence of the matching failure Send to the data access side.

The matching verification unit 33 is configured to verify, by the data access terminal, the verification result according to the verification evidence, the text accumulated value and the suffix accumulated value of the pre-stored text string, and the pre-stored public key, and generate and output the verification result.

即验证该公式中等号两端是否相等。当所有文本素数都被验证正确时，认为云服务器返回的匹配成功的匹配结果正确。In the embodiment of the present invention, when the matching result is successful, the corresponding text tuple t' _k =(P[k], r' _{k is first} calculated according to the random number set in the verification evidence of the matching success. , P[k+1], r' _k+1 ), 1≤k<m, calculate the text prime number pt' _k = PG(t' _k ) corresponding to these text tuples, and verify the set according to the text proof in the verification evidence Whether all of these text primes are correct, the verification formula is

That is, verify that the middle of the formula is equal. When all the text primes are verified to be correct, it is considered that the matching result returned by the cloud server is correct.

In the embodiment of the present invention, when the matching result is a matching failure, it may first determine whether the character c ₁ in the verification evidence of the first matching failure is less than P[m ₁ +1], and P[m ₂ + 1] Whether it is smaller than the character c ₂ , whether the first suffix is smaller than the pattern string to be matched, and whether the pattern string to be matched is smaller than the second suffix. Then verify whether the first suffix and the second suffix are correct.

1≤k＜m₁，当k＝m₁时对应的文本元组为

进而计算这些文本 元组的文本素数

根据这些文本元组的文本素数、匹配失败的验证证据中的WT1和数据访问端预先存储的文本累加值，验证第一后缀是否正确，验证公式为

即验证该公式中等号两端是否相等，若都相等，则可确定第一后缀正确。Specifically, when verifying whether the first suffix is correct, the corresponding text tuple may be generated according to the random number set R ¹ of the common prefix of the first suffix and the to-be-matched pattern string.

1≤k<m ₁ , when k=m ₁ the corresponding text tuple is

Then calculate the text primes of these text tuples

According to the text prime of the text tuple, the WT1 in the verification evidence of the matching failure, and the text accumulated value pre-stored by the data access end, verify whether the first suffix is correct, and the verification formula is

That is to verify whether the two ends of the formula are equal. If they are equal, the first suffix can be determined to be correct.

1≤k＜m₂，当k＝m₂时对应的文本元组为

进而计算这些文本元组的文本素数

根据这些文本元组的文本素数、匹配失败的验证证据中的WT²和数据访问端预先存储的文本累加值，验证第二后缀是否正确，验证公式为

即验证该公式中等号两端是否相等，若都相等，则可确定第二后缀正确。Similarly, when verifying whether the second suffix is correct, the corresponding text tuple may be generated by the second suffix and the random number set R ² of the common prefix of the pattern string to be matched.

1≤k<m ₂ , when k=m ₂ the corresponding text tuple is

Then calculate the text primes of these text tuples

According to the text prime of the text tuple, the WT ² in the verification evidence of the matching failure, and the text accumulated value pre-stored by the data access end, verify whether the second suffix is correct, and the verification formula is

That is, it is verified whether the two ends of the formula are equal, and if they are equal, it can be determined that the second suffix is correct.

计算该后缀元组的后缀素数ps'＝PG(s')，最后通过匹配失败的验证证据中的后缀证明对该后缀素数进行验证。In the embodiment of the present invention, it is also required to verify whether the first suffix and the second suffix are consecutive in the order of the suffix array. Specifically, when the length of the common prefix of the first suffix and the to-be-matched mode string is zero, the first character hc ₁ of the first suffix is the character c ₁ in the verification evidence of the failed match, otherwise the character P[1], when When the length of the common prefix of the second suffix and the pattern string to be matched is zero, the first character hc ₂ of the second suffix is the character c ₂ in the verification evidence of the failed match, otherwise the character P[1], and the suffix tuple is generated.

The suffix prime number ps'=PG(s') of the suffix tuple is calculated, and finally the suffix prime number is verified by the suffix proof in the verification evidence of the failed match.

In the embodiment of the present invention, when all the verifications in the matching failure are correct, it is determined that the matching result of the matching failure returned by the cloud server is correct. In the verification process of the pattern string matching result, the power operation of the large integer is used, which reduces the calculation amount of the matching process, and only needs to store the fixed-size public key, and combines the pattern string, the random number set, and the proof set. Verification simplifies the verification steps for the data access side.

Preferably, as shown in FIG. 4, the pattern string matching verification apparatus further includes a key generation unit 41, a verifiable data generation unit 42, and a data transmission unit 43, wherein:

The key generation unit 41 is configured to generate a public and private key password according to the preset security parameter by the data owner. Yes, publicize the public key of the public-private key pair;

The verifiable data generating unit 42 is configured to generate a suffix array according to the text string, bind a random number to each character of the text string, generate a random number set of the text string, according to the text string, the random number set of the text string, the suffix array, a set of random numbers and a public key of the suffix array to generate a dynamically verifiable data structure;

The data sending unit 43 is configured to send the text string, the suffix array, and the random number set of the text string, the text proof set, and the suffix proof set to the cloud server, and send the text accumulated value and the suffix accumulated value of the text string to the data possession end. Data access side.

In the embodiment of the present invention, before the matching verification of the mode string is performed, the data possession end needs to perform data processing, and the processed data is separately sent to the cloud server and the data access end to improve the efficiency of the matching verification. The step of performing data processing on the data end may include:

(1) The data owner may first generate a public-private key pair according to the preset security parameters, and publicize the public key in the public-private key pair.

Specifically, the public-private key pair of the RSA Accumulator may be generated according to the security parameter, and the public-private key pair may include a private key and a public key, and the private key is sk={p, q, φ(N)}. The key is pk={N=pq,g← _R QR _N , PG(·)}, where p and q are large prime numbers, φ(N) is an Euler function of N, and φ(N)=(p-1 (q-1), QR is the quadratic residual group of modulo N, g is a random element in the quadratic residual group of modulo N, and PG(·) is a pre-defined prime number generating function of the data possession end.

(2) The data owner generates a suffix array and a random number set of the text string according to the text string.

Specifically, the process of generating the suffix array of the text string by the data owner may be as shown in FIG. 2 . In addition, a random number r _{i is} bound to each character T[i] of the text string, thereby obtaining a random number set R={r _i |1≤i≤n} of the text string, where n is the length of the text string.

(3) The data owner generates a dynamic verifiable data structure according to the text string, the suffix array, the random number set of the text string, the random number set of the suffix array, and the public key.

计算每个文本素数的文本证明

得到文本串的文本证明集合

同样地，生成后缀元组s_j＝('neb',T[SA[j]],r_SA[j],T[SA[j+1]],r_SA[j+1])，计算每个后缀元组对应的后缀素数ps_j＝PG(s_j)，得到后缀素数集合PS＝{ps_j,1≤j＜n}，计算文本串的后缀累加值

计算每个后缀素数的后缀证明

获得文本串的后缀证明集合

Specifically, performing a pairwise association on all adjacent characters in the text string to obtain a corresponding text tuple t _i =<T[i], r _i , T[i+1], r _i+1 >, and calculating each The text prime of the text tuple pt _i = PG(t _i ), obtain the text prime number set PT={pt _i , 1≤i<n} of the text string, and calculate the text accumulated value of the text prime number set (for convenience of description, a text accumulating value called a text string)

Calculate text proof of each text prime

Get a text proof collection of text strings

Similarly, generate a suffix tuple s _j = ('neb', T[SA[j]], r _SA[j] , T[SA[j+1]], r _SA[j+1] ), calculate each The suffix tuple corresponds to the suffix prime number ps _j = PG(s _j ), and the suffix prime number set PS={ps _j , 1≤j<n} is obtained, and the suffix accumulated value of the text string is calculated.

Calculate the suffix proof of each suffix prime number

Get the suffix proof set of the text string

In the embodiment of the present invention, the text proof set, the suffix proof set, the text accumulated value and the suffix accumulated value of the text string constitute a dynamic verifiable data structure, so as to implement dynamic update of data in the pattern string matching query through the dynamically verifiable data structure. . The data owner sends the text string, the suffix array, and the random number set of the text string, the text proof set, and the suffix proof set to the cloud server, and sends the text accumulated value and the suffix accumulated value of the text string to the data access end, and the data possession end Retains the text string, the suffix array, and the random number set of the text string, the text accumulated value, and the suffix accumulated value.

Preferably, the mode string matching verification apparatus further includes a data side updating unit 47, an update data transmitting unit 48, and a cloud updating unit 49, wherein:

The data end updating unit 47 is configured to: when the data owner receives the update instruction for inserting, deleting, and/or replacing, according to the character string to be inserted, the character string to be deleted in the text string, and/or the replacement a string, and a public key, updating the text string, the suffix array, and the random number set of the text string, the text accumulated value, and the suffix accumulated value, and generating auxiliary information for the cloud server update;

The update data sending unit 48 is configured to send, by the data owner, the text accumulated value and the suffix accumulated value of the updated text string to the data access end, and send the auxiliary information to the cloud server;

The cloud update unit 49 is configured to: when the cloud server receives the update instruction for inserting, deleting, and/or replacing, according to the character string to be inserted, the character string to be deleted in the text string, and/or the character string to be replaced, And public key and auxiliary information, pre-stored text strings, suffix arrays, texts in the cloud server The string's random number set, text proof set, and suffix proof set are updated.

As an example, when the data owner receives the data insertion instruction, the insertion position in the text string, the length of the string to be inserted, and the character string to be inserted are obtained, and the following operations are performed:

T[i,j]＝T[i]T[i+1]...T[j]，i为插入位置。(1) Insert the string s to be inserted into the text string: T'=T[1:i-1]||s||T[i:n], where T' is obtained after inserting the string Text string,

T[i,j]=T[i]T[i+1]...T[j], where i is the insertion position.

(2) Add the random number corresponding to the character in the string to be inserted in the random number set R of the text string: R'={r ₁ ... r _i-1 , r' ₁ ... r' _l , r _i ... r _n }, where r' ₁ ... r' _l is a random number corresponding to the character in the string s to be inserted added to the random number set R, and l is the string s to be inserted length.

(3) Calculate a new prime number for the updated text string. The formula for calculating the new prime number can be: pt' ₀ = PG(T[i-1], r _i-1 , s[1], r' ₁ ), Pt' _i = PG(s[i],r' _i ,s[i+1],r' _i+1 ),pt' _l =PG(s[l],r' _l ,T[i],r _i ), where 1 ≤ _i < 1, aggregated into TIS = {pt' _j | 0 ≤ _j ≤ l}.

(4) Delete the <t[i-1], T[i]> associated prime number pt _i-1 , aggregate into TDS={pt _i-1 }, and get the auxiliary information AuxData={r' ₁ ,... ,r' _l }.

其中，I_t＝∏_pt∈TISpt，D_t＝∏_pt∈TDSpt。文本辅助累加值的计算公式为：

其中，wit为witness的简写，用来表示数据的辅助作用。(5) updating the text accumulated value of the text string and calculating the text auxiliary accumulated value of the text string, and the formula for updating the text accumulated value of the text string may be:

Where I _t = ∏ pt _{∈ TIS} pt, D _t = ∏ pt _{∈ TDS} pt. The text-assisted accumulated value is calculated as:

Among them, wit is shorthand for witness, used to represent the auxiliary role of data.

(6) generating an suffix array SA' of the updated text string T', comparing the difference between the suffix array SA of the text string before the update and the updated suffix array SA', determining the prime set SDS to be deleted, and Calculate the set of prime numbers SIS that need to be added.

其中，I_s＝∏_ps∈SISps，D_s＝∏_ps∈SDSps。后缀辅助累加值的计算公式为：

获得辅助信息

(7) Update the suffix accumulated value of the text string and calculate the suffix auxiliary accumulated value. The update formula for the suffix accumulated value is:

Where I _s = ∏ ps _{∈ SIS} ps, D _s = ∏ ps _{∈ SDS} ps. The formula for calculating the suffix auxiliary accumulated value is:

Access to auxiliary information

Preferably, when the cloud server receives the data update instruction, according to the character string to be inserted, the character string to be deleted in the text string, and/or the character string to be replaced, and the public key and the auxiliary information, the cloud server The pre-stored text string, the suffix array, and the random number set of the text string, the text proof set, and the suffix proof set are updated to implement dynamic update of the cloud server data.

As an example, when the cloud server receives the data insertion instruction, it acquires the insertion position in the text string, the length of the character string to be inserted, and the character string to be inserted, and performs the following operations:

T[i,j]＝T[i]T[i+1]...T[j]，i为插入位置。(1) Insert the string s to be inserted into the text string: T'=T[1:i-1]||s||T[i:n], where T' is obtained after inserting the string Text string,

T[i,j]=T[i]T[i+1]...T[j], where i is the insertion position.

(2) Add the random number corresponding to the character in the string to be inserted in the random number set R of the text string: R'={r ₁ ... r _i-1 , r' ₁ ... r' _l , r _i ... r _n }, where r' ₁ ... r' _l is a random number corresponding to the character in the string s to be inserted added to the random number set R, and l is the string s to be inserted length.

(3) Calculate a new prime number for the updated text string. The formula for calculating the new prime number can be: pt' ₀ = PG(T[i-1], r _i-1 , s[1], r' ₁ ), Pt' _i = PG(s[i],r' _i ,s[i+1],r' _i+1 ),pt' _l =PG(s[l],r' _l ,T[i],r _i ), where 1 ≤ _i < 1, aggregated into TIS = {pt' _j | 0 ≤ _j ≤ l}.

(4) Delete the prime numbers pt _i-1 associated with <T[i-1], T[i]>, and assemble them into TDS={pt _i-1 }.

计算新的文本证明

并添加到WT中。根据文本证明集合WT中剩余的素数pt，对对应的文本证明进行更新：

其中，a*pt+b*D_t＝1。最后得到新的文本证明集合WT'。(5) Delete the text proof wt _pt corresponding to each prime number pt∈TDS from the text proof set WT of the text string. For each new prime pt'∈TIS, calculate

Calculate a new text proof

And added to the WT. Update the corresponding text proof according to the remaining prime number pt in the text proof set WT:

Where a*pt+b*D _t =1. Finally, a new text proof set WT' is obtained.

(6) generating an suffix array SA' of the updated text string T', comparing the difference between the suffix array SA of the text string before the update and the updated suffix array SA', determining the prime set SDS to be deleted, and Calculate the set of prime numbers SIS that need to be added.

并添加到后缀证明集合WS中，其中，I'_s＝∏_ps∈SIS-ps'ps。根据后缀证明集合WS中剩余的素数ps，对对应的后缀证明进行更新：

其中，a*pt+b*D_t＝1。最后得到新的后缀证明集合WS'。(7) Delete the ws _ps corresponding to each prime number ps∈SDS from the WS in the suffix proof set of the text string T, and calculate a new suffix proof for each prime number ps'∈SIS

And added to the suffix proof set WS, where I _'s = ∏ _{ps ∈ SIS-ps'} ps. The corresponding suffix proof is updated according to the remaining prime number ps in the set WS according to the suffix:

Where a*pt+b*D _t =1. Finally, a new suffix proof set WS' is obtained.

In the embodiment of the present invention, the cloud server, the data access end, and the data Owner cooperate to complete the matching verification of the pattern string, and the suffix array is used as the index of the cloud server matching process in the matching verification process, thereby improving the efficiency of the pattern string matching. The textual proof set and the suffix proof set in the dynamic verifiable data structure complete the verification of the evidence, and the verification result is completed by the text accumulating value and the suffix accumulating value in the dynamically verifiable data structure, and the data access end stores the fixed size. The public key makes the verification more concise. The dynamic verifiable structure generated by the data owner realizes the dynamic update of data on the data owner and the cloud server, and effectively reduces the calculation overhead of the data owner and the communication overhead between the data owner and the cloud server in the update process.

In the embodiment of the present invention, each unit of the pattern string matching verification apparatus may be implemented by a corresponding hardware or software unit, and each unit may be an independent software and hardware unit, or may be integrated into one soft and hardware unit, and is not limited thereto. this invention.

Embodiment 3:

FIG. 3 shows the structure of a mode string matching verification apparatus according to Embodiment 3 of the present invention. For the convenience of description, only parts related to the embodiment of the present invention are shown.

The pattern string matching verification apparatus 5 of the embodiment of the present invention includes a processor 50, a memory 51, and a computer program 52 stored in the memory 51 and operable on the processor 50. The processor 50, when executing the computer program 52, implements the steps in the above-described method embodiments, such as steps S101 through S103 shown in FIG. Alternatively, processor 50, when executing computer program 52, implements the functions of the various units of the apparatus embodiments described above, such as the functions of units 31 through 33 shown in FIG.

In the embodiment of the present invention, the cloud server, the data access end, and the data Owner cooperate to complete the matching verification of the pattern string, and the suffix array is used as the index of the cloud server matching process in the matching verification process. The efficiency of the pattern string matching is improved, the verification evidence is searched through the text proof set and the suffix proof set in the dynamic verifiable data structure, and the matching result is verified by the text accumulating value and the suffix accumulating value in the dynamically verifiable data structure. In addition, the data access side stores a fixed-size public key, making verification more concise. The dynamic verifiable structure generated by the data owner realizes the dynamic update of data on the data owner and the cloud server, and effectively reduces the calculation overhead of the data owner and the communication overhead between the data owner and the cloud server in the update process.

Embodiment 4:

In an embodiment of the present invention, there is provided a computer readable storage medium storing a computer program, which when executed by a processor, implements the steps in the foregoing method embodiments, for example, FIG. Steps S101 to S103 are shown. Alternatively, the computer program, when executed by the processor, implements the functions of the various units of the apparatus embodiments described above, such as the functions of units 31 through 33 shown in FIG.

In the embodiment of the present invention, the cloud server, the data access end, and the data Owner cooperate to complete the matching verification of the pattern string, and the suffix array is used as the index of the cloud server matching process in the matching verification process, thereby improving the efficiency of the pattern string matching. The textual proof set and the suffix proof set in the dynamic verifiable data structure complete the verification of the evidence, and the verification result is completed by the text accumulating value and the suffix accumulating value in the dynamically verifiable data structure, and the data access end stores the fixed size. The public key makes the verification more concise. The dynamic verifiable structure generated by the data owner realizes the dynamic update of data on the data owner and the cloud server, and effectively reduces the calculation overhead of the data owner and the communication overhead between the data owner and the cloud server in the update process.

The computer readable storage medium of the embodiments of the present invention may include any entity or device capable of carrying computer program code, a recording medium such as a ROM/RAM, a magnetic disk, an optical disk, a flash memory, or the like.

The above is only the preferred embodiment of the present invention, and is not intended to limit the present invention. Any modifications, equivalent substitutions and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. Within the scope.

Claims (10)

A pattern string matching verification method, characterized in that the method comprises the following steps: When the cloud server receives the pattern string matching verification request of the data access end, the cloud server acquires the to-be-matched pattern string sent by the data access end, and matches the to-be-matched pattern string with the pre-stored text string according to the pre-stored suffix array. Matching result The cloud server searches for the verification evidence corresponding to the matching result according to the text string, the suffix array, and the pre-stored random number set of the text string, the text proof set, and the suffix proof set, and the matching result and the verification result. Evidence is sent to the data access end; The data access end verifies the matching result according to the verification evidence, the text accumulated value and the suffix accumulated value of the text string stored in advance, and a pre-stored public key, and generates and outputs a verification result, The text proof set, the suffix proof set, the text accumulating value and the suffix accumulating value of the text string constitute a dynamic verifiable data structure obtained by the data possessor preprocessing the text string. The method of claim 1, wherein the method further comprises: before the step of the cloud server receiving the pattern string matching verification request of the data access end, the method further comprises: Generating, by the data owner, a public-private key pair according to a preset security parameter, and exposing the public key in the public-private key pair; Generating the suffix array according to the text string, and binding a random number to each character of the text string, generating a random number set of the text string, according to the text string, a random number set of the text string, and a suffix Generating the dynamic verifiable data structure by an array, a random number set of the suffix array, and the public key; The data owner sends the text string, the suffix array, and the random number set of the text string, the text proof set, and the suffix proof set to the cloud server, and sends the text accumulated value and the suffix accumulated value of the text string. Give the data access side. The method according to claim 1, wherein after the step of verifying the matching result and generating and outputting the verification result, the method further comprises: When the data owner receives the update instruction for inserting, deleting, and/or replacing, according to the character string to be inserted, the character string to be deleted in the text string, and/or the character string to be replaced, And the public key, updating the text string, the suffix array, and the random number set of the text string, the text accumulated value, and the suffix accumulated value, and generating auxiliary information for the cloud server update; The data owner sends the text accumulated value and the suffix accumulated value of the updated text string to the data access end, and sends the auxiliary information to the cloud server; When the cloud server receives an update instruction for inserting, deleting, and/or replacing, according to the character string to be inserted, the character string to be deleted in the text string, and/or the character string to be replaced, and The public key and the auxiliary information update the text string, the suffix array, the random number set of the text string, the text proof set, and the suffix proof set pre-stored in the cloud server. The method according to claim 1, wherein the cloud server searches for the match according to the text string, the suffix array, and a pre-stored random number set of the text string, a text proof set, and a suffix proof set. The results correspond to the steps of verifying the evidence, including: When the matching result is that the matching is successful, the cloud server acquires a substring that successfully matches the to-be-matched pattern string from the text string, and generates a set according to the random number set and the text proof set of the text string. Determining a random number set and a text proof set of the substring, and combining the random number set and the text proof set of the substring into the verification evidence that the matching is successful; And the step of the cloud server searching for the verification evidence corresponding to the matching result according to the text string, the suffix array, and the pre-stored random number set of the text string, the text proof set, and the suffix proof set, further comprising: When the matching result is that the matching fails, the cloud server searches for the first suffix and the second suffix in the text string according to the to-be-matched mode string, according to the random number set and the text proof set of the text string. Generating a random number set and a text proof set of the common prefix of the first suffix, the second suffix, and the to-be-matched pattern string, respectively; And generating, according to the first suffix, the second suffix, the length of the common prefix of the to-be-matched pattern string, the random number set, and the text proof set, generating verification evidence that the matching fails. The method according to claim 4, wherein said data access terminal performs a text accumulated value and a suffix accumulated value of said text string stored in advance according to said verification evidence, and a pre-stored public Key, the step of verifying the matching result, including: When the matching result is that the matching is successful, the matching result is verified according to the random number set and the text proof set in the verification evidence of the matching success, and the verification formula is:

Wherein, 1≤k <m, the Acc _t is the accumulated value of the suffix text string, the wt _'k is the sub-set of the text string in the text proved k-tuples proof text, the pt ' _k is the text prime of the kth text tuple in the to-be-matched pattern string, and m is the length of the to-be-matched pattern string. A mode string matching verification device, characterized in that the device comprises: And the mode string matching unit is configured to: when the cloud server receives the mode string matching verification request of the data access end, acquire the to-be-matched mode string sent by the data access end, and store the to-be-matched mode string and the pre-storage according to the pre-stored suffix array The text string is matched to obtain a matching result; An evidence search unit, configured to search, according to the text string, the suffix array, the pre-stored random number set of the text string, the text proof set, and the suffix proof set, the verification evidence corresponding to the matching result, The matching result and verification evidence are sent to the data access end; a matching verification unit, configured to: verify, according to the verification evidence, a text accumulated value and a suffix accumulated value of the text string stored in advance, and a pre-stored public key, verify the matching result, generate and And outputting the verification result, the text proof set, the suffix proof set, the text accumulating value and the suffix accumulating value of the text string constitute a dynamic verifiable data structure obtained by preprocessing the text string by the data possessing end. The device of claim 6 wherein said device further comprises: a key generation unit, configured to generate, by the data possession end, a public-private key password pair according to a preset security parameter, and publicize the public key in the public-private key password pair; a verifiable data generating unit, configured to generate the suffix array according to the text string, and bind a random number to each character of the text string to generate a random number set of the text string, according to the text string, Generating the dynamic verifiable data structure by a random number set of text strings, a suffix array, a random number set of a suffix array, and the public key; a data sending unit, configured to: the data string, the suffix array, and the text The set of random numbers of the string, the set of text proofs, and the set of suffixes are sent to the cloud server, and the text accumulated value and the suffix accumulated value of the text string are sent to the data access end. The device of claim 6 wherein said device further comprises: a data end updating unit, configured to: when the data owner receives an update instruction for inserting, deleting, and/or replacing, according to a character string to be inserted, a character string to be deleted in the text string, and/or a string to be replaced, and the public key, updating the text string, the suffix array, and the random number set of the text string, the text accumulated value, and the suffix accumulated value, and generating an auxiliary for the cloud server update information; An update data sending unit, configured to send, by the data owner, a text accumulated value and a suffix accumulated value of the updated text string to the data access end, and send the auxiliary information to the cloud server; a cloud update unit, configured to: when the cloud server receives an update instruction for inserting, deleting, and/or replacing, according to the character string to be inserted, a character string to be deleted in the text string, and/or The replaced string, and the public key and the auxiliary information, are updated with a text string, a suffix array, a random number set of the text string, a text proof set, and a suffix proof set pre-stored in the cloud server. A mode string matching verification device comprising a memory, a processor, and a computer program stored in the memory and operable on the processor, wherein the processor implements the right when executing the computer program The steps of the method of any of 1 to 5 are claimed. A computer readable storage medium storing a computer program, wherein the computer program, when executed by a processor, implements the steps of the method of any one of claims 1 to 5.

Images