CN118312996A - Key value database verifiable range query method and system for freshness guarantee - Google Patents

Abstract

The present invention provides a method and system for verifiable range query of a key-value database with freshness guarantee, which introduces a specific key into the updated data uploaded by the data owner and combines the specific key with the MAC chain structure to ensure the integrity of the range query data storage. The cloud server generates a chain graph storage structure using a chain graph construction algorithm and a broken chain merging algorithm to ensure the freshness of the data at all times. The query user verifies the results fed back by the cloud server based on the validity verification scheme of the bilinear multi-set accumulator to realize the correctness verification of the range query results, and realizes the efficient freshness validity verification of the query results based on the storage verification scheme of the broken chain merging algorithm. Therefore, when there is a potential risk of distrust in the cloud server, the freshness validity of the range query can still be effectively maintained.

Description

A freshness-guaranteed key-value database verifiable range query method and system

Technical Field

The present invention belongs to the technical field of data security, and in particular relates to a verifiable range query method and system for a key-value database with freshness assurance.

Background technique

With the rapid development of information technology, NoSQL databases have been widely studied in large-scale, distributed data storage and processing. Compared with traditional relational databases, NoSQL databases provide a more adaptable data storage method, are good at processing semi-structured and unstructured data, provide strong support for various data formats and structures, and can effectively adapt to changing data needs. In addition, NoSQL databases are known for their horizontal scalability. They can be expanded to handle large data volumes and high concurrent access scenarios. They have significant properties including enhanced scalability, performance, and availability, making them more suitable for contemporary applications that require fast and efficient data processing. From the perspective of data storage, NoSQL databases can be divided into key-value databases, document databases, graph databases, and column databases.

Range query is a common operation in key-value NoSQL databases. It is mainly used to retrieve data subsets that meet specific conditions, that is, a safe range query that allows searching for data belonging to a specific range. In key-value NoSQL, assuming that k represents the key, v represents the value corresponding to the database key k, t represents the corresponding timestamp of the key k update, and Q represents the query range Q = [l, r], then the query result can be expressed as R = {(k, v, t) | l < v < r}, that is, the data subset that meets the range condition is retrieved at the data value level. In the cloud key-value NoSQL storage range query process, due to the semi-trusted characteristics of cloud storage, when users store data in key-value cloud databases, cloud servers may abandon or tamper with data when dynamically maintaining data. When executing a range query, if the queried data set is incomplete and the data version is not fresh, the query result will be wrong. At the same time, due to the semi-trusted characteristics of cloud queries, cloud servers may also return incomplete or tampered query results to the query party during the query.

