CN119203220A

CN119203220A - An oblivious dynamically searchable encryption method

Info

Publication number: CN119203220A
Application number: CN202411242931.2A
Authority: CN
Inventors: 姜正涛; 温家琦; 周涵瑜; 吴正阳; 张京良
Original assignee: Communication University of China
Current assignee: Beijing Zhiheng Network Security Technology Co ltd
Priority date: 2024-09-05
Filing date: 2024-09-05
Publication date: 2024-12-27
Anticipated expiration: 2044-09-05
Also published as: CN119203220B

Abstract

The invention provides an unintentional dynamic searchable encryption method, which relates to the technical field of information security, and comprises the steps of constructing a new Labeled PSI technology by using a coding algorithm and a decoding algorithm expressed in a formal mode OKVS based on a receiver processor and a sender processor and combining a VOLE technology at a bottom layer module to obtain an intersection Z of the two parties and a corresponding label, negotiating a database updating method by a client and a server together at an application layer to dynamically update a database, negotiating a database searching method by the client and the server together to decrypt a document, and completing unintentional dynamic searchable encryption processing. The invention improves the safety and efficiency of the dynamic searchable encryption technology.

Description

Inadvertent dynamic searchable encryption method

Technical Field

The invention belongs to the technical field of information security, and particularly relates to an inadvertent dynamic searchable encryption method.

Background

In the digital economic age of information technology development, data has become a new production element, and the process of storing and processing the data gradually shifts to the cloud. But in cloud environments the user is separated from the data, the user cannot control the data, and the presence of private content prevents the full release of the data value. The data is encrypted and then stored by introducing the high-strength cipher primitives, so that the privacy security of the data can be effectively protected, but a user cannot perform meaningful operation and search operation through ciphertext data. Therefore, how to perform efficient and secure retrieval on ciphertext data becomes a challenging problem.

The searchable encryption technique (Searchable Encryption, SE) allows the user to efficiently perform retrieval operations in ciphertext. However, most of the existing SE schemes are multi-faceted static data sets, and the search index needs to be reconstructed if the stored data is updated, meanwhile, some schemes are constructed by adopting complex cipher primitives, so that the theory effect is good, the actual efficiency is extremely poor, and the applicable scenes are limited. Accordingly, scholars have proposed dynamic searchable encryption techniques (Dynamic Searchable Encryption, DSE) and inadvertent keyword search techniques (Oblivious Keyword Search, OKS) to remedy this deficiency.

DSE allows users to dynamically add or delete encrypted databases, while OKS can hide the statistics of keyword ciphertext, providing better privacy protection. OKS can be regarded as a special tagged unbalanced privacy set intersection (Labeled PSI), so that the privacy security can be better protected by designing a searchable encryption scheme based on Labeled PSI protocol.

The private collection intersection (PRIVATE SET Intersection, PSI) belongs to a specific application problem in the field of secure multiparty computing, and is one of the hot spot problems of privacy protection. PSI allows participants to compute intersections using a local data set through a series of underlying cryptographic techniques, and does not reveal any information other than intersections, which may be available to either a participant or all participants. Although PSI technology is well established, its application in the field of dynamic searchable encryption has not been studied.

From the presently disclosed codes, papers and patents, the existing DSE schemes face a series of privacy security problems such as leakage of search modes and access modes, and the like, and meanwhile, a formalized security model covering the actual capability of an attacker is lacking to prove the security of the DSE schemes, in terms of updating efficiency, index structures are frequently updated due to data insertion and deletion operations, the updating efficiency is low due to unreasonable index structures along with the continuous increase of data quantity and user quantity, and key management becomes more complex, and in terms of searching efficiency, a large number of ciphertext copies need to be transmitted by the traditional method, so that the searching communication cost is huge.

Disclosure of Invention

Aiming at the defects in the prior art, the invention provides an inadvertent dynamic searchable encryption method, which solves the problems of low efficiency, high communication overhead and query privacy leakage in the prior art when supporting dynamic data update.

In order to achieve the purpose, the technical scheme adopted by the invention is that the inadvertently dynamic searchable encryption method comprises the following steps:

S1, constructing Labeled PSI protocols based on OKVS and VOLE technical frames by using an encoding algorithm and a decoding algorithm expressed in a formal manner based on a receiver processor and a sender processor at a bottom layer module, and obtaining an intersection result Z and a corresponding label by the receiver processor, wherein the intersection result Z is a keyword set to be searched, and a document identifier set corresponding to the keyword is stored in the corresponding label;

S2, negotiating a database updating method jointly by the client and the server at the application layer, encrypting the plaintext document and completing ciphertext database updating operation, negotiating a database searching method jointly by the client and the server, completing unintentional dynamic searchability of multiple keywords based on Labeled PSI protocols, and decrypting the document after obtaining the searching result by the client.

Further, the step S1 includes the steps of:

s101, generating a random matrix M by a receiver processor according to a key value set (k, v), wherein each row of the random matrix M comprises a random block with fixed length and random starting position, k represents the key set, and v represents a value vector;

S102, according to random block elements, a coding algorithm of OKVS is expressed in a formalized mode to solve z in a linear system M.z=v, wherein z represents a coding result of a key value set after OKVS coding;

S103, recovering a value v _i corresponding to the given arbitrary key k _i by a decoding algorithm of formal representation OKVS according to the obtained z;

S104, in order to construct Labeled PSI protocols, a receiver processor encodes all keys based on OKVS and encapsulates the encoding results by using a VOLE protocol, wherein after the sender processor and the receiver processor call the VOLE protocol, the sender processor obtains parameters delta, B, the receiver processor obtains parameters A and C and satisfies C=delta A+B, labeled PSI protocols encapsulate OKVS encoding results by using random variables, the encapsulation process is that the receiver processor encapsulates A '=A+P and transmits the A' =A+P to the sender processor, and the sender processor encapsulates K=delta A '+B so that the parameters A and C=delta A' +B are satisfied:

K=ΔA'+B=Δ(A+P)+B=ΔA+B+ΔP=C+ΔP

