GAP: Privacy-Aware and Authenticated Knowledge Graph Queries in Hybrid-Storage Blockchains
Abstract
Hybrid-storage blockchain (HSB) has been a prevailing and efficient storage model in blockchain-based applications. It retains raw data off-chain and only stores metadata on-chain for integrity check to improve scalability. However, for widely provided query services, ensuring query integrity without compromising data privacy is an ongoing challenge in HSB since the off-chain storage provider may be malicious. Existing work has largely focused on authenticated keyword search or range queries over textual data, while several studies on authenticated queries on graph data either ignore user privacy or merely enable user-side verification, with limited support for various graph queries. This paper presents GAP, the first privacy-aware and publicly authenticated scheme for rich queries, including node keyword, edge type, connectivity, and subgraph matching queries, over knowledge graphs in HSB. The core of GAP lies in a novel authenticated data structure (ADS), which incorporates our modified hybrid index and an orthogonal list encrypted with inner product encryption (IPE). With such an ADS, we efficiently perform diverse graph queries with privacy protection, meanwhile generating verification objects (VOs) for public verifiability of the query integrity. Additionally, GAP supports dynamic node/edge updates with forward privacy and update integrity. Security analysis proves that GAP achieves 𝓛-adaptive security with desired privacy and integrity. Comparative experiments on both real-world and synthetic datasets validate that GAP yields a 40%–50% reduction in trapdoor generation. It also outperforms others by over two orders of magnitude in search time, and its on-chain performance is around twice as efficient as the baselines.