Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908449414053888 |
|---|---|
| author | Zhang, Xiaojian Wang, Junqing Chen, Kerui Zhao, Peiyuan Bai, Huiyuan |
| author_facet | Zhang, Xiaojian Wang, Junqing Chen, Kerui Zhao, Peiyuan Bai, Huiyuan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10627 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy Zhang, Xiaojian Wang, Junqing Chen, Kerui Zhao, Peiyuan Bai, Huiyuan Cryptography and Security Databases 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. |
| title | Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy |
| topic | Cryptography and Security Databases |
| url | https://arxiv.org/abs/2507.10627 |