Beyond result verification: Efficient privacy-preserving spatial keyword query with suppressed leakage

Publication Type

Journal Article

Publication Date

1-2024

Abstract

Boolean range query (BRQ) is a typical type of spatial keyword query that is widely used in geographic information systems, location-based services and other applications. It retrieves the objects inside the query range and containing all query keywords. Many privacy-preserving BRQ schemes have been proposed to support BRQ over encrypted data. However, most of them fail to achieve efficient retrieval and lightweight result verification while suppressing access and search pattern leakage. Thus, in this paper, we propose an efficient verifiable privacy-preserving Boolean range query with suppressed leakage. Firstly, we convert BRQ into multi-keyword query by using Gray code and Bloom filter. Then, we achieve efficient oblivious multi-keyword query by combining distributed point function and PRP-based Cuckoo hashing, which protects the access and search patterns. Moreover, we support lightweight and oblivious result verification based on oblivious query, aggregate MAC, keyed-hashing MAC and XOR-homomorphic pseudorandom function. It enables query users to verify the result integrity with a proof whose size is independent of the size of the outsourced dataset. Finally, formal security analysis and extensive experiments demonstrate that our proposed scheme is adaptively secure and efficient for practical applications, respectively.

Keywords

access pattern, Privacy-preserving Boolean range query, result verification, search pattern

Discipline

Information Security

Research Areas

Cybersecurity

Publication

IEEE Transactions on Information Forensics and Security

Volume

19

First Page

2746

Last Page

2760

ISSN

1556-6013

Identifier

10.1109/TIFS.2024.3354414

Publisher

Institute of Electrical and Electronics Engineers

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/TIFS.2024.3354414

This document is currently not available here.

Share

COinS