正确性可验证的密文图数据最短路径外包计算方案  

Correctness Verifiable Outsourcing Computation Scheme of Shortest Path Querying over Encrypted Graph Data

作　　者：丁红发[1,2] 于莹莹 蒋合领[1] DING Hongfa;YU Yingying;JIANG Heling(College of Information,Guizhou Key Laboratory of Big Data Statistical Analysis,Guizhou University of Finance and Economics,Guiyang 550025,China;State Key Laboratory of Pubic Big Data,Guizhou University,Guiyang 550025,China)

机构地区：[1]贵州财经大学信息学院贵州省大数据统计分析重点实验室,贵阳550025 [2]贵州大学公共大数据国家重点实验室,贵阳550025

出　　处：《计算机科学》2024年第5期400-413,共14页Computer Science

基　　金：国家自然科学基金(62002080);贵州省教育厅自然科学研究项目(黔教技[2023]065号,黔教技[2023]014号)。

摘　　要：地理位置、社交网络等海量图数据应用广泛且包含大量隐私,通常需要安全的外包计算来提供多样化的查询服务。然而,如何设计正确性可验证的图数据外包计算协议仍是公开的难题。为此,提出了加密图数据上正确性可验证的精确最短路径外包计算方案。该方案利用加法同态加密构造密态图数据上的广度优先最短路径计算算法,支持加密图数据的精确最短距离查询外包计算;其次,基于双线性映射累加器构造最短路径外包计算结果的概率正确性验证机制。分析和证明表明,该方案能以概率可靠性实现正确性可验证的精确最短路径的外包计算,具备随机预言模型下的IND-CCA2安全。对比实验结果表明,所提方案相比其他相关方案在安全性、功能性方面有显著优势,性能上较已有可验证图数据外包计算方案在初始化及加密环节、查询环节、验证及解密环节的时间开销分别降低了0.15%~23.19%,12.91%~30.89%和1.13%~18.62%。Mass graph data such as geolocation and social networks are widely used and contain massive privacy,usually,it requires varied query services through secure outsourcing computation schemes.However,it is still an open challenge to design correctness verifiable outsourcing computation protocols for graph data.To this end,a correctness-verifiable outsourcing computation scheme of accurate shortest path over encrypted graph data is proposed.In this scheme,a breadth-first shortest path algorithm for encrypted graph data is constructed by using additive homomorphic encryption to support the outsourcing computation of exact shortest distance queries over encrypted graph data.Secondly,a probabilistic correctness verification mechanism of shortest path outsourcing computation result is constructed by using the bilinear mapping accumulator.Analysis and proof show that this scheme implements the correctness-verifiable accurate shortest path outsourcing computation with probabilistic reliability,it has the security of IND-CCA2 under the random oracle model.Comparisons and experiments indicate that the proposed scheme has significant advantages compared with other related schemes in terms of security and functionality,compared with existing verifiable graph data outsourcing computation schemes,the overheads in the initialization and encryption phase,the query phase,and the verification and decryption phase reduces by 0.15%~23.19%,12.91%~30.89%and 1.13%~18.62%,respectively.

关 键 词：图数据外包计算 可验证 最短路径查询 密码累加器 同态加密 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]