The existing technologies have proposed many range query verification schemes, but they have some limitations. For example, Zhang et al. [Zhang C, Xu C, Xu J, Tang Y, and Choi B,"Gem^2-tree: A gas-efficient structure for authenticated range queries in blockchain," in 2019IEEE 35th international conference on data engineering (ICDE), 2019, CCF B: IEEE, pp. 842-853] proposed a range query result integrity verification scheme in blockchain; Xu et al. [Xu C, Zhang C, Xu J. vchain: Enabling verifiable boolean range queries over blockchain databases [C] // Proceedings of the 2019 international conference on management of data. 2019: 141-158] proposed a Boolean range query integrity verification scheme in blockchain databases. Xu et al. [Xu Z, Lin Y, Sandor V K A, et al. A lightweight privacy and integrity preserving range query scheme for mobile cloud computing [J]. Computers & Security, 2019, 84: 318-333] used encrypted data indexes and vector neighbor chains (VNC) to achieve data privacy and query result integrity verification. Bajaj et al. [Bajaj S, Chakraborti A, and Sion R, "ConcurDB: Concurrent query authentication for outsourced databases," IEEE Transactions on Knowledge and Data Engineering, vol. 33, no. 4, pp. 1401-1412, 2019] proposed the ConcurDB system, which uses a signature-based range query verification method to decouple query execution and verification processes. The system establishes links based on tuple attributes, completes integrity verification by verifying the links, and uses memory checks to ensure the correctness and integrity of the links. Yao et al. [Yao X, Zhang R, Huang D, and Zhang Y,"Verifiable query processing over outsourced social graph," IEEE/ACM Transactions on Networking, vol. 29, no. 5, pp. 2313-2326, 2021] studied verifiable query processing on outsourced social graphs. Data consumers can verify the integrity of any query results returned by untrusted SDPs, and proposed three schemes for single-attribute range queries and another scheme for multi-attribute range queries on outsourced social data. Yang et al. [Yang W, Liu L, Liu Y, et al. Secure and efficient multi-dimensional range query algorithm over TMWSNs [J]. Ad Hoc Networks, 2022, 130: 102820] proposed an algorithm based on multi-dimensional buckets, which uses buckets as transmission units and the range of perceived data in buckets as indexes to verify the integrity of query results by checking the integrity of query results. However, these schemes that query keys cannot efficiently perform range query verification on data values, and do not support data freshness verification.

Although some works have explored freshness verification schemes based on range queries, so far, these schemes still cannot efficiently perform freshness verification at the data value level. For example, Hong et al. [Hong J, Wen T, Gu Q, et al. Query integrity verification based-on mac chain in cloud storage [C] // 2014 IEEE / ACIS 13th International Conference on Computer and Information Science (ICIS). IEEE, 2014: 125-129] proposed a MAC Chain scheme. The table structure of MAC Chain is R (A1, ..., An, Version, Predecessor, Checksum). Each time the data is updated, the corresponding Version value will increase by 1. The value of Predecessor represents the primary key of the previous data, and the hash value is stored in Checksum. The data owner periodically sends freshness summary information to the trusted third party (TTP) and shares the key and the hash value recorded from the cloud. After the trusted third party receives the freshness summary information, if the tuple version stored in the TTP is less than the version corresponding to the freshness summary, the TTP will be updated. The query user verifies the freshness of the data by comparing the versions of the TTP tuple. After the freshness is verified, the result set is chained. If the result set forms a complete chain from the upper boundary to the lower boundary, the query result is complete. Although this solution can verify freshness to a certain extent, the range query efficiency is very low for multi-interval key value data.

There is also a solution that partially supports freshness verification, but only supports verification at the key level, such as the solution proposed by Hu et al. [HuY, Yao X, Zhang R, et al. Freshness Authentication for Outsourced Multi-Version Key-Value Stores [J]. IEEE Transactions on Dependable and Secure Computing, 2022]. In the outsourcing scenario, this solution slices time and builds an LSK-MHT tree in each slice. The leaf nodes store the key, value and timestamp of the current updated key, and the nodes that have not been updated are merged to store the key and the time slice corresponding to the last update of the key. The integrity of each slice is verified by comparing the root signature, and the latest data of the current key is obtained by the index value of the time slice. The query user verifies the freshness of the data by comparing the timestamp based on the data returned by the cloud server in turn. Although this solution can verify the freshness of range queries of key-value databases, its query verification is for key queries. Although it can be extended to range queries, its performance is limited.

In summary, the prior art has the following disadvantages:

1. For multi-interval key-value data, range query validation at the value level is not supported.

2. For multi-interval key-value data, range query verification is not supported. Instead, point queries are extended to range queries, which is inefficient and does not consider the situation where the cloud server deliberately ignores a time interval and does not perform updates.

3. The existing technology verifies the query results by recording the interval where the latest data is located, or recording the version summary, and the verification complexity is relatively high.

Summary of the invention

In order to solve the above problems existing in the prior art, the present invention provides a method and system for verifiable range query of a key-value database with freshness guarantee. The technical problem to be solved by the present invention is achieved through the following technical solutions:

In a first aspect, the present invention provides a method for verifiable range query of a key-value database with freshness guarantee, comprising:

In the upload phase, the data owner generates data and regularly uploads the updated data and the corresponding MAC chain signature to the cloud server; the updated data includes a specific key kp, and the value corresponding to the specific key kp records a random number associated with the data update time interval;

In the construction phase, the cloud server processes the updated data using a chain graph construction algorithm and a broken chain merging algorithm to construct a chain graph storage structure; receives a query request from a query user requesting to query data of any time interval, and queries the chain graph storage structure in response to the query request to generate verification information and query results, thereby constructing a verification object containing the verification information and returning it to the query user;

In the verification stage, the query user verifies the integrity, freshness and correctness of the query data contained in the query result based on the query result and verification object returned by the cloud server.

In a second aspect, the present invention provides a freshness-guaranteed key-value database verifiable range query system, comprising:

The data owner is used to generate data in the upload phase and regularly upload the updated data and the corresponding MAC chain signature to the cloud server; the updated data includes a specific key kp, and the value corresponding to the specific key kp records a random number associated with the data update time interval;

A cloud server is used for, during the construction phase, using a chain graph construction algorithm and a broken chain merging algorithm to process the updated data to construct a chain graph storage structure; receiving a query request from a query user to query data of any time interval, and querying the chain graph storage structure in response to the query request to generate verification information and query results, thereby constructing a verification object containing the verification information and returning it to the query user;

The query user is used to verify the integrity, freshness and correctness of the query data contained in the query result according to the query result and verification object returned by the cloud server during the verification phase.

Beneficial effects:

1. In view of the first shortcoming of the prior art, the present invention proposes a novel chain graph storage structure to directly perform range queries at the value level.

2. In response to the second shortcoming of the prior art, the present invention proposes a chain graph storage structure and introduces a specific key to efficiently execute range queries and prevent the cloud from not performing updates.

3. In view of the third shortcoming of the prior art, the present invention proposes a path exploration method combined with a bilinear mapping accumulator to implement verification and reduce complexity.

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

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of a system model of the present invention;

FIG2 is a flow chart of a method for verifiable range query of a key-value database with freshness assurance according to the present invention;

3 is a flow chart of a verifiable range query freshness system provided by the present invention;

FIG4 is a diagram showing an example of a chain graph construction algorithm provided by the present invention;

FIG5 is a diagram showing an example of a broken link merging algorithm provided by the present invention;

FIG. 6 is a diagram showing an example of a verification structure provided by the present invention.

Detailed ways

The present invention is further described in detail below with reference to specific embodiments, but the embodiments of the present invention are not limited thereto.

Before introducing the query method of the present invention, a brief introduction is first given to the system model and security model of the present invention.

Referring to FIG1 , FIG1 shows the system model of the present invention, which involves three main participants, namely the data owner, the cloud server, and the query user. In the system, the data owner creates key-value data by slicing at a certain time interval, and regularly uploads the updated data to the key-value NoSQL database of the cloud server in the form of an attached data signature. The cloud server is responsible for the storage of data, and responds to the query user's range query on behalf of the data owner, and sends the query result and freshness validity verification object to the query user. The query user initiates a query, and after receiving the query result and verification object, verifies the query result based on the verification object.

The present invention is based on the following security assumptions, in which the data owner is regarded as a trusted entity and can faithfully perform data upload operations; the cloud server is regarded as a semi-trusted entity, which may maliciously tamper with the data uploaded by the data owner, fail to perform updates and deceive the user data owner that there is no update, or deliberately return tampered, forged or outdated data version query results to the user-initiated query; the query user is regarded as a trusted entity and can faithfully perform queries and verifications. The goal of the present invention is to design a freshness validity verification scheme, so that the freshness validity of range queries can be effectively maintained even when there is a potential risk of distrust in the cloud server.

The knowledge involved in the present invention is briefly introduced below.

1) Hash function

A hash function is a one-way function that converts an input of any length into an output of a fixed length. It is usually difficult to reverse the original data based on the hash value. In cryptography, it is widely used for integrity verification.

2) Message Authentication Code (MAC)

