CN115391803A - Encrypted hybrid index tree generation and privacy protection space-time contact query method - Google Patents

Abstract

The invention discloses a space-time contact query method for generating an encrypted mixed index tree and protecting privacy, which comprises the following steps: acquiring a plurality of groups of original space-time data, wherein each group of original space-time data comprises original space position data and original time data; encoding the original spatial position data by using a Hilbert curve to obtain a plurality of groups of space-time processing data including spatial encoding data and original time data; generating a prefix code family of the space coding data of each group of the space-time processing data; taking each group of space-time processing data and a prefix coding family of each group of space-time processing data as leaf nodes of the mixed index tree; combining different prefix coding families, and generating non-leaf nodes layer by layer from bottom to top; each parent node contains the prefix code family or the merged code family of all the child nodes; respectively generating a bloom filter of each leaf node and each non-leaf node to obtain a mixed index tree; and encrypting the bloom filter to obtain an encrypted mixed index tree.

Description

Generation of an encrypted hybrid index tree and privacy-preserving spatio-temporal contact query method

technical field

The invention belongs to the technical field of communication, and in particular relates to an encrypted hybrid index tree generation and privacy-protected space-time contact query method.

Background technique

Now that the means of attacking cloud servers are becoming more and more systematic, and the attack threshold is gradually lowering, the concern about data privacy leakage in cloud servers is increasing, and the time-space contact query is more likely to cause the leakage of user itinerary. However, in the face of such a large amount of spatio-temporal data, how to safely and efficiently complete the above tasks has become the top priority, and currently there is no solution that can perform spatio-temporal contact queries and take into account both efficiency and safety.

The existing scheme closest to the present invention is to search for privacy-preserving spatial text keywords. A solution based on grayscale and bitmap coding proposed by Wang et al. is called PBRQ. However, PBRQ has the following disadvantages:

1) Unable to support privacy-protected spatio-temporal intersection query: only for spatial keyword search, when the data set contains time and space information, it can’t do anything.

2) Low efficiency in the face of large-scale data: PBRQ responds slowly to massive data requests, and cannot achieve the efficiency of flow adjustment work. Specifically, PBRQ takes 3.14 seconds to obtain query results from 1*10^5 ciphertext objects, which is not suitable for a large number of data sets and is too inefficient.

Contents of the invention

In order to solve the above-mentioned problems in the related technologies, the present invention provides an encrypted hybrid index tree generation and privacy-protected spatio-temporal contact query method. The technical problem to be solved in the present invention is realized through the following technical solutions:

The present invention provides a method for generating an encrypted hybrid index tree, including:

Acquiring multiple sets of original spatio-temporal data of multiple objects; each set of original spatio-temporal data includes original spatial position data, and original time data corresponding to the original spatial position data;

Encoding the original spatial position data by using a Hilbert curve to obtain multiple sets of spatiotemporal processing data including spatial encoding data and the original time data;

Prefix encoding is performed on the spatial encoding data in each set of spatiotemporal processing data to generate a prefix encoding family of each set of spatiotemporal processing data;

By using each set of spatio-temporal processing data and the prefix encoding family of each set of spatio-temporal processing data as a leaf node of the hybrid index tree, multiple leaf nodes are obtained;

By merging different prefix coding families, non-leaf nodes are generated layer by layer from bottom to top; wherein, each non-leaf node corresponds to a merged coding family, and each non-leaf node is at least one leaf node or at least one non-leaf node The parent node, the merged code family corresponding to each parent node contains the prefix code family or merged code family of all child nodes of the parent node;

According to the prefix encoding family corresponding to each leaf node, generate the Bloom filter of each leaf node, and generate the Bloom filter of each non-leaf node according to the combined encoding family corresponding to each non-leaf node, and obtain Hybrid index tree; where the Bloom filters of different leaf nodes have the same length, and the Bloom filters of non-leaf nodes in different layers have different lengths;

Symmetric encryption is performed on each Bloom filter to obtain an encrypted hybrid index tree.

The present invention also provides a privacy-protected space-time contact query method, including:

Obtaining a query request containing query data; the query data includes: query spatial position data, query time data corresponding to the query spatial position data;

performing encoding processing on the query spatial position data in the query data by using a Hilbert curve to obtain query processing data including query encoding data and the query time data;

performing prefix encoding on the query encoding data to generate a prefix encoding family of the query encoding data;

According to the prefix coding family, a prefix code corresponding to each layer of the encrypted hybrid index tree is obtained, and a prefix code corresponding to each layer does not contain a wildcard;

generating a decryption key for each layer according to preset security parameters, the prefix code corresponding to each layer, and the prefix code corresponding to each layer that does not contain wildcards;

Generate a corresponding Bloom filter according to the decryption key of each layer, and encrypt the generated Bloom filter to obtain multiple queries corresponding to multiple layers of the encrypted hybrid index tree one-to-one. Bloom filter;

The plurality of query Bloom filters are used as query tokens, and data query is performed from the encrypted hybrid index tree by using the query tokens to obtain query results.

The present invention has the following beneficial technical effects:

In the hybrid index tree generated by the present invention, the non-leaf nodes include the data obtained after Hilbert curve processing and prefix encoding processing on the spatial position data, and the leaf nodes not only include the data obtained after Hilbert curve processing and prefix encoding on the spatial position data. The data obtained after curve processing and prefix encoding processing also includes the original time data corresponding to the spatial position data, and each leaf node or non-leaf node corresponds to a Bloom filter, and each Bloom filter is organized in a tree structure device. Therefore, on the one hand, when the data to be checked is spatio-temporal data containing time data and spatial data (for example, including time and a place corresponding to the time), the query of spatio-temporal data can be realized, which is more suitable for flow adjustment work ; On the other hand, it can satisfy the query process with sub-linear time complexity, and can get a dynamically pruned search space when performing data query, which can improve the efficiency of linear data structure search and greatly reduce the time consumption of data retrieval .

