CN115225260A - Dynamic searchable encryption method - Google Patents

Abstract

The invention provides a dynamic searchable encryption method, which constructs a file identifier encryption and decryption key by using a double-chain structure, allows a client to update data stored in a server as required, cannot completely recover the double-chain key of a corresponding file after deletion operation is executed, ensures that the deleted file cannot be queried in a subsequent query process so as to realize backward security, and simultaneously has high overall operation efficiency based on simple encryption primitive constructs such as a hash function and a pseudorandom function, and realizes safe and efficient dynamic addition, deletion and query.

Description

A Dynamic Searchable Encryption Method

technical field

The invention relates to the technical field of dynamic searchable encryption, in particular to a dynamic searchable encryption method for constructing a key based on a double-chain structure to realize backward security.

Background technique

With the rapid development of networks and smart devices such as the Internet, Internet of Things, and mobile terminals, the types and scale of data are growing at an unprecedented rate, forming abundant data resources. In order to store and share these data resources more conveniently, the usual practice is for the data owner to host the data on the local client to the server such as the cloud platform, and then the server provides various services for the data user. At the same time, in order to ensure data security, the data owner will encrypt the data on the client side and then outsource the ciphertext data to a server such as a cloud platform for storage.

In order to securely carry out various cloud services on encrypted data, such as keyword-based query services, searchable encryption technology is widely used. In order to further meet the characteristics of data dynamics in the big data environment, dynamic searchable encryption is proposed, which allows users to update the data that has been outsourced to the cloud platform on demand. Research shows that how to ensure forward security and backward security in the update process are two important aspects of searchable encryption technology. Forward security requires that newly added files cannot be retrieved using previous query trapdoors, while backward security emphasizes that deleted files cannot be retrieved anymore. Among them, forward security can be realized by trapdoor replacement, keyword counter and other technologies, while backward security usually requires complex encryption primitives (such as Oblivious RAM, public key puncture encryption) or multiple rounds of interactive query to achieve, there is efficiency low problem. In the literature "Practical backward-secure searchable encryption from symmetric puncturable encryption", Sun et al. constructed a symmetric puncturable encryption scheme by using puncture pseudo-random functions to achieve backward security under the premise of ensuring a single round of search. However, this scheme needs to send a large amount of PKS (Public Key Share) to the cloud server during the deletion process, resulting in a lot of communication overhead; in addition, the symmetric puncture encryption is based on AES construction, which involves multiple rounds of AES encryption in the construction process, which is inefficient. . Therefore, how to ensure backward security and improve the running efficiency of dynamic query schemes is still a very difficult problem.

SUMMARY OF THE INVENTION

In order to solve the above-mentioned defects in the prior art, the present invention provides a dynamic searchable encryption method, which uses a double-chain structure to construct a file identifier encryption and decryption key, which allows the client to update the data stored in the server as needed. , the double-chain key of the corresponding file cannot be completely recovered after the deletion operation is performed, ensuring that the deleted file cannot be queried in the subsequent query process to achieve backward security. At the same time, the scheme is based on simple encryption primitives (such as hash functions, pseudo Random function) structure, the overall operation efficiency is high, and it can realize safe and efficient dynamic addition, deletion and query.

According to the first aspect of the present invention, a dynamic searchable encryption method is provided, which is characterized by comprising: a data addition step, a data deletion step, and a data query step;

The client includes a plaintext index table DB, a master private key msk, and a symmetric encryption key _ke , wherein the DB stores keyword-file identifier pairs, and each keyword w in the DB corresponds to a sub-data set DB(w), The data set includes all keyword-file identifier pairs corresponding to the keyword, and the sub-data set is divided into one or more segments. The system parameter t represents the maximum number of keyword-file identifier pairs that each segment can hold. number, the system parameter d represents the maximum number of keyword-file identifier pairs that can be deleted in each segment;

The server includes a ciphertext index table EDB, and the EDB includes a query ciphertext index table T _S and a deletion ciphertext index table T _D , and stores the ciphertext data generated through the data adding step;

Data addition steps include:

Step 101: The client determines the order c of the keyword-file identifier pair (w, f) to be operated in DB(w), the segment p to which (w, f) belongs in DB(w), and ( w,f) order i in segment p, the total number of key-file identifier pairs cnt and the total number of segments S in local table Tc(w) record DB(w)

其中e₁为(w,f)的第一查询密文，e₂为(w,f)的第二查询密文，

为e₁和e₂在T_S中的次序，e₃为(w,f)的删除密文，

为e₃在T_D中的次序，将τ_add发送给服务端；Step 102: The client encrypts (w, f) and generates data to add a trapdoor

where e ₁ is the first query ciphertext of (w, f), e ₂ is the second query ciphertext of (w, f),

is the order of e ₁ and e ₂ in T _S , e ₃ is the deleted ciphertext of (w, f),

For the order of e ₃ in TD, send _{τ add} to the server;

和

Step 103: The server updates the EDB after receiving τ _add , so that

and

The steps of generating e ₁ and e ₂ in step 102 specifically include:

Step A1: For w and p, use msk to encrypt through HMAC algorithm H, and generate the forward chain root key _{Kw,p and reverse chain root key K′w,p of} segment p, ( _Kw,p ,K′ _w,p )←H(msk,w||p), where || is a string concatenation operation;

b_k＝2K_{w，p，k，i}-K′_{w，p，k，i}，K_w,p,k,i＝X(d_w,p,k,i)，K′_w,p,k,i＝X(d′_w,p,k,t+1-i)，d_w,p,k←H(K_w,p,k)，d′_w,p,k←H(K′_w,p,k)，其中k∈[1,d]，

表示异或运算，b_k为(w,f)的第k个双链密钥，K_w,p,k,i为(w,f)的第k个正向链密钥，K′_w,p,k,i为(w,f)的第k个反向链密钥，d_w,p,k为分段p的第k个正向链密钥，d′_w,p,k为分段p的第k个反向链密钥；Step A2: Generate the file identifier key corresponding to (w, f)

b _k =2K _w,p,k,i -K'w _,p,k,i , _Kw,p,k,i =X( _dw,p,k ,i), _{K'w,p,k ,i} =X(d′ _w,p,k ,t+1-i), _dw,p,k ←H( _Kw,p,k ), d′ _w,p,k ←H( _{K′w ,p,k} ), where k∈[1,d],