Message Authentication Code, also known as MAC, is a technology commonly used to protect the integrity of data communications. The main idea is to first perform a hash operation on the message content to generate a value of fixed length, and then verify the integrity of the message by comparing the MAC to ensure that the message has not been changed during transmission. MAC chain is a chain protection mechanism, where each message depends on the previous message to form a chain structure. If a message is tampered with, the MAC chain will become invalid.

3)q-Strong Diffie-Hellman (q-SDE)

make is a bilinear mapping pair, For all polynomials q and all probabilistic polynomial-time adversaries Adv, q-SDE satisfies the following formula

Pr[s;p;(c,h)←Adv(σ):h＝e(g,g) ^1/(c+s) ]≈0

4) Bilinear multi-set accumulator

Bilinear multiset accumulators are a generalization of accumulators that can handle multisets, not just general sets. Multisets are different from general sets in that they allow elements to appear multiple times. Bilinear multiset accumulators map multisets to elements in a cyclic multiplicative group in a collision-resistant form. Accumulators can be used to prove that sets are disjoint, and consist mainly of the following algorithms:

KeyGen(1 ^λ )→(sk, pk): input security parameter 1 ^λ , output private key sk and public key pk.

Setup(X, pk) → acc(X): Input the multi-set X and the public key pk, and calculate the cumulative value acc(X). Due to the characteristics of polynomial interpolation, the calculation can be performed without knowing the private key.

ProveDisjoint(X ₁ ,X ₂ ,pk)→π: Input two multisets X ₁ ,X ₂ , where Public key pk, output a proof π.

VerifyDisjoint(acc(X ₁ ), acc(X ₂ ), π, pk) → {0, 1}: Input cumulative values acc(X ₁ ), acc(X ₂ ), proof π, public key pk, if and only if , output 1.

The symbols and abbreviations involved in the present invention are explained below.

Table 1 Description of abbreviations

Table 2 Abbreviations and definitions of key terms

Abbreviations Full name translate MAC Message Authentication Code Message Authentication Code DO Data Owner Data Owner VO Verification Object Verify the object ADS Authenticated Data Structure Verify data structure CGSS Chain Graph Storage Structure Chain graph storage structure

The detailed process of a freshness-guaranteed key-value database verifiable range query method of the present invention is described in detail below.

A verifiable range query method for a key-value database with freshness guarantee of the present invention is divided into three stages: data owner uploads data, cloud server builds chain graph storage structure CGSS and verification object VO, and query and verification by querying user. In the upload stage, the data owner DO regularly uploads the updated data D and MAC chain signature sign(H(D)) to the cloud server. In the cloud server construction stage, two parts are involved: 1. The cloud server constructs the chain graph storage structure CGSS according to the chain graph construction algorithm and broken chain merging algorithm proposed in the present invention. 2. The query user initiates a range query Q, and the cloud server generates a verification structure ADS and a query result R based on the query, constructs a verification object VO containing result verification information, VO={sign(H(D)), ADS, π, acc(X)}, and returns VO and the result R to the query user. In the verification stage, the query user verifies the data integrity, freshness, and correctness based on the result R and VO returned by the cloud server.