The present invention will be described in further detail below in conjunction with the accompanying drawings and embodiments.

Description of drawings

FIG. 1 is an optional flow chart of a method for generating an encrypted hybrid index tree provided by an embodiment of the present invention;

FIG. 2 is a schematic diagram of an exemplary encoding process of multiple sets of original spatio-temporal data by using a Hilbert curve provided by an embodiment of the present invention;

FIG. 3A is a three-dimensional schematic diagram of an exemplary generated hybrid index tree provided by an embodiment of the present invention;

FIG. 3B is a schematic plan view of an exemplary generated hybrid index tree provided by an embodiment of the present invention;

FIG. 4 is an optional flow chart of a privacy-protected spatio-temporal contact query method provided by an embodiment of the present invention;

FIG. 5 is a schematic diagram of an exemplary data query process according to a query token provided by an embodiment of the present invention;

FIG. 6 is a flowchart of an exemplary encrypted hybrid index tree generation method and a privacy-protected spatio-temporal contact query method provided by an embodiment of the present invention;

FIG. 7 is an application scenario diagram of an exemplary privacy-protected space-time contact query system provided by an embodiment of the present invention;

FIG. 8A is a schematic diagram of an exemplary time required to generate a query token by using the method of the present invention according to an embodiment of the present invention and a change in data volume;

FIG. 8B is an exemplary query time comparison diagram when the method of the present invention is used for spatio-temporal data query and the PBRQ scheme is used for spatio-temporal data query provided by the embodiment of the present invention.

Detailed ways

The present invention will be described in further detail below in conjunction with specific examples, but the embodiments of the present invention are not limited thereto.

In the description of the present invention, the terms "first" and "second" are only used for descriptive purposes, and cannot be understood as indicating or implying relative importance or implicitly specifying the quantity of indicated technical features. Thus, a feature defined as "first" and "second" may explicitly or implicitly include one or more of these features. In the description of the present invention, "plurality" means two or more, unless otherwise specifically defined.

In the description of this specification, descriptions referring to the terms "one embodiment", "some embodiments", "example", "specific examples", or "some examples" mean that specific features described in connection with the embodiment or example , structure, material or characteristic is included in at least one embodiment or example of the present invention. In this specification, the schematic representations of the above terms are not necessarily directed to the same embodiment or example. Furthermore, the specific features, structures, materials or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. In addition, those skilled in the art can combine and combine different embodiments or examples described in this specification.

Although the present invention has been described in conjunction with various embodiments herein, in the process of implementing the claimed invention, those skilled in the art can understand and Other variations of the disclosed embodiments are implemented. In the claims, the word "comprising" does not exclude other components or steps, and "a" or "an" does not exclude a plurality. A single processor or other unit may fulfill the functions of several items recited in the claims. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that these measures cannot be combined to advantage.

Fig. 1 is an optional flowchart of a method for generating an encrypted hybrid index tree provided by an embodiment of the present invention. As shown in Fig. 1, the method includes the following steps:

S101. Acquire multiple sets of original spatio-temporal data of multiple objects; each set of original spatio-temporal data includes original spatial position data and original time data corresponding to the original spatial position data.

In the embodiment of the present invention, multiple objects may be multiple different people. Each set of original spatio-temporal data can be a time data (for example, time 16:30, etc.) and a corresponding location data (for example, longitude, latitude information or place name information, etc.) where.

S102. Using the Hilbert curve, encode the original spatial position data to obtain multiple sets of spatio-temporal processing data including the spatial encoding data and the original time data.

In the embodiment of the present invention, the Hilbert curve is used to encode the original spatial position data in each group of original space-time data, and the spatial encoding data corresponding to the original spatial position data in each group of original space-time data is obtained, so that the group of original space-time data The spatial encoding data corresponding to the original spatial position data in the spatio-temporal data, and the original time data in the set of original spatio-temporal data constitute a set of spatio-temporal processed data.

Here, the Hilbert curve has a clustering property.

Exemplarily, FIG. 2 is a schematic diagram of encoding processing of multiple sets of original spatio-temporal data O ₁ -O6 using Hilbert curves, and Table 1 shows the coding process of multiple sets of original spatio-temporal data O ₁ -O6 using Hilbert curves. Multiple sets of spatio-temporal processing data obtained after encoding the original spatial position data.

object Hilbert coding raw time data O₁ 9 t1 O₂ 11 t2 O₃ 34 t3 O₄ 35 t4 O₅ 52 t5 O₆ 55 t6

Table 1

As shown in Table 1, multiple sets of original space-time data O ₁ ~ O6 are called multiple sets of objects, "9" is the spatial encoding data obtained after encoding the original spatial position data in O ₁ , and "t1" is the data in O ₁ The original time data, that is, "9" and "t1" are a set of spatio-temporal processing data; similarly, "11" is the spatial encoding data obtained after encoding the original spatial position data in _O2 , and "t2" is _O2 The original time data in , and so on, other data in the same way.

S103. Perform prefix encoding on the spatial encoding data in each set of spatiotemporal processing data, and generate a prefix encoding family of each set of spatiotemporal processing data.

In the embodiment of the present invention, when one space-encoded data in any set of spatio-temporal processing data is ω-bit data, prefix encoding can be performed on one space-encoded data in any set of spatio-temporal processed data to generate ω+1 Prefix encoding, encoding ω+1 prefixes as a prefix encoding family of a space-encoded data in the arbitrary group of spatio-temporal processing data.

Suppose a ω-bit data item Y=b ₁ b ₂ ...b _ω , its prefix coding family is a set Y={b ₁ b ₂ ...b _ω-1 *,. .., *...*}, where the i-th prefix in the set is coded as b ₁ b ₂ ...b _ω+1-i *...*. For example, the prefix code family of 000111 is *********, 0*****, 00****, 000***, 0001**, 00011*, 000111.