Indicates the XOR operation, b _k is the k-th double-chain key of (w, f), K _{w, p, k, i} is the k-th forward chain key of (w, f), K′ _{w, p,k,i} is the kth reverse chain key of (w,f), dw,p,k is the kth forward chain key of segment p, d′ _{w,p,k is} the segment the k-th reverse chain key of segment p;

Wherein, X is the key cycle generation algorithm, the first input is the seed key key _seed , the second input is the number of iterations n, and the output is the value after performing n iterations of the hash function on the key _seed ;

根据一元一次函数F_k(x)＝(K′_w,p,k,i-K_w,p,k,i)x+b_k生成第二查询密文

Step A3: Use sk _{w, f} to encrypt the file identifier f to generate the first query ciphertext

Generate the second query ciphertext according to the unary linear function F _k (x)=(K′ _w,p,k,i -K _w,p,k,i )x+b _k

和

的步骤具体包括：Generated in step 102

and

The steps specifically include:

Step B1: use msk to encrypt w through a pseudo-random function F, and generate a position calculation key PK _w ←F(msk, w);

Step B2: Use PK _w to encrypt the location information of (w, f) to generate

The step of generating _e3 in step 102 specifically includes:

Step C1: use k _e to encrypt p and i through the encryption process SE.Enc of the symmetric encryption algorithm, and generate the deleted ciphertext e ₃ ←SE.Enc( _ke ,p||i);

Data deletion steps include:

Step 201: the client encrypts the keyword-file identifier pair (w, f) to be operated and generates a data deletion trapdoor τ _del ←H(PK _w , w||f), and sends τ _del to the server;

Step 202: After receiving τ _del , the server obtains the information of T _D [τ _del ], that is, the deleted ciphertext e ₃ corresponding to (w, f), and sends e ₃ to the client;

Step 203: After receiving e ₃ , the client uses ke to decrypt _{e 3} through the decryption process SE.Dec of the symmetric encryption algorithm, and generates the segment to which (w, f) belongs in DB(w) and the segment in the segment. Order (p,i)←SE.Dec(k _e ,e ₃ ), record (p,i) to the local table Tc(w);

The data query steps include:

Step 301: The client corresponds to the keyword w to be operated, and determines the segment to which the keyword-file identifier pair belongs and the sequence in the segment according to cnt and S in Tc(w) and the keyword-file identifier pair that has performed the deletion step. The segment set R that has performed the data deletion step in DB(w), the segment set Q that has not performed the data deletion step in DB(w), and the number of times that each segment in the set R has performed the data deletion step;

Step 302: The client generates a data query trapdoor τ _srh ←(cnt,PK _w ,τ ₁ ,τ ₂ ) corresponding to the keyword w to be operated, wherein the first query information τ ₁ ←(K _w,q , K′ _w,q ) _q∈Q , K _w,q is the forward chain root key of the segment q in the set Q, K′ _w,q is the reverse chain root key of the segment q in the set Q, the first Second query information τ ₂ ←((K _w,r,h,j+1 ,K′ _w,r,h,j-1 ) _h∈[1,z] ,(d _w,r,g ,d′ _{w ,r,g} ) _g∈[z+1,d] ) _r∈R , z is the number of times the data deletion step is performed on the segment r in the set R, z≤d, the keyword at the jth position on the segment r - The file identifier pair (w,f _r,j ) is the object of the h-th data deletion step on segment r, and K _w,r,h,j+1 is the j+1-th position key on segment r The h-th forward chain key of the word-file identifier pair (w,f _r,j+1 ), _{K′w,r,h,j-1} is the j-1th position keyword-file identifier pair The h-th reverse chain key of (w,f _r,j-1 ), d _w,r,g is the g-th forward chain key of segment r, d′ _w,r,g is the segment The g-th reverse chain key of r; the client sends τ _srh to the server;

Step 303: After receiving τ _srh , the server obtains, according to τ _srh , the plaintext of the file identifier corresponding to w that has not performed the data deletion step, and cannot obtain the plaintext of the file identifier corresponding to w that has performed the data deletion step according to τ _srh ;

Step 304: The server returns all the obtained file identifiers in plaintext to the client as query results;

Further, the dynamic searchable encryption method provided by the present invention is characterized in that, the data deletion step further comprises:

After the server sends e ₃ to the client, one or more of e ₁ , e ₂ , and e ₃ corresponding to (w, f) in the EDB are not cleared.

Further, the dynamic searchable encryption method provided by the present invention is characterized in that step 302 further includes:

After the client generates τ _srh , it clears the contents of T _C [w].

Further, the dynamic searchable encryption method provided by the present invention is characterized in that step 303 includes:

Step 3031: Obtain the first query ciphertext and the second query ciphertext of all keyword-file identifier pairs corresponding to w in T _S according to cnt and PK _w ;

Step 3032: Obtain the file identifier key corresponding to the keyword-file identifier pair in the set Q according to τ ₁ , and decrypt the corresponding first query ciphertext to obtain the file identifier plaintext in the set Q;

Step 3033: Obtain the file identifier key corresponding to the keyword-file identifier pair in the set R for which the data deletion step has not been performed according to τ ₂ , and decrypt the corresponding first query ciphertext to obtain the file identifier in the set Q Run plaintext.

According to a second aspect of the present invention, a computer device is provided, characterized in that it includes:

memory for storing instructions; and

A processor configured to invoke the instructions stored in the memory to execute the dynamically searchable encryption method of the first aspect.

According to a third aspect of the present invention, a computer-readable storage medium is provided, characterized in that an instruction is stored, and when the instruction is executed by a processor, the dynamically searchable encryption method of the first aspect is executed.

Compared with the prior art, the above-mentioned technical solution conceived by the present invention has at least the following beneficial effects:

(1) The present invention constructs a file identifier encryption and decryption key based on the key construction method of the double-chain structure, which allows the client to update the data stored in the server as needed, and the corresponding file after the deletion operation is performed even if the server does not have it. If it is cleared, the server cannot completely restore the double-chain key of the file and thus cannot obtain the decryption key, which ensures that the file cannot obtain the plaintext in the subsequent query process, that is, it cannot be queried, thus realizing the backward direction of the dynamic update process. Safety.

