EFKG: An Efficient and Fine-Grained Access Control Encrypted Knowledge Graph

Abstract

As knowledge graphs are increasingly applied in sensitive domains such as healthcare, ensuring data confidentiality and fine-grained access control over outsourced graph data has become critical. In this paper, we propose EFKG, an Efficient and Fine-grained Access Control Encrypted Knowledge Graph construction scheme that simultaneously achieves data confidentiality, fine-grained access control, and high-performance multi-hop search over encrypted knowledge graphs. Compared with existing approaches, EFKG not only supports efficient single-hop and multi-hop retrieval with O(1) complexity per hop, but also satisfies fine-grained access control requirements in multi-user settings. Regarding security, we rigorously prove that EFKG achieves L-adaptive security under the standard leakage function paradigm. Extensive experiments on real-world datasets confirm that EFKG achieves microsecond-level single-hop search and scalable multi-hop traversal, offering a superior trade-off between efficiency, security, and functionality.