Scholarlink

<p>The problem of querying shortest distance on a graph has attracted significant research attention due to the widespread applicability of graphs and the ability of graph shortest path queries to address numerous application problems. Given the limited capabilities of clients and the ongoing advancements in cloud computing, people would like to outsource their graph data. Outsourcing data, however, poses the problem of privacy breaches. We should enable clients to encrypt their data before outsource it to cloud servers while retaining the capability of querying the data. The major challenge lies in designing a scheme computing the shortest distance on encrypted graph is how to strike a balance between security, efficiency and accuracy. Moreover, this challenge becomes even more pronounced as the scale of the graph increases. In this article, we propose an efficient scheme called Encrypted Shortest Distance Approximate Query (<i>ESDAQ</i>). We design a new algorithm<i> k</i>-level <i>BFS</i> and make use of cryptographic primitive AES to fulfill the scheme where <i>k</i> is an optional parameter selected by user. The total time cost can be <i>O</i>(<i>N</i>) at best to finish setup and query, which is superior to SOTA solutions of <i>O</i>(<i>NlogN</i>). Theoretical security analysis shows that <i>ESDAQ</i> can reach<i> CQA2</i>-security . Theoretical analysis on security, performance and accuracy are provided of our proposed scheme. Meanwhile, experiments on 12 representative real-world datasets and comprehensive comparison with top and latest schemes are provided. The experiments results demonstrates that our scheme is highly efficient and can be effectively applied to large-scale graphs which comprising over 3 million nodes and 1 billion edges.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Efficient shortest distance approximate query on large scale encrypted graph data

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月30日

查看全文
  • Xiaotong Dong,
  • Bo Li,
  • Xiaojie Zhu,
  • Yong Li,
  • Weiping Wang

摘要

The problem of querying shortest distance on a graph has attracted significant research attention due to the widespread applicability of graphs and the ability of graph shortest path queries to address numerous application problems. Given the limited capabilities of clients and the ongoing advancements in cloud computing, people would like to outsource their graph data. Outsourcing data, however, poses the problem of privacy breaches. We should enable clients to encrypt their data before outsource it to cloud servers while retaining the capability of querying the data. The major challenge lies in designing a scheme computing the shortest distance on encrypted graph is how to strike a balance between security, efficiency and accuracy. Moreover, this challenge becomes even more pronounced as the scale of the graph increases. In this article, we propose an efficient scheme called Encrypted Shortest Distance Approximate Query (ESDAQ). We design a new algorithm k-level BFS and make use of cryptographic primitive AES to fulfill the scheme where k is an optional parameter selected by user. The total time cost can be O(N) at best to finish setup and query, which is superior to SOTA solutions of O(NlogN). Theoretical security analysis shows that ESDAQ can reach CQA2-security . Theoretical analysis on security, performance and accuracy are provided of our proposed scheme. Meanwhile, experiments on 12 representative real-world datasets and comprehensive comparison with top and latest schemes are provided. The experiments results demonstrates that our scheme is highly efficient and can be effectively applied to large-scale graphs which comprising over 3 million nodes and 1 billion edges.