Here, the prefix code matching rule is: Given a range [y _min , y _max ], the query S[y _min , y _max ] is the minimum set of prefix codes covering the range [y _min , y _max ]. For any data item Y and query range [y _min , y _max ], if and only if F(Y)∩S[y _min , y _max ], Y∈[y _min ,y _max ].

S104. Using each set of spatio-temporal processing data and the prefix encoding family of each set of spatio-temporal processing data as a leaf node of the hybrid index tree to obtain multiple leaf nodes.

S105. By merging different prefix coding families, non-leaf nodes are generated layer by layer from bottom to top; wherein, each non-leaf node corresponds to a merged coding family, and each non-leaf node is at least one leaf node or at least one non-leaf node The parent node of the node, the merged code family corresponding to each parent node includes the prefix code family or merged code family of all child nodes of the parent node.

S106. Generate a Bloom filter for each leaf node according to the prefix encoding family corresponding to each leaf node, and generate a Bloom filter for each non-leaf node according to the combined encoding family corresponding to each non-leaf node, and obtain Hybrid index tree; where the Bloom filters of different leaf nodes have the same length, and the Bloom filters of non-leaf nodes in different layers have different lengths.

In the embodiment of the present invention, the lengths of Bloom filters corresponding to nodes in the same layer are the same, and the lengths of Bloom filters corresponding to nodes in different layers are different.

In the embodiment of the present invention, the prefix coding family or the combined coding family of all nodes on the BH-Tree are stored in a Bloom filter, and by means of the Bloom filter, it can be easily determined whether a data range Contains all query purpose space information, that is, to determine whether a node on a single tree belongs to a certain range.

In an embodiment, the principle of generating a Bloom filter for each leaf node V=(s ₁ , s ₂ ,...,s _n ) is as follows:

1) The Bloom filter is initialized as a P-bit binary vector B; P is a preset value, which can be set according to actual needs, for example, it can be 6 or 8, etc.;

2) Select t independent hash functions {H _i } _1≤i≤t , the value range of each hash function is [1,P], and use these t independent hash functions to process each data s∈ V performs hash calculation to obtain all indexes {H _i (s)} _1≤i≤t of each data; t is a preset value, and can also be set according to actual needs; s ₁ , s ₂ ,..., s _n is the n data in the leaf node;

3) For each piece of data, set all the bits of the piece of data whose indices are {H _i (s)} _1≤i≤t to 1.

Exemplarily, FIG. 3A is a three-dimensional schematic diagram of a hybrid index tree (BH-Tree) generated based on the Hilbert processing and prefix encoding processing of multiple sets of original spatio-temporal data O ₁ to O ₆ ; 3B is a schematic plan view of a hybrid index tree (BH-Tree) generated according to the Hilbert processing and prefix coding processing of multiple sets of original spatio-temporal data O ₁ -O ₆ . As shown in Figure 3B, N ₀ is the parent node of N ₁ , N ₂ and N ₃ (that is, N ₁ , N ₂ and N ₃ are the child nodes of N ₀ ), and N ₁ is the parent node of N ₄ (that is, N ₄ is the child node of N ₁ ), N ₂ is the parent node of N ₅ (that is, N ₅ is the child node of N ₂ ), N ₃ is the parent node of N ₆ (that is, N ₆ is the child node of N ₃ ), N ₄ is the parent node of O ₁ and O ₂ (that is, O ₁ and O ₂ are the child nodes of N ₄ ), N ₅ is the parent node of O ₃ and O ₄ (that is, O ₃ and O ₄ are the child nodes of N ₅ ), N ₆ is the parent node of O ₅ and O ₆ (that is, O ₅ and O ₆ are the child nodes of N ₆ ). N ₀ is in the first layer of BH-Tree, N ₁ , N ₂ and N ₃ are in the second layer of BH-Tree, N ₄ , N ₅ and N ₆ are in the third layer of BH-Tree, O ₁ , O ₂ , O ₃ , O ₄ , O ₅ and O ₆ are in the fourth layer of BH-Tree; and, O ₁ , O ₂ , O ₃ , O ₄ , O ₅ and O ₆ are 6 different Leaf nodes, N ₀ , N ₁ , N ₂ , N ₃ , N ₄ , N ₅ and N ₆ are 7 different non-leaf nodes of the BH-Tree respectively.

S107. Perform symmetric encryption on each Bloom filter to obtain an encrypted hybrid index tree.

In the embodiment of the present invention, the security parameters can be obtained first, and the first key is generated according to the security parameters, and then, the first key is used to perform symmetric key hidden vector encryption on each Bloom filter to obtain an encrypted hybrid index tree .

计算出第一密钥msk，其中，M表示消息空间范围，用于表示对范围不超过M的数据采用msk进行加密。In some embodiments, the security parameter λ can be obtained, the payload message space M={'True'} can be defined, and the formula

The first key msk is calculated, where M represents the range of the message space, and is used to indicate that the data whose range does not exceed M is encrypted with msk.

In some embodiments, the encryption process can be implemented using the formula c _l =F(msk,"true",x _l ||l) and c=({c _l } _l∈[m] ), where l represents any Bloom filter, x _l represents the data stored in any Bloom filter, c _l represents any encrypted Bloom filter, c represents the set of encrypted Bloom filters (that is, encrypted hybrid index tree), That is, c=(c ₁ ,c ₂ ,...,c _n ); m represents the set of Bloom filters corresponding to all nodes in the hybrid index tree, m=(l ₁ ,l ₂ ,...,l _n ), for example, l ₁ represents the Bloom filter corresponding to the first node of the first layer, and the same applies to others; x represents the set of data stored in all Bloom filters, x=(x ₁ ,x ₂ , ..., x _n ), for example, x ₁ represents the data stored in the Bloom filter corresponding to the first node of the first layer.

