An Efficient Graph Encryption Scheme Supporting Shortest Path Fuzzy Queries

Graph encryption is a form of searchable encryption that enables a cloud server to handle private queries on graphs. Ghosh, Kamara, and Tamassia (ASIA CCS 2021) proposed the first graph encryption scheme (GES) that supports single-pair shortest path (SPSP) queries. This means that given two vertices in a graph, the scheme can return the shortest path between them. In traditional SPSP queries, clients are required to provide complete and precise information about their departure and destination points. However, in real-life situations, individuals often only have a general idea of their intended locations, lacking specific details. To address this issue, we introduce a new type of SPSP query known as the SPSP fuzzy query, which accommodates this uncertainty. In addition, we propose PathFQ-GES, an efficient graph encryption scheme that supports both conventional SPSP queries and the new SPSP fuzzy queries. PathFQ-GES utilizes a novel data structure along with the SP-matrix (ASIA CCS 2021) to effectively perform these query functions while maintaining adaptive security based on the defined leakage profile of PathFQ-GES. We take a method that executes the GKT scheme multiple times for SPSP fuzzy queries as the baseline and have experimentally validated the performance of PathFQ-GES on nine real-world datasets. The results show that PathFQ-GES can effectively handle the proposed SPSP fuzzy queries. It can achieve a decrease of over 50% in response time compared to the baseline.