(2) The encryption and decryption operations of the present invention all use light-weight primitives, especially in the process of data deletion, no complicated calculation is required, and the client only needs to record the deletion state.

It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention.

Description of drawings

The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments consistent with the invention and together with the description serve to explain the principles of the invention.

FIG. 1 is a schematic flow chart showing the main steps of dynamic encryption according to an exemplary embodiment.

FIG. 2 is a schematic diagram illustrating interaction between a client and a cloud server according to an exemplary embodiment.

FIG. 3 is a schematic diagram illustrating a process of generating a file identifier key according to an exemplary embodiment.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other as long as there is no conflict with each other.

Before explaining the technical solutions of the present invention in detail, the meanings represented by some symbols involved in this article are listed as follows:

Exemplary embodiments will be described in detail herein, examples of which are illustrated in the accompanying drawings.

The present invention provides a dynamic searchable encryption method 10, as shown in FIG. 1, which realizes dynamic update and security on a server such as a cloud platform through three different processes: a data addition step 100, a data deletion step 200, and a data query step 300. Inquire.

Among them, the client is usually the terminal device of the data owner, such as personal computer, mobile phone, etc., with limited data storage capacity and available functions; Provide powerful functions. The data owner often needs to store the client's data on the server to obtain more services, but the server may not be trusted, so the encrypted data needs to be stored on the server. The encrypted data should be dynamically updated, and Guarantee forward and backward security in the dynamic update process.

In the initialization stage, the client preprocesses the local file data set to form a set of keyword-file identifier pairs, namely the plaintext index table DB, each keyword in the DB corresponds to a sub-data set, and the sub-data set includes the keyword Corresponding to all keyword-file identifier pairs, the subdataset is divided into one or more segments. Since the invention adopts the idea of segmentation to generate a queryable ciphertext index, the client will generate a system parameter (t, d) during the initialization process, where the system parameter t represents the keyword-file that each segment can accommodate The maximum number of identifier pairs, and the system parameter d indicates the maximum number of keyword-file identifier pairs that can be deleted in each segment.

In some embodiments, the client implements the division of data subsets by processing the DB into an inverted index, and the order c of the keyword-file identifier pair (w, f) in DB(w) is (w) ,f) the order in the inverted index of w on the DB.

In the initialization phase, the client also generates the master private key msk and the symmetric encryption key _ke . In some embodiments, the client generates msk and _ke according to a given security parameter λ.

位置，用于在数据查询步骤300中解密恢复出明文f，删除密文e₃存放在删除密文索引表T_D中的

位置，用于在数据删除步骤200中向客户端反馈应删除文件的信息，从而被客户端解密后记录。The ciphertext index table EDB is stored on the server. The EDB includes the query ciphertext index table T _S and the delete ciphertext index table T _D , and stores the ciphertext data generated through the data adding step 100. In the initialization stage, the server can pre-generate the ciphertext data. The corresponding data structure of the EDB can also be gradually generated in the data adding step 100 . For a keyword-file identifier pair (w, f), the encrypted ciphertext is added to the EDB, and the query ciphertexts e ₁ and e ₂ are stored in the query ciphertext index table T _S

The position is used to decrypt and restore the plaintext f in the data query step 300, and the deleted ciphertext _e3 is stored in the deleted ciphertext index table _TD .

The location is used to feed back the information of the file to be deleted to the client in the data deletion step 200, so that it is decrypted and recorded by the client.

Next, the data adding step 100 , the data deletion step 200 , and the data querying step 300 are described in detail.

In the data adding step 100, for the keyword-file identifier pair (w, f) to be operated, that is, the information of (w, f) needs to be added to the server, including the following steps:

Step 101, the client determines the position information c, p, and i of (w, f), and stores the size information cnt and S of DB(w) into Tc(w).

其中

表示向上取整。Specifically, the total number cnt of keyword-file identifier pairs in DB(w) can be obtained when the client preprocesses to generate the DB. In some embodiments, the client obtains the data of w on the DB through an inverted index. The maximum number of sorts in the inverted index is the total number of keyword-file identifier pairs cnt in DB(w); the total number of segments S in DB(w) can be obtained by calculation

in

Indicates rounded up.

在分段p中的次序i可以通过计算获得i＝c％p，％为取余运算。For the position information of (w,f), including its order c in DB(w), the segment p to which it belongs in DB(w), the order i of (w,f) in segment p, in some In the embodiment, the order c in DB(w) can be obtained by searching the order of (w, f) in the inverted index of w, and the segment p to which it belongs can be obtained by calculation

The order i in the segment p can be obtained by calculation i=c%p, % is the remainder operation.

The cnt and S are stored in the local table Tc(w) to be retrieved in the data query step 300 to construct a data query trapdoor.

将τ_add发送给服务端。Step 102: The client encrypts (w, f) and generates data to add a trapdoor

Send τ _add to the server.

为e₁和e₂在T_S中的次序，e₃为(w,f)的删除密文，

为e₃在T_D中的次序Specifically, e ₁ is the first query ciphertext of (w, f), e ₂ is the second query ciphertext of (w, f),

is the order of e ₁ and e ₂ in T _S , e ₃ is the deleted ciphertext of (w, f),

is the order of e ₃ in _TD

和

Step 103: The server updates the EDB after receiving τ _add , so that

and

The key in the data adding step 100 is how to generate each ciphertext in the data adding trapdoor τ _add and its storage location in step 102 .

The steps of generating e ₁ and e ₂ in step 102 specifically include:

Step A1: For w and p, use msk to encrypt through HMAC algorithm H, and generate the forward chain root key _{Kw,p and reverse chain root key K′w,p of} segment p, namely ( _{Kw, p} ,K′w _,p )←H(msk,w||p).

Step A2: Generate the file identifier key corresponding to (w, f)

In order to generate the file identifier key, for segments p and (w, f), there are several groups of forward chains and reverse chains, the number of which is determined by the system parameter d, that is, the number of segments that can be deleted in each segment The maximum number of keyword-file identifier pairs.

表示异或运算，sk_w,f由d个b_k连续异或运算后得到，所以需要获得d个b_k的值，b_k的具体计算方法为：In formula 1, b _k is the k-th double-chain key of (w, f), k∈[1,d],