In the hybrid index tree generated by the present invention, the non-leaf nodes contain the spatial position data processed by the Hilbert curve and the prefix encoding, and the leaf nodes not only contain the spatial position data processed by the Hilbert curve and the prefix encoding , also contains the original time information corresponding to the spatial position data, and each leaf node or non-leaf node corresponds to a Bloom filter, and each Bloom filter is organized in a tree structure. Therefore, on the one hand, when the data to be checked is spatiotemporal information containing time information and spatial information (for example, including time and a place corresponding to the time), the query of spatiotemporal information can be realized, which is more suitable for flow adjustment work ; On the other hand, it can satisfy the query process with sub-linear time complexity, and can get a dynamically pruned search space when performing data query, which can improve the efficiency of linear data structure search and greatly reduce the time consumption of data retrieval .

In some embodiments, the above S105 can be realized through S1051-S1056:

S1051. By merging different prefix coding families corresponding to multiple leaf nodes, the first combined coding family corresponding to each leaf node is obtained, and the first combined coding family is used as the first parent node of the corresponding leaf node; wherein , each leaf node is a child node of the corresponding first parent node.

S1052. Use the leaf node as the ωth layer of the hybrid index tree, and use the first parent node as the ω-1th layer of the hybrid index tree.

S1053. By merging the first merged code families corresponding to multiple first parent nodes, the second merged code family corresponding to each first parent node is obtained, and the second merged code family is used as the corresponding first parent node A second parent node; wherein, each first parent node is a child node of the corresponding second parent node.

S1054. Use the second parent node as layer ω-2 of the hybrid index tree.

S1055. Merge the second merged code families corresponding to multiple second parent nodes to obtain a third merged code family corresponding to each second parent node, and use the third merged code family as the corresponding second parent node A third parent node; wherein, each second parent node is a child node of the corresponding third parent node.

S1056. Use the third parent node as the ω-3th layer of the hybrid index tree until a node of the ω-wth layer of the hybrid index tree is obtained; wherein, w is ω-1.

For example, when ω is 6, the constructed hybrid index tree has 6 layers.

In some embodiments, the first combined coding family includes: the first original coding and the first sub-coding; based on this, the above S1051 can be implemented in the following manner:

Compare the prefix codes in different prefix code families corresponding to multiple leaf nodes bit by bit, and determine at least two first prefix code families with the same code value of the first ω-1 bit and different code values of the ω-th bit, when When there are at least two first prefix encoding families, the ω-th code value of the prefix encoding that does not contain wildcards in at least two first prefix encoding families is set as a wildcard to obtain the first original encoding; the first original encoding of the first The code value of ω-1 bit is set as a wild card, and the first sub-code is correspondingly obtained, and the code value of the ω-2th bit of the first original code is set as a wild card, and the corresponding first sub-code is obtained, until the first original code When the code value of the ω-wth bit is set as a wildcard, at least one first sub-code is correspondingly obtained; w is ω-1; the first original code and at least one first sub-code are used as at least two first prefix code families The first parent node of the corresponding leaf node.

Here, the wildcard is "*", which means "1" or "0".

Here, when there are no at least two first prefix coding families, the prefix codes in different prefix coding families corresponding to multiple leaf nodes are compared bit by bit, and it is determined that the first ω-2 bit code values are the same, and the ω-th -At least two second prefix encoding families with different code values of 1 bit, when there are at least two second prefix encoding families, the ω-1th bit of the prefix encoding that does not contain wildcards in the at least two second prefix encoding families and the ω-th code value are both set as wildcards to obtain the third original code; the code value of the ω-2th bit of the third original code is set as a wildcard to obtain the third sub-code correspondingly, and the third original code ω-2 The code value of -3 bits is set as a wild card, and the third sub-code is obtained correspondingly, until the code value of the ω-w bit of the third original code is set as a wild card, at least one third sub-code is correspondingly obtained; w is ω- 1: Use the third original code and at least one third child code as the first parent node of the leaf nodes corresponding to at least two second prefix code families.

Exemplarily, as shown in FIG. 3B above, ω is 6, because there is no first 5-bit code value in the prefix coding family of the six leaf nodes O ₁ , O ₂ , O ₃ , O ₄ , O ₅ and O ₆ Two or more prefix coding families that are the same and have different 6th code values, so continue coding from the prefixes of the six leaf nodes O ₁ , O ₂ , O ₃ , O ₄ , O ₅ , and O ₆ In the family, determine which prefix codes of the leaf nodes in the prefix code family are all prefix codes with the same first 4 code values and different 5th code values, and obtain the prefix codes in the prefix code family between O ₁ and O ₂ The prefix codes are prefix codes with the same code value of the first 4 digits (that is, "0010") and different code values of the 5th digit, and the prefix codes in the prefix code family between O ₃ and O ₄ are all code values of the first 4 digits The same (that is, "1000"), and the prefix codes with different code values in the 5th digit, the prefix codes in the prefix code family between O ₅ and O ₆ are all the same in the first 4 code values (that is, "1101" ), and the code value of the 5th digit is different, so, for O ₁ and O ₂ , the 5th and 6th code values of "001001" that do not contain wildcards can be set as the wildcard "*" , to get "0010**" (i.e. the first original code), so that "001***", "00****", "0*****", "****"; take "0010**, 001***, 00****, 0******, ****" or N ₄ as the connection between O ₁ and O ₂ For the first parent node, for O ₃ and O ₄ , and O ₅ and O ₆ , the same principle can be used to obtain the first parent node N ₅ and the first parent node N ₆ .

In some embodiments, the second combined coding family includes: a second original code and a second sub-coding, and when there are at least two first prefix coding families, the above S1053 can be implemented in the following manner:

Comparing the codes in different first merged code families bit by bit, and determining at least two merged code families with the same code value of the first ω-2 bits and different code values of the ω-1th bit, when there are at least two merged code families When encoding the family, in at least two merged encoding families, the ω-1 to ω-th code values of the code that contains the least wildcard are all set as wildcards to obtain the second original code; the second original code ω- The 2-bit code value is set as a wildcard, corresponding to the second sub-code, and the code value of the ω-3 bit of the second original code is set as a wildcard, corresponding to the second sub-code, until the second original code ω When the code value of the -w bit is set as a wildcard, at least one second sub-code is correspondingly obtained; w is ω-1; the second original code and at least one second sub-code are used as the first corresponding to at least two merged code families The second parent of the parent node.

