{"ID":2894696,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.10627","arxiv_id":"2507.10627","title":"Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy","abstract":"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.","short_abstract":"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 proce...","url_abs":"https://arxiv.org/abs/2507.10627","url_pdf":"https://arxiv.org/pdf/2507.10627v1","authors":"[\"Xiaojian Zhang\",\"Junqing Wang\",\"Kerui Chen\",\"Peiyuan Zhao\",\"Huiyuan Bai\"]","published":"2025-07-14T07:04:08Z","proceeding":"cs.CR","tasks":"[\"cs.CR\",\"cs.DB\"]","methods":"[]","has_code":false}