Beyond Access Pattern: Efficient Volume-Hiding Multi-Range Queries Over Outsourced Data Services

doi:10.1109/TIFS.2025.3540576

Beyond Access Pattern: Efficient Volume-Hiding Multi-Range Queries Over Outsourced Data Services

2025-01-01

0

PRE

AI

DOI：10.1109/TIFS.2025.3540576

Original

Original request for help

Save

Abstract

En 中文

Multi-range query (MRQ) is a typical multi-attribute data query widely used in various practical applications. It is capable of searching all data objects contained in a query request. Many privacy-preserving MRQ schemes have been proposed to realize MRQ on encrypted data. However, existing MRQ schemes only consider the security threat caused by access pattern leakage, not the harm of volume pattern leakage. Moreover, most existing schemes cannot achieve efficient queries and updates while preserving the access pattern. In this paper, we propose an efficient MRQ scheme for hiding volume and access patterns. We first design a joint data index using Order-Revealing Encryption (ORE) and Pseudo-random functions (PRFs) to realize volume-hiding range queries. Then, we combine the private set intersection (PSI) and hardware Software Guard Extensions (SGX) to compute each attribute's intersection of query results. In addition, we preserve access patterns during queries by designing a batch refresh algorithm and an update protocol. Finally, rigorous security analysis and extensive experiments demonstrate the security and performance of our scheme in real-world scenarios.

Keywords:

Cryptography

Indexes

Encryption

Servers

Protocols

Protection

Electronic mail

Hardware

Information leakage

Fans

Privacy-preserving multi-range query

volume pattern

access pattern

hardware SGX

Beyond Access Pattern: Efficient Volume-Hiding Multi-Range Queries Over Outsourced Data Services

Abstract

Journal

Organization