In conjunction with FIG. 2 and FIG. 3 , the present invention provides a key-value database verifiable range query method with freshness assurance, including:

1. In the upload phase, the data owner generates data and regularly uploads the updated data and the corresponding MAC chain signature to the cloud server; the updated data includes a specific key kp, and the value corresponding to the specific key kp records a random number associated with the data update time interval;

1.1. Update data

The data owner DO generates data; if the data is updated at any time interval, the MAC chain hash value H(D) of each updated data D in the time interval is calculated; the MAC chain hash value H(D) is signed to obtain a signature sign(H(D)), and the updated data D and the signature sign(H(D)) are uploaded to the cloud server; wherein the updated data includes a key-value storage and an introduced specific key kp, the key-value storage is composed of a combination of data records, each data record contains a unique key k∈K and a data value, the data value receives different versions at different time intervals, each version corresponds to an update node, represented as o, o=(k, v, t), the value corresponding to the specific key kp records a random number associated with the data update time interval.

Each interval data owner uploads a random number signature to prevent the cloud server from not updating. Regardless of whether there is valid data update, once the cloud discards the data, as long as there is data update in the subsequent interval, it will be discovered. Therefore, assuming that the key is represented by K = {1, ..., |K|}, if all data are updated in time interval 1, the updated data is k∈{1,...,|K|), At time interval i, if the data owner updates some keys, if the update keys are sorted in ascending order Let α = ks ⁱ [1] be the first key value of ks ⁱ , then the updated data is expressed as

1.2. Generate MAC chain

The data owner DO calculates each update node of time interval i in turn Hash value And the hash value Link them into a MAC chain in key order, expressed as α＝ks ⁱ [1];

The MAC chain H(D _i ) is signed to generate sign(H(D _i )), and the data owner DO uploads the updated data D _i and the signature sign(H(D _i )) to the cloud server.

2. In the construction phase, the cloud server processes the updated data using the chain graph construction algorithm and the broken chain merging algorithm to construct a chain graph storage structure; receives a query request from a query user requesting to query data of any time interval, and responds to the query request to query the chain graph storage structure to generate verification information and query results, thereby constructing a verification object containing the verification information and returning it to the query user;

2.1. Cloud server builds chain graph storage structure

a. The cloud server sets the construction rules of the chain graph construction algorithm.

The chain graph construction algorithm of the present invention is introduced below.

The construction rule of the chain graph construction algorithm of the present invention is: except for the update data of the first time interval, the update data of each other time interval is constructed by the last update node of the corresponding key Point to the current node Right pointer If the current node Next adjacent key node If there is an update, build a downward pointer Otherwise construct a left pointer Let the pointer set _Pi = {pi _,1,1 ,..., _pi,i,k }, where, If the node is deleted at time interval i The corresponding pointer set p _i,j,k = NULL.

The algorithm based on the above rules is shown in Algorithm 1:

b. In time interval i, recursively construct each updated node in the time interval i using the chain graph construction algorithm containing the construction rule and the chain graph storage structure of the previous time interval The corresponding pointers of and form a pointer set;

The cloud server receives the data uploaded by the data owner in this interval i, and updates it based on the chain graph storage structure CGSS _i-1 constructed last time to form this chain graph storage structure CGSS _i . The storage structure is CGSS _i = {B _i , _Pi } in the i interval, where _Bi is the data node set and Pi is the chain pointer set. _Bi is first obtained by Bi _-1 through the chain graph construction algorithm to obtain B′ _i = Bi _-1 ∪D _i , and then B′ _i is subjected to the broken chain merging algorithm. According to the algorithm, the deleted node set S _i and the merged node set M _i are selected to obtain _Bi = B′ _i -S _i +M _i , where the deleted nodes are composed of the nodes that originally need to be deleted or merged to cause deletion; _Pi is first obtained by _Di and Pi _-1 through the chain graph construction algorithm to obtain P′ _i = Pi _-1 +DP _i , where DP _i is the pointer set of each node of _Di , and then P′ _i is subjected to the broken chain merging algorithm. According to the algorithm, the chain set CP _i to be disconnected is selected to obtain _Pi = P′ _i /CP _i .

c. Construct a preliminary chain graph storage structure within time interval i using the pointer set within time interval i, all updated data, and the chain graph storage structure of the previous time interval;

d. Utilize the broken link merging algorithm to optimize the preliminary chain graph storage structure within the time interval i to obtain the chain graph storage structure within the time interval i.