Wherein delta represents a random scalar generated by the VOLE protocol functional module, A, B and C represent random vectors generated by the VOLE protocol functional module, C=delta A+B is satisfied, A' represents a mask after information is packaged, P represents a coding result after a dataset of a receiver processor is OKVS coded, and K represents an intermediate calculation vector of a sender processor;

S105, according to the packaging result, based on OKVS decoding algorithm of S103, by respectively calculating X ', L ' and Y ', the intersection result Z and the corresponding label are obtained by the receiver processor, and the construction of Labeled PSI protocol is completed:

Z=X'∩Y'

wherein Z represents the final intersection result of Labeled PSI protocols, X ' represents the mask ciphertext of the local set X of the sender processor, L ' represents the ciphertext set after encrypting the document identifier L, and Y ' represents the mask ciphertext of the local set Y of the receiver processor.

Still further, the step S101 includes the steps of:

a1, generating a random matrix M by a receiver processor according to a key value set (k, v), wherein each row of the random matrix M comprises a random block with a fixed length b _w and a random starting position;

a2, for each row in the random matrix M, randomly selecting s _i as a random block starting position of the ith row by a receiver processor;

a3, generating a b _w -bit random block element by using a random predictor according to a key k _i corresponding to each row i of the matrix.

Still further, the step S102 includes the steps of:

B1, sequencing by a receiver processor according to the starting position s _i of each row of random blocks in the random matrix M, and re-labeling;