Indicates the XOR operation, sk _{w, f} are obtained after d consecutive XOR operations of b _k , so it is necessary to obtain d values of b _k , and the specific calculation method of b _k is:

b _k = 2K _w,p,k,i -K′w _,p,k,i (Equation 2);

_Kw,p,k,i =X( _dw,p,k ,i), _K'w,p,k,i =X(d' _w,p,k ,t+1-i) (Equation 3 );

_dw,p,k ←H( _Kw,p ,k), d′ _w,p,k ←H( _K′w,p,k ) (Equation 4);

Among them, K _w,p,k,i is the kth forward chain key of (w,f) _{, K′w,p,k,i} is the kth reverse chain key of (w,f) , d _w,p,k is the kth forward chain key of segment p, d′ _w,p,k is the kth reverse chain key of segment p.

X is the key cycle generation algorithm, the first input is the seed key key _seed , the second input is the number of iterations n, and the output is the value after performing n iterations of the hash function on the key _seed .

In some embodiments, the pseudocode for the algorithm is as follows:

According to the key cycle generation algorithm and formula 3, it can be known that:

_Kw,p,k,i+1 =X( _Kw,p,k,i ,1), _{K′w,p,k,i-1} =X( _K′w,p,k,i ,1 ) (Formula 5);

Therefore, the k-th forward chain key of (w, f) is executed again by X algorithm to obtain the k-th forward chain key of the next order position in the forward direction, and the k-th forward chain key of (w, f) The reverse chain key executes the X algorithm once to obtain the k-th reverse chain key in the next order position in the reverse direction.

根据一元一次函数F_k(x)＝(K′_w,p,k,i-K_w,p,k,i)x+b_k生成第二查询密文

Step A3: Use sk _{w, f} to encrypt the file identifier f to generate the first query ciphertext

Generate the second query ciphertext according to the unary linear function F _k (x)=(K′ _w,p,k,i -K _w,p,k,i )x+b _k

Those skilled in the art can understand that if the plaintext f is to be decrypted according to the ciphertext e ₁ , sk _w,f needs to be obtained, that is, the value of each b _k needs to be calculated, k∈[1,d].

On the one hand, it can be known from Equation 3 and Equation 4 that if the forward chain root key _Kw,p and reverse chain root key _K′w,p and i of segment p are obtained, each a b _k , thereby obtaining the plaintext f at position i on segment p.

On the other hand, according to formula 2, it can be known that the unary linear function F _k (x) is essentially based on two coordinate points on the plane (1,K _w,p,k,i ) and (2, _{K′w,p ,k,i} ), b _k is the intercept of F _k (x), and e ₂ stores another point of the function (3,F _k (3)); therefore, if for each F _k ( x), any one of the forward chain key K _{w, p, k, i} and the reverse chain key K′ _{w, p, k, i} of (w, f) can be obtained, then according to (1 ,K _w,p,k,i ) and (3,F _k (3)) two points, or according to (2, _K′w,p,k,i ) and (3,F _k (3)) two points For each point, the intercept b _k of each F _k (x) is calculated by the Lagrangian interpolation method, so as to obtain the plaintext f of the position i on the segment p.

和

的步骤具体包括：Generated in step 102

and

The steps specifically include:

Step B1: use msk to encrypt w through a pseudo-random function F, and generate a position calculation key PK _w ←F(msk, w);

Step B2: Use PK _w to encrypt the location information of (w, f) to generate

Through the above encryption, the location information of (w, f) in the DB can be hidden from the server, and the ciphertext information of (w, f) can be stored in the encrypted location in the EDB.

The step of generating _e3 in step 102 specifically includes:

Step C1: use k _e to encrypt p and i through the encryption process SE.Enc of the symmetric encryption algorithm, and generate the deleted ciphertext e ₃ ←SE.Enc( _ke ,p||i).

Among them, the encryption algorithm includes DES algorithm, 3DES algorithm and other algorithms, and in some embodiments, the encryption algorithm uses the AES algorithm.

In the data deletion step 200, for the keyword-file identifier pair (w, f) to be operated, that is, the ciphertext information corresponding to (w, f) in the EDB needs to be deleted, including the following steps:

Step 201: The client encrypts (w, f) and generates a data deletion trapdoor τ _del ←H(PK _w ,w||f), and sends τ _del to the server.

Step 202: After receiving τ _del , the server obtains the information of _TD [τ _del ], that is, the deleted ciphertext e ₃ corresponding to (w, f), and sends e ₃ to the client.

的生成方式是一致的，内容均为H(PK_w,w||f)，因此T_D[τ_del]即为

可获得(w,f)对应的删除密文e₃。It can be known from step 201 and step B2 that τ _del and

The generation method is consistent, and the content is H(PK _w ,w||f), so T _D [τ _del ] is

The deleted ciphertext e ₃ corresponding to (w, f) can be obtained.

Step 203: After receiving e ₃ , the client uses ke to decrypt _{e 3} through the decryption process SE.Dec of the symmetric encryption algorithm, and generates the segment to which (w, f) belongs in DB(w) and the segment in the segment. Order (p,i)←SE.Dec( _ke ,e ₃ ), record (p,i) to the local table T _c (w);

Since e ₃ is encrypted by a symmetric encryption algorithm, after the client obtains _{e 3} , it can decrypt the position information (p, i) of (w, f) according to the corresponding ke of the client, and record it in the local table Tc (w), the data deletion step 200 has been performed by (w, f) that marked the location locally, and the ciphertext information in the EDB should be deleted.

Those skilled in the art can understand that, due to different data management mechanisms of servers such as different cloud platforms, even if the client sends a delete command to the server, the server may not substantially clear the corresponding data.

In some embodiments, after the server sends e ₃ to the client, one or more of e ₁ , e ₂ , and e ₃ corresponding to (w, f) in the EDB are not cleared. For example, the server just marks some data in e ₁ , e ₂ , and e ₃ as being in the "deleted" state.

Then, when querying after this, the data e ₁ , e ₂ , and e ₃ that should have been deleted may be obtained by the server again, and the server may obtain the plaintext of the data, thus resulting in a backward security risk, which is usually Data owners don't want to see.

