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

doi:10.19678/j.issn.1000-3428.0066861

摘要/Abstract

摘要：

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

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

Abstract:

The widely used massive graph data, such as the ones used for social networks, communication networks, and bioproteins, contain large amount of private and sensitive personal and commercial information; therefore, it is essential to encrypt such graph data and outsource query services in cloud computing. However, it is challenging to design efficient outsourcing schemes for computation that can accurately determine the shortest-distance queries on encrypted graph data to ensure high security of private information and to improve the efficiency of computations such as encrypted queries.In this study, an outsourcing computing scheme for exact shortest-distance queries is proposed for graph data based on the 2-hop cover labeling and additive homomorphic encryption.First, a breadth-first search pruning strategy is proposed for preprocessing the original set of labels generated by the 2-hop cover labeling, wherein the number of labels is reduced, and the query efficiency is improved. Subsequently, the set of labels is encrypted, and a secure index structure is constructed based on the additive homomorphic encryption and pseudo-random function.Thus, the information related to the nodes and distances of the graph data is protected while computing the accurate shortest distance query on the encrypted graph data. Analysis and experiments show that the proposed scheme can accurately compute the outsourcing shortest distance of the encrypted graph data with a semi-honest assumption that satisfies INDCPA under the random oracle model and(L₁, L₂)security. The proposed scheme can protect the private information retrieved during outsourcing computation on graph data, thereby reducing the overhead by approximately 13.04%-24.24% and 36.44%-46.13% in the graph data encryption and shortest distance querying phases, respectively, when comparing with the existing similar schemes.

Key words: outsourced computation of graph data, shortest distance querying, 2-hop cover labeling, additive homomorphic encryption, privacy preserving

于莹莹, 丁红发, 蒋合领. 图数据精确最短距离的隐私保护外包计算方案[J]. 计算机工程, 2023, 49(9): 158-171.

Yingying YU, Hongfa DING, Heling JIANG. Privacy-Preserving Outsourced Computation Scheme for Accurate Shortest Distance of Graph Data[J]. Computer Engineering, 2023, 49(9): 158-171.

https://www.ecice06.com/CN/Y2023/V49/I9/158

图/表 12

图1 二跳覆盖标记方案示例

Fig.1 Example of 2-hop cover labeling scheme

图2 密文图数据上最短距离外包计算模型

Fig.2 Outsourced computation model of the shortest distance over encrypted graph data

图3 广度优先搜索修剪策略示例

Fig.3 Example of breadth first searching pruning strategy

图4 密文距离值安全比较电路

Fig.4 Secure comparison circuit for encrypted distance values

图5 标记数量及标记生成时间开销对比

Fig.5 Comparison of the number of labels and the time overhead of label generation

图6 图数据加密时间开销对比

Fig.6 Time overhead comparison of encrypted graph data

图7 生成查询令牌的时间开销对比

Fig.7 Time overhead comparison of generating query token

图8 最短距离查询的时间开销对比

Fig.8 Time overhead comparison of the shortest distance querying

图9 密文结果解密的时间开销对比

Fig.9 Time overhead comparison of decrypting ciphertext results

参考文献 31

1	QIAN J W , LI X Y , ZHANG C H , et al. Social network de-anonymization and privacy inference with knowledge graph model. IEEE Transactions on Dependable and Secure Computing, 2019, 16 (4): 679- 692. doi: 10.1109/TDSC.2017.2697854
2	JI S L , MITTAL P , BEYAH R . Graph data anonymization, de-anonymization attacks, and de-anonymizability quantification: a survey. IEEE Communications Surveys & Tutorials, 2017, 19 (2): 1305- 1326.
3	ZHANG L , XIONG H , HUANG Q , et al. Cryptographic solutions for cloud storage: challenges and research opportunities. IEEE Transactions on Services Computing, 2022, 15 (1): 567- 587. doi: 10.1109/TSC.2019.2937764
4	刘向宇, 李佳佳, 安云哲, 等. 一种保持结点可达性的高效社会网络图匿名算法. 软件学报, 2016, 27 (8): 1904- 1921. URL
	LIU X Y , LI J J , AN Y Z , et al. Efficient algorithm on anonymizing social networks with reachability preservation. Journal of Software, 2016, 27 (8): 1904- 1921. URL
