FRQ: Fast Range Query Over Large-Scale Encrypted Key-Value Data

Yinbin Miao

doi:10.1109/TSC.2024.3463397

FRQ: Fast Range Query Over Large-Scale Encrypted Key-Value Data

2024-11-01

0

PRE

AI

DOI：10.1109/TSC.2024.3463397

Original

Original request for help

Save

Abstract

En 中文

With the rapid growth of data size, a large number of data providers outsource their private data to cloud servers to reduce the high storage and computation burdens, but it also leads to security issues such as privacy leakage. Therefore, many privacy-preserving range query schemes have been proposed. However, most of existing secure range query schemes suffer from low query efficiency and expensive computation and update overheads. To address these issues, we propose a novel Fast Range Query (FRQ) scheme for large-scale encrypted Key-Value (KV) data. First, we introduce REMIX, a space-efficient KV index data structure based on Log-Structured Merge-trees (LSM-trees), which maintains a global sorted view of KV pairs across multiple table files for efficient range queries. Besides, we exploit the write-efficiency compression strategy of LSM-trees to ensure efficient dynamic data updates. Finally, we use Czech Havas Majewski (CHM) to protect the index structure, which reduces the computation overhead and ensures the retrieval accuracy. Formal security analysis proves that our scheme can achieve an acceptable level of security. Extensive experiments demonstrate that our scheme improves the query efficiency by nearly $8\times$8x and update efficiency by $7\times$7x compared to state-of-the-art solutions over million-level datasets.

Keywords:

Indexes

Encryption

Filters

Data structures

Hash functions

Complexity theory

Nearest neighbor methods

Czech HavasMajewski (CHM)

key-value data range query

LSM-tree

REMIX

FRQ: Fast Range Query Over Large-Scale Encrypted Key-Value Data

Abstract

Journal

Organization