By recording deletion information locally, the present invention is used to generate a data query trapdoor including deletion information based on the double-chain key structure of the present invention in the data query step 300, so that there is a way to avoid backward security risks and enable the server to execute During the query step, the plaintext corresponding to all undeleted data ciphertexts can be queried, and the plaintext information of the data ciphertexts in the "deleted" state (regardless of whether the data ciphertexts have been cleared by the server) cannot be obtained.

In the data query step 300, the client needs to return the plaintext information of all file identifiers f corresponding to the keyword w in the EDB, usually in order to retrieve the files containing the keyword w stored in the server. Corresponding to the keyword w to be operated, including the following steps:

Step 301: The client obtains cnt, S, and historical deletion information according to the information in Tc(w), and divides DB(w) into segment sets R and Q according to whether deletion has been performed.

Wherein, cnt and S in Tc(w) will be updated every time the data addition step 100 is executed, and the historical deletion information includes the information recorded in Tc(w) after the execution of each data deletion step 200, that is, the deleted keyword- The segment to which the file identifier pair belongs and the order within the segment.

According to the above information, it can be determined that the segment set R in DB(w) that has performed the data deletion step, the segment set Q that has not performed the data deletion step in DB(w), and each segment in the set R performs data deletion Step 200 times.

Step 302: The client generates a data query trapdoor τ _srh ←(cnt, PK _w , τ ₁ , τ ₂ ), and sends τ _srh to the server.

Among them, the first query information τ ₁ ←(K _w,q ,K′ _w,q ) _q∈Q , K _w,q is the forward chain root key of the segment q in the set Q, and K′ _w,q is the reverse chain root key of segment q in set Q;

The second query information τ ₂ ←((K _w,r,h,j+1 ,K′ _w,r,h,j-1 ) _h∈[1,z] ,(d _w,r,g ,d′ _w,r,g ) _g∈[z+1,d] ) _r∈R , z is the number of data deletion steps performed on segment r in the set R, z≤d, the key to the jth position on segment r The word-file identifier pair (w, _fr,j ) is the object of the hth data deletion step performed on segment r, and _Kw,r,h,j+1 is the j+1th step on segment r The position key-file identifier pair (w,f _r,j+1 ) is the h-th forward chain key, and _{K′w,r,h,j-1} is the j-1th position key-file identifier The h-th reverse chain key of the symbol pair (w,f _r,j-1 ), d _w,r,g is the g-th forward chain key of segment r, d′ _w,r,g is the h-th reverse chain key of segment r;

Step 303: After receiving τ _srh , the _server obtains the plaintext of the file identifier corresponding to w without performing the data deletion step according to τ _srh , and cannot obtain the plaintext of the file identifier corresponding to w with the data deletion step performed according to τ srh.

Due to the requirement of backward security, the data query trapdoor τ _srh cannot enable the client to obtain the ability to decrypt the ciphertext information that has been subjected to the data deletion step, that is, it cannot allow the client to obtain the file identifier password of this type of ciphertext information. key. Corresponding to step 302, the object of the h-th data deletion step performed on segment r is (w,f _r,j ). Therefore, the data query trapdoor τ _srh cannot contain complete information for decrypting f _,j .

Obviously, it can be known from the content of τ ₁ that τ ₁ is the decryption information used for each segment in the set Q, and cannot be used for the segment r in the set R, so the server cannot restore _fr,j according to τ ₁ .

Moreover, it can be known from the content of τ ₂ that the server cannot decrypt the information of τ ₂ to restore _fr,j .

Specifically, it can be known from the foregoing description of step A3 that if _fr,j is to be restored, the value of each b _k of (w,f _r,j ) must be obtained, k∈[1,d]. The minimum requirement for calculating the value of b _k is to obtain the k-th forward chain key K _w,r,k,j or the k-th reverse chain key _K′w,r,k,j .

On the one hand, the gth (dw _,r,g ,d′ _w,r,g ) of segment r is given in τ ₂ , g∈[z+1,d], it can be known from Equation 3, according to Only the g-th forward chain key K _w,r,g,j or the g-th reverse chain key _K′w,r,g,j of (w,f _r,j ) can be obtained by calculating (w,f _r,j ) b _g , but cannot calculate the h-th forward chain key K _w,r,h,j and the h-th reverse chain key of (w,f _r,j ) K′ _w,r,h,j , h∈[1,z], so the b _h of (w,f _,j ) cannot be obtained.

On the other hand, the h-th forward chain key K _w,r,h,j+1 and (w,f _r,j-1 ) of (w,f _r,j+1 ) are given in τ ₂ The h-th reverse chain key K′ _w,r,h,j-1 , according to formula 5, only each keyword-file identifier pair (w,f _{r,j+1 ) forward and backward can be obtained (w,f r,j+1} ) ,f _r,j+2 ),...,(w,f _r,d ) the h-th forward chain key, and (w,f _r,j-1 ) reverse each keyword-file The h-th reverse chain key of the identifier pair (w,f r _{, j-2} ),...,(w,f _r,1 ), so it is impossible to calculate the The h forward chain keys K _w,r,h,j and the h-th reverse chain key _K′w,r,h,j , so that b _h of (w,f _r,j ) cannot be obtained.

Therefore, in step 303, according to τ _srh , the server can only obtain the plaintext of the file identifier corresponding to w for which the data deletion step has not been performed, but cannot obtain the plaintext of the file identifier corresponding to w where the data deletion step has been performed.

Step 304: The server returns all the obtained file identifiers in plaintext to the client as query results.

In some embodiments, step 303 specifically includes the following steps:

Step 3031: Obtain the first query ciphertext and the second query ciphertext of all keyword-file identifier pairs corresponding to w in T _S according to cnt and PK _w .

c∈[1,cnt]，即可获得所有关键词-文件标识符对的第一查询密文和第二查询密文

并且，每个关键词-文件标识符对所属的分段p可以通过计算获得

在分段p中的次序i可以通过计算获得i＝c％p。Specifically, in step 3031, by calculating the position

c∈[1,cnt], the first query ciphertext and the second query ciphertext of all keyword-file identifier pairs can be obtained

And, the segment p to which each keyword-file identifier pair belongs can be obtained by calculation