The broken link merging algorithm of the present invention is described in detail below.

The broken link merging algorithm mainly performs broken links in a path exploration manner and merges the expired version data of the same key to reduce the number of nodes in the verification process, and finally outputs the interval chain graph storage structure CGSS _i . The broken link merging algorithm mainly involves deleting and merging nodes in the B′ _i set and breaking the pointers in the P′ _i set. Assume Indicates a single node or a node after multiple nodes are merged. k is the key, ct _i is the merged node in the i interval involving the interval set, assuming that there is a single node in interval i′ After merging, it is expressed as Store {k, ct _i′ }, then ct _i′ = {i′}. Continue with the interval i node If i>i′ is merged, the interval i needs to be added to ct _i , then the merged node is Store {k, ct _i }, where ct _i = {i′, i}. Delete the node before merging And merge the nodes Store to interval i. If the interval where the pointer of key k-1 points to key k is i″, the earliest interval of ct _i is i′ and the interval where the pointer of key k points to k+1 is i″′, and min(i″, i″′)＞i′ is satisfied, then ct _i also needs to delete all intervals before min(i″, i″′). The specific broken link merging algorithm is shown in Algorithm 2:

The cloud server recursively constructs CGSS _i for the update data _Di sent by DO according to the above chain graph construction algorithm and broken chain merging algorithm. When i=1, k∈K. According to the chain graph construction algorithm, construct direction Down pointer direction Down pointer at this time The interval data is the latest data, and there is no need to break the chain and merge, forming a chain graph storage structure CGSS _1. When i≠1, assuming that the i interval part of the key is updated, update the data α＝ks ⁱ [1]， In this step, the broken link merging algorithm is used to perform path exploration from the first key to the last key on the preliminary chain graph storage structure CGSS′ _i = {B′ _i , P′ _i ), B′ _i = Bi _-1 ∪D _i ; P′ _i = Pi _-1 +DP _i within the time interval i, and the latest data of each key is explored first; then the path to the next key is explored, and irrelevant nodes on the way to the next key are deleted or merged to obtain the chain graph storage structure CGSS _i = {B _i , P _i }, B _i = B′ _i -S _i +M _i ; P _i = P′ _i /CP _i within the time interval i; if all keys are updated within the time interval i, the time interval i = 1 is reset.

For example, given the updated data as shown in Table 3, the data table has 7 keys and 4 intervals. Each key corresponds to a grid in different intervals. If the grid is empty, it means that the corresponding key has no updated data in the interval. If there is data, it indicates the specific value of the key updated in the interval. Figure 4 shows the final output structure diagram of the chain graph construction algorithm for the first 4 intervals. Figure 5 shows the chain graph storage structure diagram of the broken chain merge output based on Figure 4.

Table 3. Update data example

2.2 Query User-Generated Queries

The query user initiates a range query _Qi = [l, r] at interval i, requiring the return of all (k, v, t) tuples that meet the conditions, where v∈[l, r], and the query results are required to be valid and fresh. Let _X1 = {l, l+1, ..., r), A bilinear pairing is defined where and are two cyclic multiplicative groups with the same prime order p, e is the identity element, g is the generator, and a random number belonging to the integer ring is selected The number a is used as the private key s, then the public key is Query user calculation And send p(X ₁ ), pk and query interval i to the cloud server.

2.3 Cloud Server Builds Verification Object VO

The server receives a query request _Qi = [l, r] initiated by a query user at a time interval i, wherein the range query request requires the return of all (k, v, t) tuples that meet the conditions, as well as p( _X1 ), pk and the query time interval i; constructs a verification structure _ADSi using the p( _X1 ), pk and the query time interval i, and generates a verification object _VOi and a query result set _Ri .

2.3.1 Building ADS

On the basis of the chain graph storage structure CGSS _i = {B _i , _Pi }, where _Pi = {pi _{, 1, 1} , ..., _{pi, i, k} }, the latest value of each key in CGSS _i = {B _i , _Pi } is mapped to an integer ring The accumulator determines whether each node is in range and adds all the latest nodes that are not in range. inner The value is added to the set X ₂ ;

Map the set _X2 to the ring of integers and calculate the cumulative values of p(X ₁ ) and p(X ₂ ) If the current node and adjacent nodes of If the value is not in the range, it will be merged and the merged node Store it in the k-1 position of the first key involved before merging to obtain the verification structure ADS _i ; if there is a single merged node for the adjacent keys, perform column-wise merging to obtain the verification structure ADS _i ; except for the last node Except for the corresponding downward nodes, all other nodes involved are deleted. Store {{k-1, k), i); the latest node in the range The query result set R _i is formed.

Continuing with the example in Table 3, if the interval is 3, and the query user query range is [5, 7], then the verification structure ADS ₃ is as shown in FIG6 .

2.3.2 Constructing VO

