作者：gufe_hfding

论文概要

今天分享的是北理工朱烈煌老师团队2020年最新的图数据隐私保护论文，该论文发表在Information Sciences上，题目是“PGAS: Privacy-preserving graph encryption for accurate constrained shortest distance queries”，这篇论文利用Paillier同态加密算法设计了一个精确的约束最短路径查询隐私保护算法，以实现具有隐私保护的图外包计算。近年来，朱老师团队在图数据安全计算方面发表了多篇论文，多以密码学的方法，利用安全多方计算、同态加密等进行协议设计，实现图计算过程中的安全与隐私保护，朱老师团队主要在最短路径计算方面做了不同层面的工作。

Can Zhang, Liehuang Zhu, Chang Xu, Kashif Sharif, Chuan Zhang, Ximeng Liu:
PGAS: Privacy-preserving graph encryption for accurate constrained shortest distance queries. Inf. Sci. 506: 325-345 (2020)
Meng Shen, Siqi Chen, Liehuang Zhu, Renyi Xiao, Ke Xu, Xiaojiang Du:
Privacy-Preserving Graph Encryption for Approximate Constrained Shortest Distance Queries. GLOBECOM 2019: 1-6
Meng Shen, Baoli Ma, Liehuang Zhu, Rashid Mijumbi, Xiaojiang Du, Jiankun Hu:
Cloud-Based Approximate Constrained Shortest Distance Queries Over Encrypted Graphs With Privacy Protection. IEEE Trans. Inf. Forensics Secur. 13(4): 940-953 (2018)
Chang Liu, Liehuang Zhu, Jinjun Chen:
Graph Encryption for Top-K Nearest Keyword Search Queries on Cloud. IEEE Trans. Sustain. Comput. 2(4): 371-381 (2017)

论文主要创新

这篇论文的主要创新点是针对有向图设计额外的最短路径计算标签，在此基础上利用同态加密算法实现无信息损失的加密和搜索，得到的约束最短路径查询结果与原始图上的查询结果一致。

启发与个人想法

基于密码的隐私保护方法大多是用在图的计算安全上，特别是在图外包计算中，能够较好保护图数据的结构隐私和节点隐私，缺点就是效率较低。今天和于桂海老师沟通，是否可以设计基于模糊的加噪方法，设计能够保护某类隐私的外包计算方法，提高效率，适当降低精度，只要精度不是降得特别厉害就好。比如说差分隐私用在外包计算中合适不？还是说加噪方式可以不一样，会更好？不去达到所有场景的隐私保护，只需要保护某种隐私就可以，比如结构隐私，身份隐私，或者其他特征。