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 θ to bound node degrees. However, this approach presents a fundamental trade-off in threshold parameter selection. While large θ values introduce substantial noise in the released degree sequence, small θ values result in more edges removed than necessary. Furthermore, θ 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- θ -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 ϵ-node local differential privacy. The experimental results on eight graph datasets show that our solution outperforms existing methods.