B2, traversing random block elements of each row in the random matrix M by a receiver processor, and when M [ i ] [ j ] =1, processing all elements meeting M [ i '] [ j ] =1, i' > i and s _i is less than or equal to j by using the following formula:

M[i']=M[i']⊕M[i]

v[i']=v[i']⊕v[i]

wherein, mi represents the elements of the ith row and the jth column in the random matrix M, mi represents all the elements of the ith row in the random matrix M, v i ' represents the elements of the ith row in the value vector, s _i represents the initial column position of the ith row random block in the random matrix M, mi ' represents all the elements of the ith row in the random matrix M, v i represents the elements of the ith row in the value vector, mi ' j represents the elements of the jth column in the random matrix M, wherein, the jth column of the random matrix M subjected to row processing operation has only the elements of the ith row as 1, and the elements of the ith row are all 0;

And B3, according to the processing result of the step B2, solving z in the linear system by utilizing the following formula, wherein when a certain row element is 0 in the row processing process, the z is directly made to be ≡F ^m, otherwise:

z_i＝<z_i,M[i]>+v_i

Where F ^m represents a vector space with dimension m, z _i represents the i-th row element of z, and v _i represents the i-th row element in the value vector.

Still further, the step S103 includes the steps of:

c1, let v be≡0, calculate the random block start position s≡H (k) corresponding to given arbitrary key k value and element in random block Wherein v represents a value corresponding to a given arbitrary key k value, H (·) represents a random hash function, b _w represents the length of each row of random block of the random matrix M, and k represents an arbitrary key to be decoded;

C2, according to the calculation result of the step C1, for j E [1, b _w ], v++u [ j ' ]. Z [ s+j-1] is calculated as the last return value, and the recovery of the value v _i corresponding to the given arbitrary key k _i is completed, wherein j represents the column position of each row of random block in the random matrix M, u [ j ' ] represents the j ' th bit element of the random block, and s represents the starting position of the random block.

Still further, the step S104 includes the steps of:

d1, in order to construct Labeled PSI protocols, a VOLE protocol is called by both a sender processor and a receiver processor, wherein the receiver processor encodes all keys based on OKVS and encapsulates the encoding result by utilizing the VOLE protocol;

d2, after the operation of the VOLE protocol is finished, receiving and obtaining parameters delta and B by a sender processor, and receiving and obtaining parameters A and C by a receiver processor, wherein delta represents a random scalar generated by a VOLE protocol function module, A, B and C represent random vectors generated by the VOLE protocol function module, and C=delta A+B is satisfied;

D3, encapsulating the a 'by the receiver processor, and transmitting the a' to the sender processor by using the following formula:

A'=A+P

Wherein P represents the coding result of OKVS by the receiver, A' represents the mask after the information is packaged;

d4, according to a', calculating K by the sender processor using:

K=ΔA'+B=Δ(A+P)+B=ΔA+B+ΔP=C+ΔP

Where K represents the intermediate calculation vector of the sender processor and P represents the encoding result of the receiver processor dataset after OKVS encoding.

Still further, the step S105 includes the steps of:

E1, according to the encapsulation result, based on OKVS decoding algorithm of S103, the sender processor calculates X 'and L' by using the following formulas respectively:

X'={H^o(Decode(K,x)-ΔH^F(x))|x∈X}

L'={Sym_En(K_doc,l)|l∈L[x]}

Wherein, H ^o and H ^F each represent a random hash function, decode (K, X) represents a decoding operation of OKVS, K represents an intermediate calculation vector of a sender processor, X represents an element in a set X, sym_En represents a secure symmetric encryption algorithm, K _doc represents a document encryption key, lx represents a document identifier set corresponding to the element X, L represents one element in the document identifier set Lx, and X represents a set of Labeled PSI protocols used by a server;

E2, calculating Y 'by the access processor by using the following formula, and sending the Y' to the sender processor;

Y'={H^o(Decode(C,y),y)|y∈Y}

wherein Decode (C, Y) represents the decoding operation of OKVS, Y represents an element in set Y, C represents a random vector generated by the VOLE protocol;

E3, according to the X 'and the Y', calculating Z by using the following formula to obtain the result of the original data set X and Y:

Z=X'∩Y';

And E4, obtaining a corresponding label { Lz|z epsilon Z } according to Z, and completing construction of Labeled PSI protocols, wherein Lz represents a document identifier set corresponding to the intersection set element Z.

Still further, the step S2 includes the steps of:

S201, respectively generating a secret key, an empty keyword state table and an empty encryption database at a client;

s202, negotiating a database updating method by the client and the server together, encrypting the plaintext document, and completing the ciphertext database updating operation;

S203, negotiating a database searching method by the client and the server together according to the updating result, completing the unintentional dynamic searchability of the multiple keywords based on Labeled PSI protocols, and decrypting the document after obtaining the searching result by the client.

Still further, the step S202 includes the steps of:

F1, generating a series of empty lists T _w,T_kw,T_dic,T_count,T_update by the client, wherein a table T _w is used for storing keyword information in the updating process, a table T _kw is used for storing mapping from a keyword w to a keyword token kt _w, a table T _dic is used for storing ciphertext information on a document index chain DIC, a table T _count is used for storing the number of documents corresponding to the keyword w, and a table T _update is used for storing all ciphertext information in the updating process;

F2, extracting documents one by one in a document database DB by a client, calculating a table T _w by the client for any keyword w, and searching the keyword sigma [ w ] from a local keyword state table;

f3, responding to the fact that the keyword sigma [ w ] is not found, enabling sigma [ w ] ≡0, and calculating to obtain the latest update times n ^update of the keyword w;

F4, according to the calculation result of the step F3, the client searches (kt _w,st_w)←T_kw [ w ] from the table T _kw, and if not found, kt _w←F(K_s, w) is calculated, And T _kw←T_kw∪{w,(kt_w,st_w), where T _kw [ w ] represents the mapping of the keyword w to the keyword token kt _w and the search token st _w, F (K _s, w) represents a pseudo-random function, H () represents a hash function,The latest update times of the keyword w are represented;

F5, according to the calculation result of the step F4, searching T _count [ w ] from a table T _count by the client, and in response to the fact that the T _count [ w ] is not found, making T _count [ w ] ≡0 and obtaining c _w←T_count [ w ] +1, wherein T _count [ w ] represents and stores a list of the number of document identifiers corresponding to the keyword w, and c _w represents the number of documents corresponding to the keyword w in the updating operation process;

F6, according to the calculation result of the step F5, calculating to obtain calculation document encryption information loc (i.e. H (st _w,c_w)、eid←Sym_En(K_doc, id)) and T _dic[st_w]←T_dic[st_w { (loc, eid) }, wherein loc represents the address of each node of the document index chain DIC, eid represents the ciphertext encrypted by the document identifier id, sym_En represents symmetric encryption operation, K _doc represents a document encryption key, and T _dic[st_w represents a document index chain corresponding to the search token st _w;

f7, for any keyword w epsilon T _w, calculating sigma [ w ] ++1, (kt _w,st_w)←T_kw[w]、c_w←T_count [ w ] and value ≡G (st _w,1^λ)⊕(op||c_w)) by a client, saving (kt _w,(value,T_dic[st_w ])) in a table T _update, and sending the table T _update to a server by the client, wherein all keyword sets involved in the updating process are saved in the table T _w, sigma [ w ] represents a client local keyword state table, c _w represents the number of documents corresponding to the keyword w in the updating process, T _count [ w ] represents the number of documents corresponding to the keyword w, value represents an operation information mask of the updating process, G () represents a hash function, op=0 represents a document adding operation, op=1 represents a document deleting operation, and lambda represents a calculation safety parameter;

and F8, merging the table T _update with the encryption database EDB by the server to finish updating operation of the ciphertext database.

Still further, the step S203 includes the steps of:

G1, generating Y 'by a client according to an updating result, R' is { }, kt _w←F(K_s,w)、st_w←H(kt_w and sigma [ w ] are calculated for any keyword w, and a search token st _w is stored to Y ', wherein Y' represents a set of the client for Labeled PSI protocol, R represents a final result set, kt _w represents a keyword token, F (K _s, w) represents a pseudo-random function, st _w represents a search token, H () represents a hash function, sigma [ w ] represents a keyword, and kt _w represents a keyword token;

G2, generating X ", lx≡ { }, for the encryption database EDB, calculating st _w←H(kt_w,c_i by the server, wherein X" represents the set of servers for Labeled PSI protocol, lx represents the set of document identifiers for the corresponding element X, c _i represents the c _i th node;

G3, according to the generated search token st _w, op and c _w are obtained through calculation by using the following formula:

(op||c_w)←value⊕G(st_w,1^λ)

Wherein c _w represents the number of documents corresponding to the keyword w in the update operation process, value represents an operation information mask corresponding to the update process, G () represents a hash function, op represents an operation type, op=0 represents a document adding operation, op=1 represents a document deleting operation, and λ represents a calculation security parameter;

G4, from 1 to c _w, calculating to obtain loc (H) (st _w, j) and Eid (EDB) (loc), wherein loc represents the address of the j-th node of the document index chain DIC, and the encrypted ciphertext of the Eid document identifier id, and EDB represents an encrypted database;

G5, saving, by the server, the search token st _w to X ", and adding the encrypted document identifier of op=0 to lx, removing the document encrypted identifier of op=1 from lx;

G6, the client and the server call Labeled PSI the protocol together, after Labeled PSI the protocol is operated, the client receives the final result intersection I=X '-U Y' and { L [ Y '] |y' ∈I } corresponding to the intersection element, wherein L [ Y '] represents the encrypted document to be searched by the client, and Y' represents the intersection element;

and G7, saving the L [ y' ] to the set R by the client, decrypting the document by using the key, and completing the encryption processing of the unintentional dynamic searchable.

The invention has the beneficial effects that:

(1) The invention is applicable to new cryptography parameters, the research of PSI in the field of searchable encryption is still blank in the prior art, and the invention provides a new and effective careless keyword search protocol; compared with the traditional dynamic searchable encryption protocol, the invention supports multi-keyword search, realizes forward security and backward security, and protects privacy security of a search mode in the search process;

(2) Compared with the OKS protocol, the method has the advantages that the number of ciphertext is equal to the product of the number of keywords and the number of files, the communication cost is only equal to the number of files corresponding to the query keyword set, the communication efficiency is high, the formal security model is utilized to prove the security of the protocol, namely, the random predictive model is utilized to simulate common attacks, such as keyword attack selection, and the security of the protocol is proved.

Drawings

FIG. 1 is a flow chart of the method of the present invention.

FIG. 2 is a schematic diagram of a dynamic searchable encryption system model that satisfies a single read-single write architecture according to an embodiment of the present invention.

Detailed Description

The following description of the embodiments of the present invention is provided to facilitate understanding of the present invention by those skilled in the art, but it should be understood that the present invention is not limited to the scope of the embodiments, and all the inventions which make use of the inventive concept are protected by the spirit and scope of the present invention as defined and defined in the appended claims to those skilled in the art.

Examples

As shown in fig. 1 to 2, the invention provides an inadvertent dynamic searchable encryption method, which comprises a bottom layer module (Labeled PSI) and an application layer, wherein the bottom layer module is mainly used for supporting the implementation of an application layer search algorithm, and the technical structure of the bottom layer module consists of Oblivious Key-Value Stores (OKVS for inadvertent key Value storage) and Vector Oblivious Linear Evaluation (VOLE for transparent vector linear estimation), and mainly comprises two entities, namely a Sender processor Sender and a Receiver processor Receiver. Wherein, the Sender processor Sender holds a data set X, and for any X epsilon X, the Sender processor Sender holds a group of corresponding tag sets { Lx|x epsilon X }, and the Receiver processor Receiver holds a data set Y; the technical architecture consists of Oblivious Key-Value Stores (OKVS) and Vector Oblivious Linear Evaluation (VOLE). The dynamic searchable encryption scheme related to the invention can be divided into three stages of Setup, update and Search, and is based on a special secondary index structure, wherein the index structure comprises keyword index chains (Keyword index chain, KIC) and document index chains (Document index chain, DIC), the keyword index chains KIC are used for storing keyword Update information, the document index chains DIC are used for storing encrypted document information, each keyword w corresponds to one keyword index chain KIC, each keyword index chain KIC comprises n nodes, each node represents one Update operation of the keyword, and the node is linked with one document index chain DIC, and each node of the document index chains DIC corresponds to one encrypted keyword/document pair. The Labeled PSI protocol is a labeled unbalanced privacy set intersection technology. The implementation method is as follows:

S1, constructing Labeled PSI protocols based on OKVS and VOLE technical frameworks by using an encoding algorithm and a decoding algorithm expressed in a formal manner based on a receiver processor and a sender processor at a bottom layer module, and obtaining an intersection result Z and a corresponding label by the receiver processor, wherein the intersection result Z is a keyword set to be searched, and a document identifier set corresponding to the keyword is stored in the corresponding label, and the implementation method is as follows:

S101, generating a random matrix M by a receiver processor according to a key value set (k, v), wherein each row of the random matrix M comprises a random block with fixed length and random starting position, k represents the key set, and v represents a value vector, and the implementation method is as follows:

In this embodiment, the Receiver processor Receiver generates a random matrix M ε F ^n×m, each row of which includes a random block of length b _w, except that the elements in the random block are randomly taken from {0,1}, the elements outside the block are all 0, for each row i ε [1, n ] in the random matrix, the Receiver processor Receiver randomly selects s _i←H(k_i) as the starting position of the random block for the ith row, where k _i represents the ith key, and then generates the random block elements of bits b _w using a random predictor

S102, according to random block elements, a coding algorithm of OKVS is expressed in a formalized mode to solve z in a linear system M.z=v, wherein z represents a coding result of a key value set after OKVS coding, and the implementation method is as follows:

z_i＝<z_i,M[i]>+v_i

In this embodiment, the encoding algorithm Encode of OKVS is calculated in this step, OKVS is expressed in a formalized form, i.e., the linear system mxz=v needs to be solved, where v= { v ₁,v₂,...,v_n }, M is a random matrix generated from { k ₁,k₂,...,k_n } in I, v represents a value set, v _n represents an n-th element, k _n represents an n-th element, and I represents a key value set;

The Receiver processor Receiver calculates P=OKVS.Encode (I), wherein the input parameter is I= { (k ₁,v₁),(k₂,v₂),...,(k_n,v_n) }, P represents information coded by OKVS coding algorithm, k _n,v_n represents nth key and value respectively, firstly the Receiver processor Receiver needs to order according to the starting position s _i of each row of random block of the random matrix M and re-label, s ₁≤s₂≤...≤s_n,s_n represents the starting position of the nth row of random block in the random matrix M, then the Receiver processor Receiver traverses the random block element j of each row of the random matrix, if M [ I ] [ j ] = 1, all rows I 'satisfying I' > I & s _i′ +.j are processed:

Finally, solving the solution z of the linear system according to z _i＝<z_i,M[i]>+v_i, and if a certain row element is found to be 0 in the row processing process, directly letting z+.F ^m.

S103, recovering a value v _i corresponding to a given arbitrary key k _i by a decoding algorithm of formal representation OKVS according to the obtained z, wherein the implementation method is as follows:

In this embodiment, this step calculates OKVS a decoding algorithm Decode, which in formalized representation OKVS, i.e., given an arbitrary key value k, the decoder can recover its corresponding value v;

the decoding party has a solution z of a linear system and an arbitrary key value k; let v+.0, the decoder first calculates the random block start position s+.H (k) corresponding to the key and the elements in the block Then for j e 1, b _w, and calculating v ≡ v+u [ j ] & z [ s+j-1] as the last return value.

K=ΔA'+B=Δ(A+P)+B=ΔA+B+ΔP=C+ΔP

Wherein Δ represents a random scalar generated by the VOLE protocol function module, a, B, and C each represent a random vector generated by the VOLE protocol function module, and satisfy c=Δa+b, a' represents a mask after information is encapsulated, K represents an intermediate calculation vector of the sender processor, and P represents an encoding result after the receiver processor dataset is OKVS encoded, which is implemented as follows:

A'=A+P

d4, according to a', calculating K by the sender processor using:

K=ΔA'+B=Δ(A+P)+B=ΔA+B+ΔP=C+ΔP

Z=X'∩Y'

wherein, Z represents Labeled PSI final intersection result of protocol, X ' represents mask ciphertext of local set X of sender processor, L ' represents ciphertext set after encrypting document identifier L, namely encrypted document identifier corresponding to keyword in encryption database EDB, Y ' represents mask ciphertext of local set Y of receiver processor, and the implementation method is as follows:

X'={H^o(Decode(K,x)-ΔH^F(x))|x∈X}

L'={Sym_En(K_doc,l)|l∈L[x]}

Wherein, H ^o and H ^F each represent a random hash function, decode (K, X) represents a decoding operation of OKVS, K represents an intermediate calculation vector of a sender processor, X represents an element in a set X, namely a keyword, sym_En represents a secure symmetric encryption algorithm, K _doc represents a document encryption key, lx represents a set of document identifiers corresponding to the element X, L represents one element in the set of document identifiers Lx, and X represents a set of Labeled PSI protocols used by a server;

Y'={H^°(Decode(C,y),y)|y∈Y}

wherein Decode (C, Y) represents the decoding operation of OKVS, Y represents an element in the set Y, i.e., a keyword, C represents a random vector generated by the VOLE protocol;

Z=X'∩Y'

S2, negotiating a database updating method by the client and the server together at an application layer, encrypting a plaintext document and completing ciphertext database updating operation, negotiating a database searching method by the client and the server together, completing unintentional dynamic searchability of multiple keywords based on Labeled PSI protocols, decrypting the document after obtaining a searching result by the client, and realizing the method as follows:

In this embodiment, the Client generates the key { K _s,K_doc }, an empty key state table σ, and an empty encryption database EDB.

S202, respectively generating a secret key, an empty keyword state table and an empty encryption database at a client, wherein the implementation method comprises the following steps:

F7, for any keyword w E T _w, computing sigma [ w ] ≡sigma [ w ] +1, (kt _w,st_w)←T_kw[w]、c_w←T_count [ w ] and And (kt _w,(value,T_dic[st_w ])) is saved in a table T _update, and the table T _update is sent to a server by a client, wherein the table T _w stores all keyword sets involved in the updating process, sigma [ w ] represents a client local keyword state table, c _w represents the number of documents corresponding to the keyword w in the updating process, T _count [ w ] represents the number of documents corresponding to the keyword w, value represents an operation information mask of the updating process, G () represents a hash function, op represents an operation type, op=0 represents a document adding operation, op=1 represents a document deleting operation, lambda represents a calculation security parameter;

In this embodiment, the Client and the Server together negotiate a database Update algorithm Update.

In this embodiment, the Client first generates a series of empty lists T _w,T_kw,T_dic,T_count,T_update, where T _w is used to store keyword information in the current update process, T _kw is used to store a mapping from the keyword w to the keyword token kt _w, T _dic is used to store ciphertext information on the DIC, T _count is used to store the number of documents corresponding to the keyword w, and T _update is used to store all ciphertext information in the current update process;

client first reads from document database The method comprises the steps of extracting documents doc= (id, W _id) one by one, calculating T _w←T_w { W } for any W epsilon W _id by a Client, searching a local keyword state table for the keyword sigma [ W ], if not, enabling sigma [ W ]. Times of 0 to be found, obtaining the latest update times n ^update +% sigma [ W ] +1 of the keyword W, and searching (kt _w,st_w)←T_kw [ W ] from a list T _kw by the Client, if not, calculating kt _w←F(K_s, W), and,T _kw←T_kw∪{w,(kt_w,st_w); the Client searches T _count [ w ] from the list T _count, if not, T _count [ w ] ≡0 is caused to obtain c _w←T_count [ w ] +1, and then document encryption information loc≡H (st _w,c_w)、eid←Sym_En(K_doc, id) and T _dic[st_w]←T_dic[st_w ≡ { (loc, eid) } are calculated;

Table T _w holds all keyword sets in the current update process, and for any w ε T _w, client computes σ [ w ] ≡σ [ w ] +1, (kt _w,st_w)←T_kw[w]、c_w←T_count [ w ] and And (kt _w,(value,T_dic[st_w ])) is saved in a table T _update, finally, the Client sends the list T _update to the Server, and the Server merges the list T _update with the encryption database EDB, namely EDB≡EDB u T _update.

S203, negotiating a database searching method by the client and the server together according to the updating result, completing the unintentional dynamic searchability of the multiple keywords based on Labeled PSI protocol, decrypting the document after obtaining the searching result by the client, and realizing the method as follows:

(op||c_w)←value⊕G(st_w,1^λ)

In this embodiment, the Client and the Server together negotiate a database Search algorithm Search.

In this embodiment, the Client generates Y ", r≡ { }, calculates kt _w←F(K_s,w)、st_w←H(kt_w, σ [ w ]) for any w∈q, and saves the search token st _w to Y"; the Server generates X ", lx ] ≡ { }, calculates st _w←H(kt_w, i) for the encryption database EDB, where i=1, 2, and calculates from the generated st _w Op and c _w are obtained, then loc≡H (st _w, j), eid≡EDB [ loc ], where j ε [1, c _w ]; the Server saves the search token st _w to X ", adds the encrypted document identifier of op=0 to Lx, and removes the document encrypted identifier of op=1 from Lx; the Client and the Server call Labeled PSI the protocol together, wherein the Client plays the role of Receiver processor Receiver, the Server plays the role of Sender processor Sender, after the protocol runs, the Client receives the final result intersection I=X". U.Y "and { L [ Y '] |y'. E.I } corresponding to the intersection element, the Client saves the final result L [ Y ] into the set R, and decrypts the document by using the key K _doc.

In this embodiment, the present invention is a dynamic searchable encryption model based on a single read single write system model. The invention can be divided into three stages of Setup, update and Search, wherein in the Update stage, the constructed secondary index structure comprises a keyword index chain KIC and a document index chain DIC, namely the part of a dotted line box in figure 2, and in the Search stage, keyword searching is carried out by calling Labeled PSI modules.

In the embodiment, the method and the device are mainly applicable to dynamic data updating scenes and are divided into two entities, namely a Client and a Server. The data document doc= (id, W _id) contains a unique document identifier id e {0,1} ^* and a set of keywords W _id, in a plaintext databaseIn (c), the document identifier set corresponding to the keyword W is set as DB (W) = { id|w e W _id }. In Setup phase, client generates two symmetric encryption keys K _s and K _doc, an empty keyword state table σ and an empty ciphertext database EDB, where K _s is used for encryption generation of various tokens, K _doc is used for encryption of document identifiers, σ is used for saving the number of updates of each keyword

In this embodiment, in order to improve data updating efficiency and reduce communication complexity, the present invention optimizes a traditional inverted index structure and adjusts the structure into a secondary index structure, which includes a keyword index chain KIC and a document index chain DIC. If each update operation is only for one keyword/document pair, the length of the keyword index chain KIC will become longer and one keyword/document set at a time can be processed by introducing the document index chain DIC.

Due to plaintext databasesSimilar to the forward index structure, to encrypt it according to the index structure, a temporary empty mapping table T _w,T_kw,T_dic,T_count,T_update needs to be introduced, and each mapping table function is as described above, so the Update phase Client includes the following steps:

Step S1, client side is from plaintext database Extracting a document doc= (id, W _id), and storing a keyword W corresponding to the document to T _w;

step S2, calculating the latest update times of the keyword w If the keyword w information is not stored in the keyword state table sigma in the process, making sigma [ w ] ≡0;

Step S3, if the information of the keyword w is stored in the mapping table T _kw, directly extracting (kt _w,st_w)←T_kw [ w ]; if the keyword w is processed for the first time, calculating a keyword token kt _w and a search token st _w corresponding to the keyword w, wherein the formula is as follows:

and saves it into mapping table T _kw, i.e., T _kw←T_kw∪{w,(kt_w,st_w);

Step S4, calculating the number c _w of document identifiers added to DIC by the keyword w in the round, if the information of the keyword w is stored in the mapping table T _count, making c _w←T_count [ w ] +1, otherwise, making T _count [ w ] > be less than 0, and calculating the value of c _w;

Step S5, calculating encrypted document information loc≡H (st _w,c_w)、eid←Sym_En(K_doc, id) and T _dic[st_w]←T_dic[st_w { (loc, eid) };

Repeating S1 to S5 until all documents in the plaintext document database DB are processed, wherein a table T _w stores all keyword sets in the updating process, and aiming at all w epsilon T _w, constructing a ciphertext database EDB according to the index structure;

Step S6, calculating sigma [ w ] ≡sigma [ w ] +1, (kt _w,st_w)←T_kw[w]、c_w←T_count [ w ] and value ≡G (st _w,1^λ)⊕(op||c_w) for any keyword w epsilon T _w by the Client, wherein value is information stored by a KIC node and comprises the corresponding keyword w update type (op=0 is an adding operation and op=1 is a deleting operation) and the number of documents corresponding to the keyword w c _w in the updating process, and storing (kt _w,(value,T_dic[st_w) in a table T _update by the Client and sending the information to a Server.

The Update phase Server updates the local ciphertext database EDB according to the table T _update.

Because Labeled PSI protocol is used to ensure the safe operation of the Search mechanism in the Search stage, some safety parameters need to be preset before the formal operation of the protocol to initialize the data set, the Server acts as a Sender role and the Client acts as a Receiver role in the protocol operation stage. In the dynamic searchable encryption Search mechanism provided by the embodiment of the present invention, the Search stage needs the Client side and the Server Fang Shou to generate the data set of locally running Labeled PSI protocol, and mainly includes the following steps:

step S1, client generates a local data set Y' according to a search keyword set Q, and calculates kt _w←F(K_s, w) and st _w←H(kt_w, sigma [ w ] for any keyword w epsilon Q, wherein F is a pseudo-random function, H is a random hash function, sigma is a keyword state table locally held by the Client;

Step S2, the Server generates a local data set X 'according to the ciphertext database EDB, generates a label set L [ X ] corresponding to any X E X', calculates st _w←H(kt_w, i) and i=1, 2 according to the generated st _w, calculates (op|c _w)←value⊕G(st_w,1^λ) to obtain operation types op of all nodes on the KIC and the number c _w of the nodes corresponding to the DIC, and then calculates

Loc≡h (st _w,j),j＝1,2,...,c_w and eid≡edb [ loc ];

And step S3, the Server saves all st _w to a data set X' and processes the documents corresponding to the keywords according to the operation type op. Specifically, the encrypted document identifier of op=0 is saved to the data set L [ x ], and the encrypted document identifier of op=1 is removed from the data set L [ x ];

step S4, the Client and the Server call Labeled PSI the protocol together, wherein the Client plays the role of Receiver processor Receiver, the Server plays the role of Sender processor Sender, the protocol operation is finished, the Client receives the final result intersection I=X ', U Y' and { L [ Y '] |y' ∈I } corresponding to the intersection element;

Because the Client uses the latest updating times sigma [ w ] of each keyword to dynamically generate a search token st _w, the Client cannot obtain a search result by using the previous search token st _w', and the forward privacy security of a user is ensured;

and S5, the Client uses the key K _doc to decrypt the data set L [ y' ] to obtain a final plaintext result.

Those of ordinary skill in the art will appreciate that the embodiments described herein are intended to aid the reader in understanding the practice of the invention and that the scope of the invention is not limited to such specific statements and embodiments. Those of ordinary skill in the art can make various other specific modifications and combinations from the teachings of the present disclosure without departing from the spirit thereof, and such modifications and combinations remain within the scope of the present disclosure.

Claims

1. A method for inadvertent dynamic searchable encryption, characterized in that it comprises the following steps:

S1. In the bottom layer module, based on the receiving processor and the sending processor, the encoding algorithm and decoding algorithm of the OKVS are formally represented, and the Labeled PSI protocol is constructed based on the OKVS and VOLE technical framework. The receiving processor obtains the intersection result Z and the corresponding label, where the intersection result Z is the keyword set to be searched, and the corresponding label stores the document identifier set corresponding to the keyword;

S2. At the application layer, the client and the server jointly negotiate a database update method, encrypt the plaintext document, and complete the ciphertext database update operation; and the client and the server jointly negotiate a database search method, complete multi-keyword dynamic search based on the Labeled PSI protocol, and the client decrypts the document after obtaining the search results.

2. The inadvertent dynamic searchable encryption method according to claim 1, wherein step S1 comprises the following steps:

S101, a receiving processor generates a random matrix M according to a key value set (k, v), wherein each row of the random matrix M includes a random block of a fixed length and a random starting position, k represents the key set, and v represents the value vector;

S102, formalizing the encoding algorithm of OKVS according to the random block elements to solve z in the linear system M·z=v; wherein z represents the encoding result of the key value set after OKVS encoding;

S103, based on the solved z, a decoding algorithm of OKVS is formally represented to restore the value _vi corresponding to any given key k _i ;

S104. To construct the Labeled PSI protocol, the receiving processor encodes all keys based on OKVS and encapsulates the encoding results using the VOLE protocol. After the sending processor and the receiving processor call the VOLE protocol, the sending processor obtains parameters Δ,B, and the receiving processor obtains parameters A,C, and C=ΔA+B. The Labeled PSI protocol encapsulates the OKVS encoding results using random variables. The encapsulation process is as follows: the receiving processor encapsulates A'=A+P and transmits it to the sending processor; the sending processor encapsulates K=ΔA'+B, so that it satisfies:

K=ΔA'+B=Δ(A+P)+B=ΔA+B+ΔP=C+ΔP

Wherein, Δ represents the random scalar generated by the VOLE protocol function module, A, B, and C all represent random vectors generated by the VOLE protocol function module, and satisfy C = ΔA + B, A' represents the mask after the information is encapsulated, P represents the encoding result of the receiving processor data set after OKVS encoding, and K represents the intermediate calculation vector of the sending processor;

S105. According to the encapsulation result, based on the OKVS decoding algorithm of S103, by calculating X', L' and Y' respectively, the receiving processor obtains the intersection result Z and the corresponding label, and completes the construction of the Labeled PSI protocol:

Z＝X'∩Y'

Among them, Z represents the final intersection result of the Labeled PSI protocol, X' represents the masked ciphertext of the local set X of the sender processor, L' represents the ciphertext set after the document identifier l is encrypted, and Y' represents the masked ciphertext of the local set Y of the receiver processor.

3. The inadvertent dynamic searchable encryption method according to claim 2, wherein step S101 comprises the following steps:

A1. The receiving processor generates a random matrix M according to the key value set (k, v), wherein each row of the random matrix M includes a random block with a fixed length of b _w and a random starting position;

A2. For each row in the random matrix M, the receiving processor randomly selects _si as the starting position of the random block in the i-th row;

A3. According to the key k _i corresponding to each row i of the matrix, a random oracle is used to generate a random block element of b _w bits.

4. The inadvertent dynamic searchable encryption method according to claim 2, wherein step S102 comprises the following steps:

B1. The receiving processor sorts the random blocks in each row in the random matrix M according to their starting positions _si and renumbers them;

B2. The receiving processor traverses the random block elements of each row in the random matrix M. When M[i][j]=1, the following formula is used to process all elements that satisfy M[i'][j]=1, i'>i and s _i ≤j:

Wherein, M[i][j] represents the element in the i-th row and j-th column of the random matrix M, M[i] represents all elements in the i-th row of the random matrix M, v[i'] represents the element in the i'th row of the value vector, _si represents the starting column position of the random block in the i-th row of the random matrix M, M[i'] represents all elements in the i'th row of the random matrix M, v[i] represents the element in the i-th row of the value vector, and M[i'][j] represents the element in the i'th row and j-th column of the random matrix M. Among them, after the row processing operation, only the elements in the i-th row of the j-th column of the random matrix M are 1, and the elements in the i'>i row are all 0;

B3. According to the processing result of step B2, the following formula is used to solve z in the linear system, wherein, when there is a row whose elements are all 0 during the row processing, z←F ^m is directly set; otherwise:

z _i = <z _i ,M[i]> + v _i

Where ^Fm represents a vector space of dimension m, _zi represents the i-th row element of z, and _vi represents the i-th row element in the value vector.

5. The inadvertent dynamic searchable encryption method according to claim 2, wherein step S103 comprises the following steps:

C1. Let v←0, calculate the starting position s←H(k) of the random block and the element in the random block corresponding to any key k value Where v represents the value corresponding to a given arbitrary key k, H(·) represents a random hash function, _bw represents the length of each random block in the random matrix M, and k represents an arbitrary key to be decoded;

C2. According to the calculation result of step C1, for j∈[1, _bw ], calculate v←v+u[j']·z[s+j-1] as the final return value to complete the recovery of the value _vi corresponding to any given key _ki , where j represents the column position of each row of the random block in the random matrix M, u[j'] represents the j'th element of the random block, and s represents the starting position of the random block.

6. The inadvertent dynamic searchable encryption method according to claim 2, wherein step S104 comprises the following steps:

D1. To build the Labeled PSI protocol, the sending processor and the receiving processor both call the VOLE protocol, where the receiving processor encodes all keys based on OKVS and encapsulates the encoding results using the VOLE protocol;

D2. After the VOLE protocol runs, the sending processor receives and obtains the parameter Δ,B, and the receiving processor receives and obtains the parameter A,C, where Δ represents the random scalar generated by the VOLE protocol function module, and A, B, and C all represent the random vector generated by the VOLE protocol function module, and satisfy C = ΔA + B;

D3. The receiving processor uses the following formula to encapsulate A' and sends A' to the sending processor:

A'＝A+P

Wherein, P represents the encoding result of OKVS performed by the receiver, and A' represents the mask after encapsulating the information;

D4. Based on A', the sending processor calculates K using the following formula:

K=ΔA'+B=Δ(A+P)+B=ΔA+B+ΔP=C+ΔP

Wherein, K represents the intermediate calculation vector of the sending processor, and P represents the encoding result of the receiving processor data set after OKVS encoding.

7. The inadvertent dynamic searchable encryption method according to claim 2, wherein step S105 comprises the following steps:

E1. According to the encapsulation result, based on the OKVS decoding algorithm of S103, the sending processor calculates X' and L' using the following formulas:

X'＝{H°(Decode(K,x)-ΔH ^F (x))|x∈X}

L'＝{Sym_En(K _doc ,l)|l∈L[x]}

Where H° and H ^F both represent random hash functions, Decode(K,x) represents the decoding operation of OKVS, K represents the intermediate calculation vector of the sender processor, x represents an element in the set X, Sym_En represents a secure symmetric encryption algorithm, K _doc represents a document encryption key, L[x] represents the document identifier set corresponding to the element x, l represents an element in the document identifier set L[x], and X represents the set used by the server for the Labeled PSI protocol;

E2. The access-side processor calculates Y' using the following formula and sends it to the sender processor;

Y'＝{H°(Decode(C,y),y)|y∈Y}

Where Decode(C,y) represents the decoding operation of OKVS, y represents the element in the set Y, and C represents the random vector generated by the VOLE protocol;

E3. According to X' and Y', use the following formula to calculate Z, that is, the result of the original data set X∩Y:

Z＝X'∩Y'

E4. According to Z, the corresponding label {L[z]|z∈Z} is obtained to complete the construction of the Labeled PSI protocol, where L[z] represents the set of document identifiers corresponding to the intersection set element z.

8. The inadvertent dynamic searchable encryption method according to claim 1, wherein step S2 comprises the following steps:

S201, generating a key, an empty keyword status table and an empty encryption database on the client;

S202, the client and the server jointly negotiate a database update method, encrypt the plaintext document, and complete the ciphertext database update operation;

S203. According to the update result, the client and the server jointly negotiate a database search method, and perform multi-keyword dynamic search based on the LabeledPSI protocol. After the client obtains the search result, it decrypts the document.

9. The inadvertent dynamic searchable encryption method according to claim 8, wherein step S202 comprises the following steps:

F1. The client generates a series of empty lists T _w ,T _kw ,T _dic ,T _count ,T _update , where table T _w is used to store keyword information in this update process, table T _kw is used to store the mapping of keyword w to keyword token kt _w , table T _dic is used to store ciphertext information on the document index chain DIC, table T _count is used to store the number of documents corresponding to keyword w, and table T _update is used to store all ciphertext information in this update process;

F2. The client extracts documents one by one from the document database DB. For any keyword w, the client calculates the table T _w and searches for the keyword σ[w] from the local keyword state table.

F3. In response to the keyword σ[w] not being found, σ[w]←0 is set, and the latest update number of the keyword w is calculated n ^update ←σ[w]+1;

F4. According to the calculation result of step F3, the client searches for (kt _w ,st _w )←T _kw [w] in the table T _kw . If it is not found, kt _w ←F(K _s ,w) is calculated. and T _kw ←T _kw ∪{w,(kt _w ,st _w )}, where T _kw [w] represents the mapping of keyword w to keyword token kt _w and search token st _w , F(K _s ,w) represents a pseudo-random function, H() represents a hash function, Indicates the latest update times of keyword w;

F5. According to the calculation result of step F4, the client searches for T _count [w] from table T _count . If it is not found, T _count [w] is set to ← 0, and c _w ← T _count [w] + 1 is obtained, where T _count [w] represents a list of document identifiers corresponding to keyword w, and c _w represents the number of documents corresponding to keyword w during this update operation.

F6. According to the calculation result of step F5, the document encryption information loc←H(st _w ,c _w ), eid←Sym_En(K _doc ,id) and T _dic [st _w ]←T _dic [st _w ]∪{(loc,eid)} are calculated, where loc represents the address of each node of the document index chain DIC, eid represents the encrypted ciphertext of the document identifier id, Sym_En represents the symmetric encryption operation, K _doc represents the document encryption key, and T _dic [st _w ] represents the document index chain corresponding to the search token st _w ;

F7. For any keyword w∈T _w , the client calculates σ[w]←σ[w]+1, (kt _w ,st _w )←T _kw [w], c _w ←T _count [w], and value←G(st _w ,1 ^λ )⊕(op||c _w ), and saves (kt _w ,(value,T _dic [st _w ])) to table T _update , and the client sends table T _update to the server, where table T _w stores all keyword sets involved in this update process, σ[w] represents the client local keyword status table, c _w represents the number of documents corresponding to keyword w during this update operation, T _count [w] represents the number of documents corresponding to keyword w, value represents the operation information mask of this update process, G() represents the hash function, op represents the operation type, op＝0 represents the document addition operation, op＝1 represents the document deletion operation, and λ represents the calculation security parameter;

F8. The server merges table T _update with the encrypted database EDB to complete the update operation on the ciphertext database.

10. The inadvertent dynamic searchable encryption method according to claim 8, wherein step S203 comprises the following steps:

G1. According to the update result, the client generates Y”, R←{}, and for any keyword w, calculates kt _w ←F(K _s ,w), st _w ←H(kt _w ,σ[w]), and saves the search token st _w to Y”, where Y” represents the set used by the client for the Labeled PSI protocol, R represents the final result set, kt _w represents the keyword token, F(K _s ,w) represents the pseudo-random function, st _w represents the search token, H() represents the hash function, σ[w] represents the keyword, and kt _w represents the keyword token;

G2. The server generates X”, L[x]←{}, and for the encrypted database EDB, calculates st _w ←H(kt _w , _ci ), where X” represents the set used by the server for the Labeled PSI protocol, L[x] represents the document identifier set corresponding to the element x, and _ci represents the ci _- th node;

G3. According to the generated search token st _w , op and c _w are calculated using the following formula:

(op||c _w )←value⊕G(st _w ,1 ^λ )

Where c _w represents the number of documents corresponding to keyword w during this update operation, value represents the operation information mask of the corresponding update process, G() represents the hash function, op represents the operation type, op=0 represents the document adding operation, op=1 represents the document deleting operation, and λ represents the calculation security parameter;

G4. From 1 to c _w , loc←H(st _w ,j) and Eid←EDB[loc] are calculated, where loc represents the address of the j-th node in the document index chain DIC, Eid is the encrypted ciphertext of the document identifier id, and EDB represents the encrypted database;

G5. The server saves the search token st _w to X", adds the encrypted document identifier of op=0 to L[x], and removes the encrypted document identifier of op=1 from L[x];

G6. The client and the server jointly call the Labeled PSI protocol. After the Labeled PSI protocol runs, the client receives the final result intersection I = X”∩Y” and {L[y']|y'∈I} corresponding to the intersection element, where L[y'] represents the encrypted document to be searched by the client, and y' represents the intersection set element;

G7. The client saves L[y'] to the set R and uses the key to decrypt the document, completing the encryption processing of the inadvertent dynamic searchable document.