The order i in the segment p can be obtained by calculation i=c%p.

Step 3032: Obtain the file identifier key corresponding to the keyword-file identifier pair in the set Q according to τ ₁ , and decrypt the corresponding first query ciphertext to obtain the file identifier plaintext in the set Q.

Specifically, in step 3032, for the segment q, q∈Q in DB(w) for which the data deletion step has not been performed, the server uses Kw,q and _K′w , _q in τ ₁ , according to the formula 3. Formula 4 and Formula 5, calculate the forward chain key and reverse chain key of all keyword-file identifier pairs on the segment, and further obtain each keyword-file identifier pair according to formula 2. A double-chain key b _k , k∈[1,d], then calculate the file identifier key of all keyword-file identifier pairs on the segment according to formula 1, and decrypt the corresponding file identifier key with the file identifier key. First query the ciphertext, thereby calculating the plaintext of all file identifiers on the segment.

Optionally, when calculating the double-chain key b _k , use any one of the forward chain key and the reverse chain key of the keyword-file identifier pair, combined with the second query ciphertext, through Lagrangian The double-chain key b _k is obtained by interpolation.

Step 3033: Obtain the file identifier key corresponding to the keyword-file identifier pair in the set R for which the data deletion step has not been performed according to τ ₂ , and decrypt the corresponding first query ciphertext to obtain the file identifier plaintext in the set Q .

Specifically, in step 3033, for the segment r, r∈R in which the data deletion step has been performed in DB(w), the server uses the g-th forward chain key and reverse key of segment r in τ ₂ Chain key (d _w,r,g ,d′ _w,r,g ), g∈[z+1,d], calculate all keyword-file identifier pairs on this segment according to formula 3 and formula 4 The g-th forward chain key and reverse-chain key of , and further obtain the g-th double-chain key b _g of the keyword-file identifier pair according to formula 2.

Optionally, when calculating the double-chain key b _g , use any one of the g-th forward chain key and the reverse chain key of the keyword-file identifier pair, combined with the second query ciphertext, through pulling Grange interpolation method to obtain double-chain key b _g

On segment r, the object of the hth data deletion step is (w, _{f r,j} ), and the server uses Kw _,r,h,j+1 and _{Kw,r,h, j-1} , according to formula 5, obtain the h-th forward chain key of each keyword-file identifier pair in the forward direction of (w,f _r,j+1 ), and (w,f _r,j-1 ) The h-th reverse chain key of each keyword-file identifier pair in the reverse direction is combined with the second query ciphertext to obtain the upper division of segment r by Lagrangian interpolation (w,f _r, The h-th double-chain key b _h of each keyword-file identifier pair other than _j ).

For all keyword-file identifier pairs on segment r that have not performed the data deletion step, combining b _g and b _h , the file identifier key can be obtained according to formula 1, and the corresponding first file identifier key is decrypted with the file identifier key. Query the ciphertext to calculate the plaintext of all file identifiers on this segment that have not performed the data deletion step.

In some embodiments, the client clears the content of T _C [w] after generating τ _srh . This keeps the contents of T _C [w] from increasing all the time. The basis for clearing T _C [w] is: According to the access mode, once the server queries the relevant files of w, the file information contained in the keyword has actually been exposed to the server. As for querying the files added later, we can ensure that the server cannot obtain the corresponding information of the newly added data according to the existing forward security technology.

Based on the same inventive concept, the present invention provides an embodiment of a dynamically searchable encryption method, as shown in FIG. 2 .

The client runs the initialization algorithm to generate the master private key msk, symmetric encryption key _ke and system parameters params←(t,d) required by the system; in order to add files to the server (take the cloud server as an example), perform the data addition steps , the client forms a data addition trapdoor τ _add locally and sends it to the cloud server, and the cloud server updates the EDB after receiving τ _add ; in order to delete the files that have been outsourced to the cloud server, perform the data deletion step, and the client generates a data deletion trapdoor τ _del and send it to the cloud server, the cloud server updates the EDB after receiving it and returns the corresponding segment information to the client, and the client updates T _C locally according to the returned result; in order to query the file containing the keyword w, execute the data In the query step, the client generates a data query trapdoor τ _{srh locally} and sends it to the cloud server. After receiving the τ _srh , the cloud server queries the EDB for files that have not been deleted, and returns the result IND to the client.

In this embodiment, as shown in FIG. 3 , the client preprocesses the local data set to form a DB, wherein the files corresponding to w ₁ in DB(w ₁ ) are {f ₁ , f ₂ , f ₃ , f ₄ , f ₅ , f ₆ , f ₇ , f ₈ }, the client initially generates the master private key msk, the symmetric encryption key _ke , and sets the system parameters params←(t=4, d=2).

After the data addition step is performed, the client generates τ _add and sends it to the cloud server. Specific steps are as follows:

(a) According to the system parameters, the client divides DB(w ₁ ) into two segments, p ₁ and p ₂ , and writes the total number of files and segments corresponding to w ₁ into T _C [w ₁ ]←(8, 2). As shown in FIG. 3 , the files corresponding to segment p ₁ are {f ₁ , f ₂ , f ₃ , f ₄ }, and the files corresponding to segment p ₂ are {f ₅ , f ₆ , f ₇ , f ₈ }.

利用HMAC算法生成不同分段的正向链根密钥和反向链根密钥，其中p₁段对应的

p₂段对应的

进一步计算不同分段的正向链密钥和反向链密钥，如图3所示，以p₁段为例，由于d＝2，p₁段有2组正向链密钥和反向链密钥，第1组为

第2组为

(b) The client uses a pseudo-random function to calculate the location calculation key

Use HMAC algorithm to generate forward chain root key and reverse chain root key of different segments, where p ₁ segment corresponds to

corresponding to segment p ₂

Further calculate the forward chain key and reverse chain key of different segments, as shown in Figure 3, taking the p ₁ segment as an example, since d=2, the p ₁ segment has 2 sets of forward chain keys and reverse chain keys chain key, group 1 is

Group 2 is

第2组为

进一步地，计算(w₁,f₁)对应的2个双链密钥b₁和b₂，

然后计算(w₁,f₁)对应的文件标识符密钥

客户端生成