In some embodiments, when there are no at least two first prefix code families and there are at least two second prefix codes, the above S1053 can be implemented in the following manner:

Comparing the codes in different first merged code families bit by bit, and determining at least two merged code families with the same first ω-3 code value and different ω-2 code values, when there are at least two merged When encoding the family, in at least two merged encoding families, the ω-2 to ω-th code values of the code that contains the least wildcard are all set as wildcards to obtain the second original code; the second original code ω- The 3-bit code value is set as a wildcard, corresponding to the second subcode, and the code value of the ω-4th bit of the second original code is set as a wildcard, corresponding to the second subcode, until the second original code ω When the code value of the -w bit is set as a wildcard, at least one second sub-code is correspondingly obtained; w is ω-1; the second original code and at least one second sub-code are used as the first corresponding to at least two merged code families The second parent of the parent node.

In the embodiment of the present invention, the implementation principle of S1055 is the same as that of S1053 above, until the first layer node of the hybrid index tree is obtained through the principle described in S1053, the construction of the hybrid index tree is completed.

In the embodiment of the present invention, when constructing the hybrid index tree, the first parent node of each leaf node (the ω- 1 layer), and the first combined coding family corresponding to each first parent node, and then, by merging the first combined coding families corresponding to different first parent nodes, the second parent node of each first parent node ( layer ω-2 of the mixed index tree), and the second merged code family corresponding to each second parent node, and then, by merging the second merged code families corresponding to different second parent nodes, each second parent node is obtained The third parent node of the node (the ω-3 layer of the hybrid index tree), and the third merged coding family corresponding to each third parent node, until the wth parent node (the first layer of the hybrid index tree) is obtained, and , when the w-th merged code family corresponding to the w-th parent node is a prefix code composed of ω wildcards, it ends; wherein, when constructing the N-th layer node, the code corresponding to the N+1-th layer node continues to Merge one-bit code value before, so as to obtain the merged code corresponding to the node on the Nth layer, and continue to merge one-bit code value forward on the code corresponding to the node on the N+1 layer, and the parent node on the Nth layer cannot be obtained , merge the two-bit code value forward on the code corresponding to the N+1 layer node until the parent node of the N layer can be obtained.

The hybrid index tree established in the above way, from the first layer to the ω layer of the hybrid index tree, the range of data corresponding to each node gradually decreases, so that it is beneficial to reduce the amount of data search during data query, thereby improving Data query efficiency.

The embodiment of the present invention also provides a privacy-protected space-time contact query method, as shown in Figure 4, the method includes:

S201. Obtain a query request including query data; the query data includes: query spatial location data, and query time data corresponding to the query spatial location data.

S202. Using the Hilbert curve, encode the query spatial position data in the query data to obtain query processing data including query code data and query time data.

S203. Perform prefix encoding on the query encoding data to generate a prefix encoding family of the query encoding data.

S204. According to the prefix code family, obtain the prefix code corresponding to each layer of the encrypted hybrid index tree, and the prefix code corresponding to each layer that does not contain wildcards.

In some embodiments, the principle used to generate nodes at each layer of the hybrid index tree can be used to obtain the prefix code corresponding to each layer of the encrypted hybrid index tree; A prefix code corresponding to each level of the encrypted hybrid index tree is obtained.

S205. Generate a decryption key for each layer according to the preset security parameters, the prefix codes corresponding to each layer, and the prefix codes corresponding to each layer that do not contain wildcards.

In some embodiments, the security parameter can be obtained, the second key is generated according to the security parameter, and the sampling value is generated according to the security parameter; according to the security parameter, the second key, the sampling value, the prefix encoding corresponding to each layer, and The prefix encoding corresponding to each layer does not contain the prefix encoding of wildcards, and the decryption key of each layer is generated.

Exemplarily, the security parameter is λ, the second key can be the first key msk, and the decryption key J of any layer can be calculated by the following formula:

d ₁ =Sym.Enc(K,0 ^λ+logλ );

J=(d ₀ ,d ₁ ,S);

为与混合索引树的第l层对应的前缀编码中的第j个前缀编码，l_j和j∈[|S|]均为与混合索引树的第l层对应的前缀编码中，完全不包含通配符的前缀编码对应的查询编码数据，并且，当与混合索引树的第l层对应的前缀编码中，没有完全不包含通配符的前缀编码时l_j与 j∈[|S|]为0；F₀(.)表示前缀编码函数，

表示或运算；S表示与混合索引树的所有层对应的前缀编码中不包含通配符“*”的前缀编码的对应的查询编码数据的集合；Sym.Enc表示IND-CPA安全对称加密方案的加密过程。Among them, J represents the decryption key of any layer, d ₀ is the first intermediate value of this arbitrary layer, d ₁ is the second intermediate value of this arbitrary layer; K is the sampling value of this arbitrary layer, and each The sampling values of one layer are the same,

It is the j-th prefix code in the prefix code corresponding to the l-th layer of the mixed index tree, l _j and j∈[|S|] are both in the prefix code corresponding to the l-th layer of the mixed index tree, which does not contain The query code data corresponding to the wildcard prefix code, and when there is no prefix code that does not contain wildcards in the prefix code corresponding to the l-th layer of the mixed index tree, l _j and j∈[|S|] are 0; F ₀ (.) indicates the prefix encoding function,

Represents an OR operation; S represents the set of query code data corresponding to prefix codes that do not contain the wildcard "*" in the prefix codes corresponding to all layers of the hybrid index tree; Sym.Enc represents the encryption process of the IND-CPA secure symmetric encryption scheme .

S206. Generate a corresponding Bloom filter according to the decryption key of each layer, and encrypt the generated Bloom filter to obtain multiple query Blooms corresponding to multiple layers of the encrypted hybrid index tree one-to-one. filter.

