图数据精确最短距离的隐私保护外包计算方案

社交网络、通信网络、生物蛋白等海量图数据应用广泛且包含大量个人隐私和商业敏感信息,通常需要对图数据加密并通过云计算提供安全高效的外包查询服务。然而,设计加密图数据上的高效精确最短距离外包计算方案既要保证隐私数据的高安全性,又要提高加密查询等计算的效率,具有一定挑战性。提出一种基于二跳覆盖标记和加法同态的图数据精确最短距离查询外包计算方案。使用广度优先搜索修剪策略对二跳覆盖标记生成的原始标记集合进行预处理,减少预处理的标记数量并提高查询效率。基于加法同态加密和伪随机函数对标记集合进行加密处理并构造安全索引结构,保护图数据的节点和距离信息,实现加密图数据的精确最短距离查询。实验结果表明,该方案能正确进行加密图数据上精确最短距离的外包计算,在半诚实假设下满足随机预言模型下的IND-CPA安全和(L_(1),L_(2))安全,能有效保护图结构数据在外包计算中的隐私信息,在图数据加密和最短距离查询阶段相较现有同类方案分别降低了13.04%~24.24%和36.44%~46.13%的时间开销。