计算机工程

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

单位：1. 贵州财经大学 信息学院, 贵阳 5500252. 贵州省大数据统计分析重点实验室, 贵阳 5500253. 贵安新区科创产业发展有限公司, 贵阳 550025

关键词：图数据外包计算,最短距离查询,二跳覆盖标记,加法同态加密,隐私保护

基金：国家自然科学基金(62002080); 中国博士后基金(2020M673584XB); 贵州省教育厅青年科技人才成长项目(黔教合KY字[2021]140)

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

来源：2023年第9期

《计算机工程》期刊编辑部

查看计算机工程杂志2023年第9期