S207. Use multiple query Bloom filters as query tokens, and use the query tokens to query data from the encrypted hybrid index tree to obtain query results.

In the embodiment of the present invention, each obtained query Bloom filter can be put into T _Q to obtain the query token T _Q .

In some embodiments, the encrypted hybrid index tree includes ω layers, each layer includes at least one node, and each node corresponds to an encrypted Bloom filter; the query token includes: ω query cloths one-to-one corresponding to the ω layer Long filter; ω is an integer greater than 1; based on this, using the query token in the above S207 to perform data query from the encrypted mixed index tree to obtain the query result can be realized through S1～S4:

S1. Using the j-th query Bloom filter corresponding to the j-th layer, decrypt and calculate the encrypted Bloom filter corresponding to each node in the j-th layer, and obtain the first decryption result corresponding to each node ;j is 1.

S2. When the first decryption result corresponding to the i-th node in the j-th layer indicates that the decryption is successful, and the i-th node has the first child node, use the j+1-th query layout corresponding to the j+1-th layer The Bloom filter performs decryption calculation on the encrypted Bloom filter corresponding to the first child node to obtain a second decryption result.

Exemplarily, using the jth query Bloom filter corresponding to the jth layer, the process of decrypting and calculating the encrypted Bloom filter corresponding to each node N in the jth layer is as follows:

μ'=Sym.Dec(K',d ₁ );

Among them, d ₀ and d ₁ are the first intermediate value and the second intermediate value in the jth query Bloom filter; K' is the intermediate decryption value, and c _jN represents the Nth value of the jth layer in the encrypted hybrid index tree Bloom filter corresponding to nodes; N∈[|S|] means that in the Bloom filter corresponding to the Nth node in the jth layer, the space coded data corresponding to the prefix code that does not contain wildcards; μ' means the obtained The first decryption result; Sym.Dec represents the decryption process of the IND-CPA secure symmetric decryption scheme.

Exemplarily, when μ'=0 ^λ+logλ , the first decryption result indicates that the decryption is successful.

S3. When it is determined that the second decryption result corresponding to the first child node indicates that the decryption is successful, and the first child node has a child node, use the j+2th query Bloom filter corresponding to the j+2th layer to query the first child node The encrypted Bloom filter corresponding to the child node of a child node performs decryption calculation until the obtained decryption result indicates that the decryption is successful, and when the target node corresponding to the decryption result indicating that the decryption is successful does not have a child node, the ωth query cloth is used The query time data corresponding to the long filter is matched and compared with the original time data corresponding to the target node.

S4. When there is data that successfully matches the query time data in the original time data corresponding to the target node, use the data that successfully matches the query time data as the query result.

In the embodiment of the present invention, when the decryption result characterization corresponding to a certain node is successful, the node is added to the search path, and the child nodes of the node are continued to be decrypted and calculated, and when the decryption result characterization corresponding to a certain node fails, no Processing (that is, pruning); for the leaf nodes that have been added to the search path, the query time data in the query token can be used to match the original time data in the leaf node, if the match is successful, then add the result queue, otherwise do not processing, the result queue is the final return result.