Combined with the above verification structure ADS, the verification object VO is constructed. According to p(X ₁ ) and p(X ₂ ), Q ₁ , Q ₂ and the proof that they are not in the range are calculated. Sign the MAC hash sign (H (D _i )), verify the structure ADS _i , and store the fresh node in the chain graph structure CGSS _i The accumulated value acC(X ₂ ) and the out-of-range proof π _i constitute the verification object VO _i ={sign(H(D _i )), ADS _i , π _i , acc(X ₂ )}.

3. In the verification phase, the query user verifies the integrity, freshness and correctness of the query data contained in the query result based on the query result and verification object returned by the cloud server.

The query user receives the query result set R _i and the verification object VO _i ={sign(H(D _i )), ADS _i , π _i , acc(X ₂ )} returned by the cloud server;

The querying user calculates the signature sign(H(AD _i )) of the data AD _i in the time interval i in the verification structure ADS _i , and compares whether sign(H(AD _i )) and sign(H(D _i )) are equal. If they are equal, it indicates that the query data is complete;

It is worth noting that: since the data merged horizontally in the chain graph verification structure are all on the left side of the latest data, even if the data is tampered with, it will not affect the latest data. Therefore, in the present invention, the horizontally merged data does not participate in the integrity verification, as long as it proves that the latest data of each key has not been discarded or tampered with. Since the data owner uploads a signed random number rand_value(i) for each interval, once the cloud server discards the interval data without updating it, it will be detected as long as there is data update in the subsequent interval. Let AD _i be the data of each interval i in ADS _i . The query user verifies the integrity by calculating sign(H(AD _i )) and comparing whether sign(H(AD _i )) and sign(H(D _i )) are equal. If they are equal, the data is complete.

The query user, if comparing each node in the query result set _Ri Corresponding node to ADS _i Timestamp and Are they equal? If they are equal, it means that the query data is fresh data;

It is worth noting that for freshness, the query user combines the path exploration method to build ADS _i to verify that the latest data of each key is retained. On the basis of verifying the integrity and correctness of ADS _i , at this time, each updated node in ADS _i All are the latest data uploaded by the data owner without tampering. Query the user to compare each node in the result set R _i Corresponding node to ADS _i Timestamp and Are they equal? If they are, it means that the query results returned by the cloud are based on fresh data.

The query user compares each node of the query result set R _i and ADS _i , judge Whether it is within the query scope, the cloud server will provide proof for fresh data that is not within the scope

The querying user verifies using π _i and acc(X ₂ ) Are they equal to e(g, g)? If they are equal, it means that the data is indeed not within the query range; if the data are not equal, it is confirmed that the cloud server has tampered with the data.

It is worth noting that for correctness, the query user compares each node of the returned result set R _i and ADS _i , it can be determined Whether it is within the query scope. For fresh data that is not within the scope, the cloud server will provide a certificate Using π _i and acc(X ₂ ), query user authentication If they are equal, it means that the data is indeed not within the query range. If the data is not equal, the querying user will find that the cloud server has tampered with the data.

If all the above verifications pass, it proves that the query results are fresh and valid.

In a second aspect, the present invention provides a key-value database verifiable range query system with freshness guarantee, comprising:

The data owner is used to generate data in the upload phase and regularly upload the updated data and the corresponding MAC chain signature to the cloud server; the updated data includes a specific key kp, and the value corresponding to the specific key kp records a random number associated with the data update time interval;

A cloud server is used for, during the construction phase, using a chain graph construction algorithm and a broken chain merging algorithm to process the updated data to construct a chain graph storage structure; receiving a query request from a query user to query data of any time interval, and querying the chain graph storage structure in response to the query request to generate verification information and query results, thereby constructing a verification object containing the verification information and returning it to the query user;

The query user is used to verify the integrity, freshness and correctness of the query data contained in the query result according to the query result and verification object returned by the cloud server during the verification phase.

The specific details of the system implementation and method implementation of the present invention are the same and will not be repeated here.

The present invention provides a method and system for verifiable range query of a key-value database with freshness guarantee, which introduces a specific key into the updated data uploaded by the data owner and combines the specific key with the MAC chain structure to ensure the integrity of the range query data storage. The cloud server generates a chain graph storage structure using a chain graph construction algorithm and a broken chain merging algorithm to ensure the freshness of the data at all times. The query user verifies the results fed back by the cloud server based on the validity verification scheme of the bilinear multi-set accumulator to realize the correctness verification of the range query results, and realizes the efficient freshness validity verification of the query results based on the storage verification scheme of the broken chain merging algorithm. Therefore, when there is a potential risk of distrust in the cloud server, the freshness validity of the range query can still be effectively maintained.

In addition, the terms "first" and "second" are used for descriptive purposes only and should not be understood as indicating or implying relative importance or implicitly indicating the number of the indicated technical features. Therefore, the features defined as "first" and "second" may explicitly or implicitly include one or more of the features. In the description of the present invention, the meaning of "plurality" is two or more, unless otherwise clearly and specifically defined.