(c) For each keyword-file identifier pair, the client computes the corresponding file identifier key to encrypt the file identifier. As shown in Figure 3, taking (w ₁ , f ₁ ) as an example, the forward order of the p ₁ segment is 1, and the reverse order is 4. Since d=2, there are 2 groups of (w ₁ , f ₁ ) Forward chain key and reverse chain key, where group 1 is

Group 2 is

Further, calculate the two double-chain keys b ₁ and b ₂ corresponding to (w ₁ , f ₁ ),

Then calculate the file identifier key corresponding to (w ₁ , f ₁ )

Client generated

和

生成一元一次函数

根据

和

生成一元一次函数

进一步地，计算出

(d) corresponds to (w ₁ , f ₁ ), the client according to

and

Generate unary linear function

according to

and

Generate unary linear function

Further, calculate

和

w₁||f₁)，最后产生

作为(w₁,f₁)的τ_add并发送给云服务器。(e) corresponds to (w ₁ , f ₁ ), the client computes

and

w ₁ ||f ₁ ), and finally produce

τ _add as (w ₁ , f ₁ ) and sent to the cloud server.

和

After the cloud server receives τ _add , execute

and

Execute the data adding step, the client generates τ _del and sends it to the cloud server, and the cloud server returns the deleted ciphertext _e3 to the client after accessing the EDB according to τ _del . Specific steps are as follows:

并发送给云服务器；(f) Take the user wish to delete the ciphertext corresponding to (w ₁ , f ₁ ) as an example, calculate on the client

and send it to the cloud server;

发送给客户端。(g) The cloud server receives τ _del , and finds the corresponding ciphertext from _TD [τ _del ]

sent to the client.

后执行

获得(w₁,f₁)位于分段p₁的第1个位置，并将该信息存放到T_C[w₁]。(h) The cloud server receives τ _del , and the client receives

post execution

Obtain (w ₁ , f ₁ ) at the first position of segment p ₁ , and store this information in T _C [w ₁ ].

It is worth noting that, from the user's point of view, the cloud server should delete all ciphertexts corresponding to (w ₁ , f ₁ ) after receiving τ _del , but the cloud server does not necessarily completely clear the ciphertext data.

Execute the data query step, the client generates τ _srh to the cloud server, and the cloud server returns the query result IND to the client after executing the query.

(i) Take the client query keyword w ₁ as an example. The client first obtains the file f ₁ at the first position of the p ₁ segment corresponding to w ₁ according to the local T _C [w ₁ ]. The data deletion step has been performed, and it is the first time on the p ₁ segment. Delete, and obtain the total number of files cnt=8 corresponding to w ₁ at the same time.

和

生成

和

对于p₂分段，由于未执行过数据删除步骤，生成

和

生成

将τ_srh发送给云服务器(j) For p ₁ segment, the client will generate

and

generate

and

For the p ₂ segment, since the data removal step has not been performed, the resulting

and

generate

Send τ _srh to cloud server

c∈[1,8]，找到w₁对应的所有关键词-文件标识符对的第一查询密文

(k) When the cloud server receives τ _srh , first according to

c∈[1,8], find the first query ciphertext of all keyword-file identifier pairs corresponding to w ₁

找到密文

但是，由于云服务器根据

无法获得

和

任一个，从而无法利用拉格朗日插值法获得b₁，进而无法获得

用以解密

所以即使云服务器保留了密文

查询结果IND也不会包括明文f₁，从而保证了后向安全。It should be noted that for (w ₁ , f ₁ ) that has already performed the data deletion step, if the cloud server does not clear the query cipher text corresponding to (w ₁ , f ₁ ) in the previous (h), the cloud server will still according to

find ciphertext

However, since the cloud server

can not get

and

any _one of the

to decrypt

So even if the cloud server keeps the ciphertext

The query result IND also does not include the plaintext f ₁ , thus ensuring backward security.

c∈[2,8]，云服务器根据τ_srh的内容获得

对

解密可获得f_c，云服务器将查询结果IND＝{f₂,f₃,f₄,f₅,f₆,f₇,f₈}返回给客户端。for

c∈[2,8], the cloud server obtains according to the content of τ _srh

right

Decryption can obtain f _c , and the cloud server returns the query result IND={f ₂ , f ₃ , f ₄ , f ₅ , f ₆ , f ₇ , f ₈ } to the client.

Other embodiments of the invention will readily suggest themselves to those skilled in the art upon consideration of the specification and practice of the invention disclosed herein. This application is intended to cover any variations, uses, or adaptations of the invention that follow the general principles of the invention and include common knowledge or conventional techniques in the art not disclosed by this disclosure . The specification and examples are to be regarded as exemplary only, with the true scope and spirit of the invention being indicated by the following claims.

It should be understood that the present invention is not limited to the precise structures described above and illustrated in the accompanying drawings, and that various modifications and changes may be made without departing from its scope. The scope of the present invention is limited only by the appended claims.

Claims (6)

1. A dynamic searchable encryption method, comprising: a data adding step, a data deleting step and a data inquiring step;

the client comprises a plaintext index table DB, a master private key msk and a symmetric encryption key k _e Wherein, DB stores keyword-file identifier pairs, each keyword w in DB corresponds to one subdata set DB (w), the subdata set comprises all keyword-file identifier pairs corresponding to the keyword, the subdata set is divided into one or more sections, and system parameter t represents the keyword-text that each section can containThe maximum number of file identifier pairs, and the system parameter d represents the maximum number of keyword-file identifier pairs that can be deleted in each segment;

the server side comprises a ciphertext index table EDB (enhanced data base), and the EDB comprises a query ciphertext index table T _S And deleting ciphertext index table T _D Storing the ciphertext data generated by the data adding step;

the data adding step includes:

step 101: the client determines the order c of the keyword-file identifier pairs (w, f) to be operated in DB (w), (w, f) the segment p to which the keyword-file identifier pairs belong in DB (w), and the order i of the keyword-file identifier pairs (w, f) in segment p, and records the total number cnt and the total number S of the segments in DB (w) in a local table Tc (w)

Step 102: the client encrypts (w, f) and generates data adding trapdoors

Wherein e ₁ First query ciphertext of (w, f), e ₂ A second query ciphertext of (w, f),

