Search As You Want: Authenticated Keyword Search on Graphs with Bounded Leakage

Large-scale graph data are widely used in research and industry, where keyword search serves as a fundamental query paradigm. To reduce costs, data owners commonly outsource graph storage and query processing to cloud service providers, raising concerns about result integrity. Recently, an authenticated graph keyword search scheme was proposed via leveraging the blockchain network, yet it reveals extraneous graph information to the client, incurring structural inference attacks. To solve this issue, we propose PA-GKS, a privacy-aware authenticated graph keyword search scheme with bounded explicit graph leakage of vertex labels and adjacency relations through a decoupled attestation mechanism, where matching roots and answer-trees are attested with different indices independently. We also employ the PGM-index (a learned index) to accelerate the search performance. To further support realistic query requirements, we extend PA-GKS to PA-GKS^*, which enables flexible and customized keyword search with score thresholds. PA-GKS^* introduces a distance-driven tiering strategy and a Merkle tree-chain hybrid index, allowing the two-phase pruning to efficiently prune invalid matching roots. The authenticity and efficiency of our schemes are validated through security analysis and substantial experiments.