Private reachability queries on structured encrypted temporal bipartite graphs

Publication Type

Journal Article

Publication Date

3-2025

Abstract

A temporal bipartite graph is a graph model that incorporates time-related information into its edges, making it suitable for modeling real-world phenomena like disease outbreaks. However, this temporal information is often sensitive. To protect the privacy of graph data, researchers have explored various approaches to preserve privacy in graph queries, with reachability queries being popular and fundamental as they determine the possibility of reaching one node from others in a graph. While privacy-preserving reachability queries have been extensively studied, existing efforts often overlook the valuable attribute information present in both edges and nodes of the graphs. Moreover, reachability queries on temporal bipartite graphs have not received sufficient attention in the literature. To bridge this gap, we propose a novel approach to achieve various private reachability queries on structured encrypted temporal bipartite graphs (RQ-STBG) through a real-world scenario. Specifically, we construct a minimal index using hierarchical 2-hop labels and integrate structured encryption, order-revealing encryption, and garbled Bloom filters to support reachability queries with different label constraints. The proposed scheme is flexible and can cater to the query requirements of diverse users. Security analysis and experimental evaluations demonstrate that the proposed scheme achieves both preferable security and efficiency.

Keywords

Temporal bipartite graph, reachability query, privacy preserving, 2-hop label, structured encryption, garbled Bloom filte

Discipline

Information Security

Research Areas

Information Systems and Management

Publication

IEEE Transactions on Dependable and Secure Computing

Volume

22

Issue

2

First Page

1810

Last Page

1826

ISSN

1545-5971

Identifier

10.1109/TDSC.2024.3473808

Publisher

Institute of Electrical and Electronics Engineers

Additional URL

https://doi.org/10.1109/TDSC.2024.3473808

This document is currently not available here.

Share

COinS