is e ₁ And e ₂ At T _S In the order of (b), e ₃ The deleted ciphertext of (w, f),

is e ₃ At T _D In the order of (1), will be _add Sending the data to the server;

step 103: the server receives tau _add Post-update EDB to order

And

said step 102 generating e ₁ And e ₂ The method specifically comprises the following steps:

step A1: for w and p, encrypting by using msk through an HMAC algorithm H to generate a forward chain root key K of the segment p _w，p And reverse chain root Key K' _w，p ，(K _w，p ，K′ _w，p ) And ← H (msk, w | | | p), in which | | | is a string concatenation operation;

step A2: generating (w, f) corresponding file identifier keys

b _k ＝2K _{w，p，k，i} -K′ _{w，p，k，i} ，K _{w，p，k，i} ＝X(d _w，p，k ，i)，K′ _{w，p，k，i} ＝X(d′ _w，p，k ，t+1-i)，d _w，p，k ←H(K _w，p ，k)，d′ _w，p，k ←H(K′ _w，p K), where k ∈ [1, d ]]，

Representing an exclusive OR operation, b _k The kth double-stranded key of (w, f), K _{w，p，k，i} K-th forward chain key of (w, f), K' _{w，p，k，i} The k-th reverse-link key of (w, f), d _w，p，k Kth forward chain key, d 'of segment p' _w，p，k The kth reverse link key for segment p;

wherein, X is a key cycle generation algorithm, and the first input is a seed key _seed The second input is iteration number n, and the key pair is output _seed Iteratively executing the value after the hash function for n times;

step A3: using sk _w，f Encrypting the file identifier f to generate a first query ciphertext

According to a unary linear function F _k (x)＝(K′ _{w，p，k，i} -K _{w，p，k，i} )x+b _k Generating a second query ciphertext

Generated in the step 102

And

the method specifically comprises the following steps:

step B1: w is encrypted by a pseudorandom function F using msk to generate a location calculation key PK _w ←F(msk，w)；

And step B2: use of PK _w Encrypting the position information of (w, f) to generate

Said step 102 generating e ₃ The method specifically comprises the following steps:

step C1: using k _e Enc encrypts p and i through an encryption process SE of a symmetric encryption algorithm to generate a deletion ciphertext e ₃ ←SE.Enc(k _e ，p||i)；

The data deleting step comprises:

step 201: the client encrypts the key word-file identifier pair (w, f) to be operated and generates a data deletion trapdoor tau _del ←H(PK _w W | | f), will τ _del Sending the data to the server;

step 202: the server receives tau _del Then, T is obtained _D [τ _del ]I.e. delete the ciphertext e ₃ Sending out e ₃ Giving the client side;

step 203: the client receives e ₃ Then, use k _e Decryption by symmetric encryption algorithmDec pair e ₃ Decrypting to generate (w, f) the segment in DB (w) and the order (p, i) ← SE _e ，e ₃ ) Record (p, i) to the local table Tc (w);

the data query step comprises:

step 301: the client side determines a segment set R in DB (w) in which the data deletion step is executed, a segment set Q in DB (w) in which the data deletion step is not executed and the number of times each segment in the set R is executed by the data deletion step according to cnt in Tc (w), S in Tc (w) and the sequence of the segment and the segment of the keyword-file identifier pair in which the deletion step is executed;

step 302: the client generates a data query trapdoor tau corresponding to a keyword w to be operated _srh ←(cnt，PK _w ，τ ₁ ，τ ₂ ) Wherein the first query information τ ₁ ←(K _w，q ，K′ _w，q ) _q∈Q ，K _w，q Is a forward-link root key, K ', of segment Q in set Q' _w，q For reverse chain root key of segment Q in set Q, second query information tau ₂ ←((K _{w，r，h，j+1} ，K′ _{w，r，h，j-1} ) _h∈[1，z] ，(d _w，r，g ，d′ _w，r，g ) _{g∈[z+1，d]} ) _r∈R Z is the number of times the data deletion step has been performed on segment R in set R, z is less than or equal to d, and the keyword-file identifier pair (w, f) at the jth position on segment R _r，j ) Is the object of performing said data deletion step h on the segment r, K _{w，r，h，j+1} For the j +1 th position keyword-file identifier pair (w, f) on the segment r _r，j+1 ) Of the h forward link key, K' _{w，r，h，j-1} For the j-1 th position keyword-file identifier pair (w, f) _r，j-1 ) H reverse link key of d _w，r，g Is the g forward chain key of segment r, d' _w，r，g The g-th reverse-link key for segment r; the client sends tau _srh Sending the data to the server;

step 303: the server sideReception of _srh Then according to τ _srh Obtaining the plaintext of the file identifier corresponding to the file w without the data deletion step, and according to the tau _srh The plaintext of the file identifier corresponding to w and subjected to the data deletion step cannot be obtained;

step 304: and the server returns all the obtained file identifier cleartexts to the client as query results.

2. The dynamic searchable encryption method according to claim 1, wherein said data deletion step further comprises:

the server sends e ₃ After the client is given, corresponding e of (w, f) in EDB ₁ 、e ₂ 、e ₃ One or more of which are not cleared.

3. The dynamic searchable encryption method according to claim 1, wherein said step 302 further comprises:

the client generates τ _srh Then, empty T _C [w]The content of (1).

4. The dynamic searchable encryption method according to claim 1, wherein said step 303 comprises:

step 3031: according to cnt and PK _w Obtaining T _S First query ciphertext and second query ciphertext of all keyword-file identifier pairs corresponding to the medium w;

step 3032: according to τ ₁ Obtaining a key word-file identifier pair corresponding to the file identifier key in the set Q, and decrypting the corresponding first query ciphertext to obtain a file identifier plaintext in the set Q;

step 3033: according to τ ₂ And obtaining a file identifier key corresponding to the keyword-file identifier pair which does not execute the data deleting step in the set R, and decrypting the corresponding first query ciphertext to obtain the file identifier plaintext in the set Q.

5. A computer device, comprising:

a memory to store instructions; and

a processor to invoke the memory-stored instructions to perform the dynamic searchable encryption method of any of claims 1-5.

6. A computer-readable storage medium having stored thereon instructions that, when executed by a processor, perform the dynamic searchable encryption method of any one of claims 1-5.

Images