(α, β)-Core Query on Structured Encrypted Bipartite Graph

Yulin Wu

doi:10.1109/tdsc.2026.3714883

(α, β)-Core Query on Structured Encrypted Bipartite Graph

2026-07-20

0

PRE

AI

DOI：10.1109/tdsc.2026.3714883

Original

Original request for help

Save

Abstract

En 中文

An essential task in bipartite graph analysis is computing the $(\alpha, \beta )$-core based on specified $\alpha$ and $\beta$ values. Existing methods often sacrifice user data security to enhance efficiency and accuracy, either by traversing the entire bipartite graph or pre-processing multiple $(\alpha, \beta )$ combinations. While recent efforts have introduced privacy-preserving schemes for efficient $(\alpha, \beta )$-core queries, they primarily focus on node cohesion, overlooking valuable information embedded in both nodes and edges. In practical applications, analyzing both node and edge attributes is crucial for deriving meaningful insights. In this paper, we propose a novel approach for privacy-preserving $(\alpha, \beta )$-core queries on bipartite graphs: (1) Efficient core computation: Instead of pre-processing all $(\alpha, \beta )$ combinations, we construct index tables and dynamically generate the adjacency matrix in real-time for $(\alpha, \beta )$-core computation. (2) Privacy-preserving query: We design a structured encryption scheme for bipartite graphs, integrating a secure comparison protocol and a secure minimum value protocol based on symmetric homomorphic encryption to ensure privacy protection. (3) Optimized graph traversal: To avoid traversing the entire bipartite graph, we employ a bipartite graph coloring method, leveraging partition index tables and degree tables to efficiently identify query vertices that meet the specified degree constraints. (4) Extended query capabilities: Our $(\alpha, \beta )$-core query method supports privacy-preserving $(\alpha, \beta )$-weighted community ($(\alpha, \beta )$-WC) and $(\alpha, \beta )$-attribute weighted community ($(\alpha, \beta )$-AWC) queries. (5) Performance and security evaluation: Experimental results on real datasets show that the $(\alpha, \beta )$-WC query on ciphertext incurs an overhead of 0.49X to 4.89X compared to its plaintext counterpart, while the $(\alpha, \beta )$-AWC query incurs an overhead of 0.74X to 4.52X. Additionally, rigorous security analysis validates the robustness of our proposed scheme.

Keywords:

Bipartite graphs

structured encryption

$(\alpha, \beta )$ ( α , β ) -core

symmetric homomorphic encryption

privacy preserving

(α, β)-Core Query on Structured Encrypted Bipartite Graph

Abstract

Journal

Organization