5	WEI C K , JI S L , LIU C C , et al. AsgLDP: collecting and generating decentralized attributed graphs with local differential privacy. IEEE Transactions on Information Forensics and Security, 2020, 15, 3239- 3254. doi: 10.1109/TIFS.2020.2985524
6	WANG S L , ZHENG Y F , JIA X H , et al. PeGraph: a system for privacy-preserving and efficient search over encrypted social graphs. IEEE Transactions on Information Forensics and Security, 2022, 17, 3179- 3194. doi: 10.1109/TIFS.2022.3201392
7	SUNTAXI G , GHAZI A A , BÖHM K . Secrecy and performance models for query processing on outsourced graph data. Distributed and Parallel Databases, 2021, 39 (1): 35- 77. doi: 10.1007/s10619-020-07284-0
8	BLANTON M, STEELE A, ALISAGARI M. Data-oblivious graph algorithms for secure computation and outsourcing[C]//Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. New York, USA: ACM Press, 2013: 207-218.
9	KELLER M, SCHOLL P. Efficient, oblivious data structures for MPC[C]//Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security. Berlin, Germany: Springer, 2014: 506-525.
10	LI J W , LIN D , SQUICCIARINI A C , et al. Towards privacy-preserving storage and retrieval in multiple clouds. IEEE Transactions on Cloud Computing, 2017, 5 (3): 499- 509. doi: 10.1109/TCC.2015.2485214
11	GUPTA M K , CHANDRA P . Effects of similarity/distance metrics on k-means algorithm with respect to its applications in IoT and multimedia: a review. Multimedia Tools and Applications, 2022, 81 (26): 37007- 37032. doi: 10.1007/s11042-021-11255-7
12	ZHU A D, MA H, XIAO X K, et al. Shortest path and distance queries on road networks: towards bridging theory and practice[C]//Proceedings of 2013 International Conference on Management of Data. New York, USA: ACM Press, 2013: 857-868.
13	OUYANG D, QIN L, CHANG L J, et al. When hierarchy meets 2-hop-labeling: efficient shortest distance queries on road networks[C]//Proceedings of 2018 International Conference on Management of Data. New York, USA: ACM Press, 2018: 709-724.
14	CHASE M, KAMARA S. Structured encryption and controlled disclosure[M]//ABE M. Advances in cryptology-ASIACRYPT. Berlin, Germany: Springer, 2010: 577-594.
15	CAO N, YANG Z Y, WANG C, et al. Privacy-preserving query over encrypted graph-structured data in cloud computing[C]//Proceedings of the 31st International Conference on Distributed Computing Systems. Washington D.C., USA: IEEE Press, 2011: 393-402.
16	YIN P P, FAN Z, YIN S X. Privacy-preserving reachability query services for sparse graphs[C]//Proceedings of the 30th International Conference on Data Engineering Workshops. Washington D.C., USA: IEEE Press, 2014: 32-35.
17	MENG X R, KAMARA S, NISSIM K, et al. GRECS: graph encryption for approximate shortest distance queries[C]//Proceedings of the 22nd SIGSAC Conference on Computer and Communications Security. New York, USA: ACM Press, 2015: 504-517.
18	ZHU H, WU B, XIE M Y, et al. Secure shortest path search over encrypted graph supporting synonym query in cloud computing[EB/OL]. [2023-01-05]. https://ieeexplore.ieee.org/xpl/conhome/7845250/proceeding.
19	沈蒙, 赵梦蕉, 祝烈煌, 等. 支持近似最短距离查询的高效图加密机制. 南京信息工程大学学报, 2017, 9 (5): 527- 532. URL
	SHEN M , ZHAO M J , ZHU L H , et al. Efficient graph encryption mechanism for approximate shortest distance search based on cloud. Journal of Nanjing University of Information Science & Technology, 2017, 9 (5): 527- 532. URL
