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

作者：丁红发; 于莹莹; 蒋合领

来源：计算机科学, 2023, 1-21.

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

地理位置、社交网络等海量图数据应用广泛且包含大量隐私，通常需要通过安全的外包计算提供多样化的查询服务。然而，如何设计正确性可验证的图数据外包计算协议仍是公开难题。为此，提出加密图数据上正确性可验证的精确最短路径外包计算方案。该方案利用加法同态加密构造密态图数据上的广度优先最短路径计算算法，支持加密图数据的精确最短距离查询外包计算；其次，基于双线性映射累加器构造最短路径外包计算结果的概率正确性验证机制。分析和证明表明，该方案能以概率可靠性实现正确性可验证的精确最短路径的外包计算，具备随机预言模型下的IND-CCA2安全。对比和实验表明，所提方案相比其他相关方案在安全性、功能性方面有显著优势，性能上较已有可验证图数据外包计算方案在初始化及加密环节、查询环节、验证及解密环节分别降低了0.15%～23.19%、12.91%～30.89%和1.13%～18.62%的时间开销。

• 单位
  贵州财经大学; 贵州大学