Exemplarily, FIG. 5 is a schematic diagram of a data query process based on a query token. For the spatial position data in the query data, after using the Hilbert curve to encode, the obtained query encoding data are [32,33] and [52,57], and the query time data in the query data is t5; Each query encoding data 32, 33, 52 and 57 are respectively prefix-encoded to generate a prefix encoding family of each query encoding data, and the prefix encoding corresponding to the first layer of the encrypted hybrid index tree obtained according to the prefix encoding family is "*****", the prefix code corresponding to the second layer of the encrypted hybrid index tree is "1*****", the prefix code corresponding to the third layer of the encrypted hybrid index tree is "1101* *, 1110**, 1000**", the prefix code corresponding to the fourth layer of the encrypted hybrid index tree is "1101**, 11100*, 10000*"; after that, use the prefix code corresponding to each layer, corresponding Generate the decryption key J of each layer; then, as shown in Figure 5, use the decryption key J of the first layer to decrypt and calculate the node N ₀ (that is, match the prefix in the Bloom filter corresponding to N ₁ code "******"), when the decryption is successful, the decryption key J of the second layer is used to decrypt the nodes N ₁ , N ₂ and N ₃ respectively, and when the decryption of N ₁ fails, pruning , and when both N ₂ and N ₃ are successfully decrypted (that is, the prefix code "1*****" is matched in the Bloom filters corresponding to N ₂ and N ₃ respectively), the decryption encryption of the third layer is used Key J decrypts N ₅ and N ₆ respectively, and prunes when N ₅ fails to decrypt, and N ₆ succeeds in decrypting (that is, the prefix code "1101** is matched in the Bloom filter corresponding to N ₆ ”), use the query time data t5 to match the original time data t5 in the leaf node _O5 and the original time data t6 in _O6 respectively, so as to determine the original time data t5 in the leaf node _O5 and the query The time data t5 is matched, so that the original time data t5 and the original spatial position data corresponding to "1101**" corresponding to the original time data t5 in the Bloom filter of the leaf node _O5 can be used as query results.

FIG. 6 is a flowchart of a method for generating an encrypted hybrid index tree and a privacy-protected spatio-temporal contact query method provided by an embodiment of the present invention. As shown in Figure 6, a BH-tree is established for personal spatiotemporal information, a variable-length key is generated according to the BH-tree, and a key set is obtained, and then the BH-tree is encrypted through the key set to obtain an encrypted database (encrypted BH -tree), when querying spatiotemporal data from an encrypted database, first generate a traceability key (Token, that is, a query token) according to the spatiotemporal traceability request (query request), use the traceability key to query, and obtain an encrypted query As a result, the traceability result is obtained.

Fig. 7 is an application scenario diagram of the privacy-protected spatio-temporal contact query system provided by the embodiment of the present invention. As shown in Figure 7, relevant units (for example, epidemic prevention units) collect citizens’ itinerary data through legal means, extract key itinerary data, and encrypt the itinerary data to obtain personal spatio-temporal data, and upload the personal spatio-temporal data to the cloud platform for storage. The cloud platform adopts the method of generating an encrypted hybrid index tree to securely store personal spatiotemporal data, which is used to provide ciphertext data for privacy-protected spatiotemporal contact queries; when a case occurs in a certain area, and relevant institutions need to query relevant When contacting people, relevant agencies send query requests to the cloud platform, and the cloud platform uses the above-mentioned privacy-protected spatio-temporal contact query method to query spatio-temporal data, find relevant encrypted data, and return the relevant encrypted data to relevant agencies. The organization uses the shared key between the relevant organization and the relevant unit to decrypt the obtained encrypted data and obtain the plaintext data required for query.

In order to further illustrate the technical effect of the present invention, the comparison diagram obtained by simulation is described below.

Fig. 8A is a schematic diagram of the change of the time required to generate query tokens with the amount of data by using the method of the present invention; it can be known from Fig. 8A that the time for generating query tokens in the present invention is at the millisecond level in tens of thousands of data. FIG. 8B is a comparison chart of query time when the method of the present invention is used to query spatio-temporal data and when the PBRQ scheme is used to query spatio-temporal data. According to Fig. 8B, it can be seen that the query time of the present invention is significantly lower than that of PBRQ, and the query time at 10,000 levels is far lower than the time required for PBRQ query; and, it changes sublinearly with time, and has a very obvious response time advantage. Especially for a data set with a data volume of 150,000, it only takes 291.3ms to complete the generation of the query token, and 38.22ms to complete the data query. The operation efficiency is high, and it can be widely used in actual scenarios.

The above content is a further detailed description of the present invention in conjunction with specific preferred embodiments, and it cannot be assumed that the specific implementation of the present invention is limited to these descriptions. For those of ordinary skill in the technical field of the present invention, without departing from the concept of the present invention, some simple deduction or replacement can be made, which should be regarded as belonging to the protection scope of the present invention.

Claims (10)

1. A method for generating an encrypted hybrid index tree, comprising:

acquiring multiple groups of original space-time data of multiple objects; each group of original space-time data comprises original space position data and original time data corresponding to the original space position data;

coding the original spatial position data by using a Hilbert curve to obtain a plurality of groups of space-time processing data including spatial coding data and the original time data;

carrying out prefix coding on the space coding data in each group of space-time processing data to generate a prefix coding family of each group of space-time processing data;

obtaining a plurality of leaf nodes by using each group of space-time processing data and the prefix coding family of each group of space-time processing data as one leaf node of a mixed index tree;

combining different prefix coding families to generate non-leaf nodes layer by layer from bottom to top; each non-leaf node corresponds to one merged coding family, each non-leaf node is at least one leaf node or a father node of at least one non-leaf node, and the merged coding family corresponding to each father node comprises prefix coding families or merged coding families of all child nodes of the father node;

generating a bloom filter of each leaf node according to the prefix coding family corresponding to each leaf node, and generating a bloom filter of each non-leaf node according to the combined coding family corresponding to each non-leaf node to obtain a mixed index tree; wherein, the lengths of the bloom filters of different leaf nodes are the same, and the lengths of the bloom filters of non-leaf nodes of different layers are different;

and symmetrically encrypting each bloom filter to obtain an encrypted mixed index tree.

2. The method of generating an encrypted hybrid index tree according to claim 1, wherein the merged code family comprises: a first merged coding family, a second merged coding family and a third merged coding family; each prefix code comprises a code value of omega bits; the merging of different prefix coding families to generate non-leaf nodes layer by layer from bottom to top comprises the following steps:

combining different prefix coding families corresponding to the leaf nodes to obtain a first combined coding family corresponding to each leaf node, and taking the first combined coding family as a first father node of the corresponding leaf node; each leaf node is a child node of the corresponding first father node;

taking the leaf node as the omega-1 layer of the mixed index tree and the first father node as the omega-1 layer of the mixed index tree;

the second merged coding family corresponding to each first father node is obtained by merging the first merged coding families corresponding to the plurality of first father nodes, and the second merged coding family is used as the second father node of the corresponding first father node; each first father node is a child node of the corresponding second father node;

taking the second parent node as the omega-2 layer of the mixed index tree;

merging second merged coding families corresponding to a plurality of second father nodes to obtain a third merged coding family corresponding to each second father node, and taking the third merged coding family as a third father node of the corresponding second father node; each second father node is a child node of the corresponding third father node;

taking the third father node as the omega-3 layer of the mixed index tree until obtaining the node of the omega-w layer of the mixed index tree; wherein w is ω -1.

3. The method of generating an encrypted hybrid index tree according to claim 2, wherein the first merged encoding family includes: a first original code and a first sub code;

the merging different prefix code families corresponding to the leaf nodes to obtain the first merged code family corresponding to each leaf node, and using the first merged code family as a first father node of the corresponding leaf node includes:

comparing prefix codes in different prefix code families corresponding to the leaf nodes bit by bit, determining at least two first prefix code families with the same front omega-1 bit code value and different omega bits, and setting the omega bit code value of the prefix code not containing wildcards in the at least two first prefix code families as wildcards to obtain the first original code when the at least two first prefix code families exist;

setting the code value of the omega-1 bit of the first original code as a wildcard character to correspondingly obtain a first sub-code, setting the code value of the omega-2 bit of the first original code as a wildcard character to correspondingly obtain a first sub-code, and correspondingly obtaining at least one first sub-code until the code value of the omega-w bit of the first original code is set as a wildcard character; w is omega-1;

and taking the first original code and the at least one first child code as the first parent node of the leaf nodes corresponding to the at least two first prefix code families.

4. The method of generating an encrypted hybrid index tree according to claim 3, further comprising:

when the at least two first prefix coding families do not exist, comparing prefix codes in different prefix coding families corresponding to the leaf nodes bit by bit, determining at least two second prefix coding families with the same front omega-2 bit code value and different omega-1 bit code values, and when the at least two second prefix coding families exist, setting the omega-1 bit code value and the omega bit code value of the prefix code which does not contain the wildcard in the at least two second prefix coding families as wildcards to obtain a third original code;

setting the code value of the omega-2 bit of the third original code as a wildcard character to correspondingly obtain a third sub-code, setting the code value of the omega-3 bit of the third original code as a wildcard character to correspondingly obtain a third sub-code, and correspondingly obtaining at least one third sub-code until the code value of the omega-w bit of the third original code is set as a wildcard character; w is omega-1;

and taking the third original code and the at least one third child code as the first father node of the leaf nodes corresponding to the at least two second prefix code families.

5. The method of generating an encrypted hybrid index tree according to claim 3, wherein the second merged coding family comprises: a second primary code and a second secondary code;

when the at least two first prefix coding families exist, the second merged coding family corresponding to each first parent node is obtained by merging the first merged coding families corresponding to the multiple first parent nodes, and the second merged coding family is used as the second parent node of the corresponding first parent node, including:

carrying out bit-by-bit comparison on codes in different first merging code families, determining at least two merging code families with the same front omega-2 bit code value and different omega-1 bit code values, and setting the code values from the omega-1 bit to the omega-1 bit containing the code with the least wildcard characters in the at least two merging code families as wildcard characters to obtain a second original code when the at least two merging code families exist;

setting the code value of the omega-2 bit of the second original code as a wildcard character to correspondingly obtain a second sub code, setting the code value of the omega-3 bit of the second original code as a wildcard character to correspondingly obtain a second sub code, and correspondingly obtaining at least one second sub code until the code value of the omega-w bit of the second original code is set as a wildcard character; w is omega-1;

and using the second original code and the at least one second child code as the second parent node of the first parent node corresponding to the at least two merged code families.

6. The method for generating an encrypted mixed index tree according to claim 1, wherein when one spatial encoding data in any one set of spatio-temporal processing data is ω -bit data, the prefix encoding is performed on the spatial encoding data in each set of spatio-temporal processing data to generate a prefix encoding family of each set of spatio-temporal processing data, comprising:

prefix coding is carried out on one space coding data in any group of space-time processing data to generate omega +1 prefix codes;

and encoding the omega +1 prefixes to serve as a prefix encoding family of the space-time encoding data in the arbitrary group of space-time processing data.

7. The method of claim 1, wherein the symmetrically encrypting each bloom filter to obtain the encrypted hybrid index tree comprises:

acquiring a safety parameter;

generating a first secret key according to the security parameters;

and symmetrically encrypting each bloom filter by adopting the first key to obtain the encrypted mixed index tree.

8. A privacy-preserving spatio-temporal contact query method is characterized by comprising the following steps:

acquiring a query request containing query data; the query data includes: inquiring spatial position data and inquiring time data corresponding to the inquiring spatial position data;

using a Hilbert curve to encode the query spatial position data in the query data to obtain query processing data including query encoded data and the query time data;

prefix coding is carried out on the inquiry coded data, and a prefix coding family of the inquiry coded data is generated;

according to the prefix code family, obtaining a prefix code corresponding to each layer of the encrypted mixed index tree, and the prefix code corresponding to each layer does not contain a prefix code of a wildcard;

generating a decryption key of each layer according to preset security parameters, the prefix code corresponding to each layer and the prefix code which does not contain wildcard characters in the prefix code corresponding to each layer;

generating a corresponding bloom filter according to the decryption key of each layer, and encrypting the generated bloom filter to obtain a plurality of query bloom filters which are in one-to-one correspondence with the layers of the encrypted mixed index tree;

and taking the plurality of query bloom filters as query tokens, and performing data query from the encrypted mixed index tree by using the query tokens to obtain a query result.

9. The method of claim 8, wherein the encrypted hybrid index tree is composed of parent nodes and child nodes, and wherein the encrypted hybrid index tree comprises omega layers, each layer comprising at least one node, each node corresponding to an encrypted bloom filter; the query token includes: omega query bloom filters in one-to-one correspondence with the omega layers; omega is an integer greater than 1;

the data query from the encrypted mixed index tree by using the query token to obtain a query result includes:

respectively carrying out decryption calculation on the encrypted bloom filters corresponding to each node in the jth layer by adopting the jth query bloom filter corresponding to the jth layer to obtain a first decryption result corresponding to each node; j is 1;

when a first decryption result corresponding to the ith node in the jth layer represents that decryption is successful and the ith node has a first child node, performing decryption calculation on an encrypted bloom filter corresponding to the first child node by adopting a jth +1 query bloom filter corresponding to a jth +1 layer to obtain a second decryption result;

when the second decryption result corresponding to the first child node is determined to represent that decryption is successful and the first child node has a child node, performing decryption calculation on the encrypted bloom filter corresponding to the child node of the first child node by adopting a j +2 th query bloom filter corresponding to a j +2 th layer until the obtained decryption result represents that decryption is successful and the target node corresponding to the decryption result which represents that decryption is successful does not have a child node, and performing matching comparison on the query time data corresponding to the omega-th query bloom filter and the original time data corresponding to the target node by adopting the omega-th query bloom filter;

and when data successfully matched with the query time data exists in the original time data corresponding to the target node, using the data successfully matched with the query time data as the query result.

10. The privacy-preserving spatio-temporal contact query method according to claim 8, wherein the generating of the decryption key of each layer according to preset security parameters, the prefix code corresponding to each layer, and the prefix code not including wildcard in the prefix code corresponding to each layer comprises:

acquiring a safety parameter;

generating a second key according to the security parameter;

generating a sampling value according to the safety parameter;

and generating a decryption key of each layer according to the security parameter, the second key, the sampling value, the prefix code corresponding to each layer and the prefix code which does not contain wildcards in the prefix code corresponding to each layer.

Images