20	LIU C , ZHU L H , HE X J , et al. Enabling privacy-preserving shortest distance queries on encrypted graph data. IEEE Transactions on Dependable and Secure Computing, 2021, 18 (1): 192- 204. doi: 10.1109/TDSC.2018.2880981
21	SHEN M , MA B L , ZHU L H , et al. Cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection. IEEE Transactions on Information Forensics and Security, 2018, 13 (4): 940- 953. doi: 10.1109/TIFS.2017.2774451
22	WANG Q, REN K, DU M X, et al. SecGDB: graph encryption for exact shortest distance queries with efficient updates[M]//KIAYIAS A. Financial cryptography and data security. Berlin, Germany: Springer, 2017: 79-97.
23	GHOSH E, KAMARA S, TAMASSIA R. Efficient graph encryption scheme for shortest path queries[C]//Proceedings of 2021 ACM Asia Conference on Computer and Communications Security. New York, USA: ACM Press, 2021: 516-525.
24	DU M X , WU S K , WANG Q , et al. GraphShield: dynamic large graphs for secure queries with forward privacy. IEEE Transactions on Knowledge and Data Engineering, 2022, 34 (7): 3295- 3308.
25	ZHANG C , ZHU L H , XU C , et al. PGAS: privacy-preserving graph encryption for accurate constrained shortest distance queries. Information Sciences, 2020, 506, 325- 345. doi: 10.1016/j.ins.2019.07.082
26	STORANDT S. Route planning for bicycles—exact constrained shortest paths made practical via contraction hierarchy[EB/OL]. [2023-01-05]. https://ojs.aaai.org/index.php/ICAPS/article/view/13495.
27	WANG S B , XIAO X K , YANG Y , et al. Effective indexing for approximate constrained shortest path queries on large road networks. Proceedings of the VLDB Endowment, 2016, 10 (2): 61- 72. doi: 10.14778/3015274.3015277
28	XU Z F , ZHOU F C , LI J , et al. Graph encryption for all-path queries. Concurrency and Computation: Practice and Experience, 2020, 32 (16): 23- 34.
29	WANG Y, WANG Q, KOEHLER H, et al. Query-by-sketch: scaling shortest path graph queries on very large networks[C]//Proceedings of 2021 International Conference on Management of Data Virtual Event. New York, USA: ACM Press, 2021: 1946-1958.
30	AKIBA T, IWATA Y, YOSHIDA Y. Fast exact shortest-path distance queries on large networks by pruned landmark labeling[C]//Proceedings of 2013 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2013: 349-360.
31	VLADIMIR K, THOMAS S. Improved garbled circuit: free XOR gates and applications[C]//Proceedings of the 35th International Colloquium, Automata, Languages and Programming. Berlin, Germany: Springer, 2018: 486-498.

[1]	郑清安, 董建成, 陈亮, 阮英清, 李锦松, 许林彬. 分布式可信数据管理与隐私保护技术研究[J]. 计算机工程, 2024, 50(7): 174-186.
[2]	熊世强, 何道敬, 王振东, 杜润萌. 联邦学习及其安全与隐私保护研究综述[J]. 计算机工程, 2024, 50(5): 1-15.
[3]	王栋, 王合建, 玄佳兴, 郑尚卓, 陈炳聪. 面向电力调度指令的区块链隐私可追踪存证方案[J]. 计算机工程, 2024, 50(5): 158-166.
[4]	卢晓天, 朴春慧, 杨兴雨, 白英杰. 基于贝叶斯网络的差分隐私高维数据发布技术研究[J]. 计算机工程, 2024, 50(5): 167-181.
[5]	张晓均, 李兴鹏, 唐伟, 郝云溥, 薛婧婷. 云-边融合的可验证隐私保护跨域联邦学习方案[J]. 计算机工程, 2024, 50(3): 148-155.
[6]	叶晓东, 赵迎迎, 孙永奇, 赵思聪, 刘真. 基于非定长编码和滑动窗口的隐私保护记录链接方法[J]. 计算机工程, 2024, 50(2): 154-164.
[7]	邱天晨, 郑小盈, 祝永新, 封松林. 面向非独立同分布数据的联邦学习架构[J]. 计算机工程, 2023, 49(7): 110-117.
[8]	陈福安, 柳毅. 基于区块链的V2G无证书环签密隐私保护方案[J]. 计算机工程, 2023, 49(6): 34-41,52.
[9]	王群, 李馥娟, 倪雪莉, 夏玲玲, 梁广俊. 区块链隐私保护机制研究[J]. 计算机工程, 2023, 49(4): 1-13.
[10]	杨越佳, 华蓓, 钟志威, 高咪. 基于同态加密的隐私保护逻辑回归协同计算[J]. 计算机工程, 2023, 49(4): 23-31.
[11]	唐敏, 张宇浩, 邓国强. 一种高效的非交互式隐私保护逻辑回归模型[J]. 计算机工程, 2023, 49(4): 32-42,51.
[12]	张晓均, 刘庆, 郑爽, 王鑫, 薛婧婷, 王世雄. 支持隐私保护的可验证云端数据分享方案[J]. 计算机工程, 2023, 49(3): 49-57.
[13]	王静怡, 刘百祥, 方宁, 彭凌祺. 基于区块链与属性密码体制的匿名数据共享访问控制[J]. 计算机工程, 2023, 49(10): 41-52.
[14]	李尤慧子, 俞海涛, 殷昱煜, 高洪皓. 基于超级账本的集群联邦优化模型[J]. 计算机工程, 2023, 49(1): 22-30.
[15]	周全兴, 李秋贤, 丁红发, 樊玫玫. 基于博弈论优化的高效联邦学习方案[J]. 计算机工程, 2022, 48(8): 144-151,159.

选择文件类型/文献管理软件名称

选择包含的内容