Although the present application is described herein in conjunction with various embodiments, in the process of implementing the claimed application, those skilled in the art may understand and implement other variations of the disclosed embodiments by viewing the drawings, the disclosure, and the appended claims. In the claims, the word "comprising" does not exclude other components or steps, and "a" or "an" does not exclude a plurality of components or steps.

The above contents are further detailed descriptions of the present invention in combination with specific preferred embodiments, and it cannot be determined that the specific implementation of the present invention is limited to these descriptions. For ordinary technicians in the technical field of the present invention, several simple deductions or substitutions can be made without departing from the concept of the present invention, which should be regarded as falling within the scope of protection of the present invention.

Claims (10)

1. The key value database verifiable range query method for ensuring freshness is characterized by comprising the following steps of:

In the uploading stage, a data owner generates data and periodically uploads updated data and a corresponding MAC chain signature to a cloud server; the updating data comprises a specific key kp, wherein a value corresponding to the specific key kp records a random number associated with a data updating time interval;

In the construction stage, the cloud server processes the updated data by using a chain map construction algorithm and a broken chain merging algorithm to construct a chain map storage structure; receiving a query request of a query user for querying any time interval data, querying the chain map storage structure in response to the query request to generate verification information and a query result, thereby constructing a verification object containing the verification information and returning the verification object to the query user;

In the verification stage, the query user verifies the integrity, freshness and correctness of the query data contained in the query result according to the query result and the verification object returned by the cloud server.

2. The freshness guarantee key database verifiable range query method of claim 1, wherein the uploading stage, the data owner uploading the update data and the corresponding chain signature to the cloud server periodically, comprises:

the data owner DO generates data;

if the data in any time interval is updated, calculating a MAC chain hash value H (D) of each updated data D in the time interval;

Signing the MAC chain hash value H (D) to obtain a signature sign (H (D)), and uploading updated data D and the signature sign (H (D)) to a cloud server;

Wherein the update data comprises a key value store and an introduced specific key kp, the key value store is composed of a combination of data records, each data record comprises a unique key K epsilon K and a data value, the data value receives different versions at different time intervals, each version corresponds to an update node and is expressed as o, o= (K, v, t), and the value corresponding to the specific key kp records a random number associated with the data update time interval.

3. The freshness protection key database verifiable range query method as claimed in claim 2, wherein if all data is updated in time interval 1, the updated data isk∈{1,…,|K|}，At time interval i, if the data owner updates part of the keys, the updated keys are arranged in ascending orderLet α=ks ⁱ [1] be the first key of ks ⁱ, then the update data is expressed as

4. The freshness guarantee key value database verifiable range query method of claim 3, wherein signing the MAC chain hash value H (D) to obtain a signature sign (H (D)), and uploading the update data D and the signature sign (H (D)) to a cloud server comprises:

The data owner DO calculates each update node of the time interval i in turn Hash value of (a)And hash the valueLinking into MAC chains in key order, denoted asα＝ksⁱ[1]；

The MAC chain H (D _i) is signed to generate sign (H (D _i)), and the data owner DO uploads the update data D _i and the signed sign (H (D _i)) to the cloud server.

5. The freshness assured key database verifiable range query method of claim 3, wherein, at the build stage, said cloud server processing said update data to build a chain map storage structure using a chain map build algorithm and a broken-chain merge algorithm comprises:

in the construction stage, the cloud server is configured to:

setting a construction rule of a chain diagram construction algorithm; the construction rule is as follows:

the update data of each time interval except the update data of the first time interval constructs the last update node of the corresponding key Pointing to the current nodeRight pointer of (2)If the current nodeAdjacent next key nodeWith updates, then the down pointer is constructedOtherwise construct left pointerLet the set of pointers P _i＝{p_i,1,1,…,p_i,i,k, wherein,If node is deleted in time interval iIts corresponding pointer set p _i,j,k = NULL;

Within a time interval i, recursively constructing each updated node within the time interval i by using a chain graph construction algorithm containing the construction rule and a chain graph storage structure of the previous time interval Corresponding pointers of the corresponding pointers, and forming a pointer set;

constructing a preliminary chain diagram storage structure in the time interval i by utilizing the pointer set in the time interval i, all updated data and the chain diagram storage structure of the previous time interval;

And optimizing the preliminary chain map storage structure in the time interval i by using a chain breaking merging algorithm to obtain the chain map storage structure in the time interval i.

6. The method for querying a verifiable range of a freshness ensured key-value database according to claim 5, wherein optimizing the preliminary chain-map storage structure in the time interval i by using a broken-chain merging algorithm to obtain the chain-map storage structure in the time interval i comprises:

The method comprises the steps of utilizing a broken-link merging algorithm to search a path of a preliminary chain diagram storage structure CGSS′_i＝{B′_i,P′_i},B′_i＝B_i-1∪D_i;P′_i＝P_i-1+DP_i, from a first key to a last key in a time interval i, and searching the latest data of each key; the path to the next key is explored again, and irrelevant nodes on the path to the next key are deleted or merged to obtain a chain map storage structure CGSS_i＝{B_i,P_i},B_i＝B′_i-S_i+M_i;P_i＝P′_i/CP_i; in a time interval i, and if all keys are updated in the time interval i, the time interval i=1 is reset.

7. The method for querying a verifiable range of a key-value database for ensuring freshness according to claim 6, wherein the steps of receiving a query request for querying data at any time interval from a querying user, querying the chain map storage structure in response to the query request to generate verification information and a query result, thereby constructing a verification object containing the verification information, and returning the verification object to the querying user comprise:

The server receives a query request Q _i = [ l, r ] initiated by a query user at a time interval i, wherein the range query request requires to return all qualified (k, v, t) tuples, p (X ₁), pk and the time interval i of the query;

Wherein v is [ l, r ], X₁＝{l,l+1,…,r}，Defining a bilinear pair, whereinAndFor two cyclic multiplication groups with the same prime order p, e is a unit element, g is a generator element, and the two cyclic multiplication groups are randomly selected to belong to an integer ringThe public key is the private key s

Using the p (X ₁), pk and the time interval i of the query, a verification structure ADS _i is constructed, and a verification object VO _i and a query result set R _i are generated.

8. The freshness ensured key database verifiable range query method of claim 7, wherein constructing a verification structure ADS _i using p (X ₁), pk and a time interval i of the query, and generating a verification object VO _i and a query result set R _i comprises:

mapping each key up-to-date value in GCSS _i＝{B_i,P_i to an integer ring Determining whether each node is in range by accumulator and updating all nodes not in rangeLining of the bagThe value is added to the set X ₂;

Mapping set X ₂ to integer rings And calculates the cumulative value of p (X ₁) and p (X ₂) If the current nodeAnd adjacent nodeA kind of electronic deviceIf the value is not in the range, merging, and merging the merged nodesThe k-1 position of the first key involved before merging is stored to obtain a verification structure ADS _i; if a single combined node exists in the adjacent keys, performing column-direction combination to obtain a verification structure ADS _i;

Wherein the last node is divided Except that the corresponding down node is not deleted, the remaining involved nodes are deleted,Storing { { k-1, k }, i };

Nodes that will be up-to-date in range Forming a query result set R _i;

Calculation of Q ₁,Q₂ from p (X ₁) and p (X ₂) and proof of being out of range

The MAC hash is signed (H (D _i)), structure ADS _i is validated, and fresh nodes in the chain graph storage structure CGSS _i Is (X ₂) and does not prove within range that pi _i constitutes the verification object VO _i＝{sign(H(D_i)),ADS_i,π_i,acc(X₂).

9. The method for querying a verifiable range of a key-value database for ensuring freshness according to claim 8, wherein in a verification stage, the querying user verifies the integrity, freshness and correctness of the query data contained in the query result according to the query result and the verification object returned by the cloud server, wherein the verification stage comprises:

The query user receives a query result set R _i and a verification object VO _i＝{sign(H(D_i)),ADS_i, π_i,acc(X₂) returned by the cloud server;

The inquiring user calculates signature sign (H (AD _i)) of data AD _i of a time interval i in the verification structure ADS _i, compares whether sign (H (AD _i)) and sign (H (D _i)) are equal, and if so, indicates that the inquiring data are complete;

The querying user, if comparing each node in the query result set R _i Node corresponding to ADS _i Time stamp of (a)AndWhether the query data are equal, if so, indicating that the query data are fresh data;

The query user compares each node of the query result set R _i And ADS _i, judgeWhether it is within the query range, the cloud server gives a proof of fresh data that is not within the range

The querying user verifies with pi _i and acc (X ₂)If equal to e (g, g), the description data is not in the query range; and if the data are not equal, confirming that the cloud server tampers the data.

10. A freshness-assured key-value database verifiable range query system, comprising:

The data owner is used for generating data in the uploading stage and uploading the updated data and the corresponding MAC chain signature to the cloud server at regular intervals; the updating data comprises a specific key kp, wherein a value corresponding to the specific key kp records a random number associated with a data updating time interval;

the cloud server is used for processing the updated data by utilizing a chain diagram construction algorithm and a broken chain merging algorithm in a construction stage so as to construct a chain diagram storage structure; receiving a query request of a query user for querying any time interval data, querying the chain map storage structure in response to the query request to generate verification information and a query result, thereby constructing a verification object containing the verification information and returning the verification object to the query user;

and the query user is used for verifying the integrity, freshness and correctness of the query data contained in the query result according to the query result and the verification object returned by the cloud server in the verification stage.