A Crypto-Assisted Approach for Publishing Graph Statistics with Node Local Differential Privacy
A Crypto-Assisted Approach for Publishing Graph Statistics with Node Local Differential Privacy
复制标题
DOI：
10.1109/bigdata55660.2022.10020435
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Shang Liu;Yang Cao;Takao Murakami;Masatoshi Yoshikawa
中科院分区：
文献类型：
--
作者：
Shang Liu;Yang Cao;Takao Murakami;Masatoshi Yoshikawa
节点差分隐私下的图统计信息发布由于比边差分隐私提供了更强的隐私保证而受到广泛关注。与节点差分隐私相关的现有工作假设拥有整个图的可信数据管理者。然而，在许多应用程序中，由于隐私和安全问题，受信任的管理者通常不可用。在本文中，我们第一次研究了节点局部差分隐私（Node-LDP）下的图统计信息发布问题，该问题不依赖于可信服务器。通过研究局部环境下图投影参数的选取和局部图投影的执行，提出了一种基于Node-LDP的度分布发布算法。具体来说，我们提出了一种基于密码基元的密码辅助局部投影方法，实现了比我们的基线pureLDP局部投影方法更高的准确性。此外，我们改进了基线图投影方法，从节点级到边缘级，保留了更多的邻域信息，具有更好的实用性。最后，在真实图上的大量实验表明，密码辅助参数选择比纯LDP参数选择具有更好的实用性，边缘级局部投影比节点级局部投影具有更高的精度，分别提高了57.2%和79.8%。
Publishing graph statistics under node differential privacy has attracted much attention since it provides a stronger privacy guarantee than edge differential privacy. Existing works related to node differential privacy assume a trusted data curator who holds the whole graph. However, in many applications, a trusted curator is usually not available due to privacy and security issues. In this paper, for the first time, we investigate the problem of publishing graph statistics under Node Local Differential privacy (Node-LDP), which does not rely on a trusted server. We propose an algorithm to publish the degree distribution with Node-LDP by exploring how to select the graph projection parameter in the local setting and how to execute the graph projection locally. Specifically, we propose a crypto-assisted local projection method based on cryptographic primitives, achieving the higher accuracy than our baseline pureLDP local projection method. Furthermore, we improve our baseline graph projection method from node-level to edge-level that preserves more neighboring information, owning better utility. Finally, extensive experiments on real-world graphs show that crypto-assisted parameter selection owns better utility than pureLDP parameter selection, and edge-level local projection provides higher accuracy than node-level local projection, improving by up to 57.2% and 79.8%, respectively.