Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy

Given a graph G defined in a domain \(\mathcal {G}\) , we investigate locally differentially private mechanisms to release a degree sequence on \(\mathcal {G}\) that accurately approximates the actual degree distribution. Existing solutions for this problem mostly use graph projection techniques based on edge deletion process, using a threshold parameter \(\theta\) to bound node degrees. However, this approach presents a fundamental trade-off in threshold parameter selection. While large \(\theta\) values introduce substantial noise in the released degree sequence, small \(\theta\) values result in more edges removed than necessary. Furthermore, \(\theta\) selection leads to an excessive communication cost. To remedy existing solutions’ deficiencies, we present CADR-LDP, an efficient framework incorporating encryption techniques and differentially private mechanisms to release the degree sequence. In CADR-LDP, we first use the crypto-assisted Optimal- \(\theta\) -Selection method to select the optimal parameter with a low communication cost. Then, we use the LPEA-LOW method to add some edges for each node with the edge addition process in local projection. LPEA-LOW prioritizes the projection with low-degree nodes, which can retain more edges for such nodes and reduce the projection error. Theoretical analysis shows that CADR-LDP satisfies \(\epsilon\) -node local differential privacy. The experimental results on eight graph datasets show that our solution outperforms existing methods.