{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T12:05:10Z","timestamp":1776168310192,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62072156"],"award-info":[{"award-number":["62072156"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Outstanding Youth Science Foundation Project of Henan Province","award":["252300421061"],"award-info":[{"award-number":["252300421061"]}]},{"name":"Basic Research Special Projects of Key Research Projects in Higher Education Institutes in Henan Province","award":["25ZX012"],"award-info":[{"award-number":["25ZX012"]}]},{"name":"Humanities and Social Sciences Research Projects of the Ministry of Education"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2026,5,31]]},"abstract":"<jats:p>\n                    Given a graph\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    defined in a domain\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {G}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , we investigate locally differentially private mechanisms to release a degree sequence on\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {G}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    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\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\theta\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    to bound node degrees. However, this approach presents a fundamental trade-off in threshold parameter selection. While large\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\theta\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    values introduce substantial noise in the released degree sequence, small\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\theta\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    values result in more edges removed than necessary. Furthermore,\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\theta\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    selection leads to an excessive communication cost. To remedy existing solutions\u2019 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-\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\theta\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -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\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\epsilon\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -node local differential privacy. The experimental results on eight graph datasets show that our solution outperforms existing methods.\n                  <\/jats:p>","DOI":"10.1145\/3799795","type":"journal-article","created":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T20:57:20Z","timestamp":1773349040000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Crypto-Assisted Graph Degree Sequence Release under Local Differential Privacy"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5504-7347","authenticated-orcid":false,"given":"Xiaojian","family":"Zhang","sequence":"first","affiliation":[{"name":"Computer Science, Henan University of Economics and Law","place":["Zhengzhou, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6246-6278","authenticated-orcid":false,"given":"Junqing","family":"Wang","sequence":"additional","affiliation":[{"name":"Computer Science, Guangzhou University","place":["Guangzhou, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3331-9978","authenticated-orcid":false,"given":"Kerui","family":"Chen","sequence":"additional","affiliation":[{"name":"Computer Science, Henan University of Economics and Law","place":["Zhengzhou, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7952-0492","authenticated-orcid":false,"given":"Peiyuan","family":"Zhao","sequence":"additional","affiliation":[{"name":"Computer Science, Henan University of Economics and Law","place":["Zhengzhou, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5417-8188","authenticated-orcid":false,"given":"Huiyuan","family":"Bai","sequence":"additional","affiliation":[{"name":"Computer Science, Henan University of Economics and Law","place":["Zhengzhou, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,14]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3133982"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3133982"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560610"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3549993.3550007"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_3_1_9_2","first-page":"1529","volume-title":"Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States","author":"Duchi John C.","year":"2013","unstructured":"John C. Duchi, Martin J. Wainwright, and Michael I. Jordan. 2013. Local privacy and minimax bounds: Sharp rates for probability estimation. In Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, Christopher J. C. Burges, L\u00e9on Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger (Eds.). 1529\u20131537. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2013\/hash\/5807a685d1a9ab3b599035bc566ce2b9-Abstract.html"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536466"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.52"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00186"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2025.49"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","unstructured":"Lihe Hou Weiwei Ni Sen Zhang Nan Fu and Dongyue Zhang. 2023. Wdt-SCAN: Clustering decentralized social graphs with local differential privacy. Comput. Secur. 125 (2023) 103036. DOI:10.1016\/J.COSE.2022.103036","DOI":"10.1016\/J.COSE.2022.103036"},{"key":"e_1_3_1_17_2","first-page":"983","volume-title":"30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021","author":"Imola Jacob","year":"2021","unstructured":"Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2021. Locally differentially private analysis of graph statistics. In 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021, Michael D. Bailey and Rachel Greenstadt (Eds.). USENIX Association, 983\u20131000. Retrieved from https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/imola"},{"key":"e_1_3_1_18_2","first-page":"537","volume-title":"31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022","author":"Imola Jacob","year":"2022","unstructured":"Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2022. Communication-efficient triangle counting under local differential privacy. In 31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022, Kevin R. B. Butler and Kurt Thomas (Eds.). USENIX Association, 537\u2013554. Retrieved from https:\/\/www.usenix.org\/conference\/usenixsecurity22\/presentation\/imola"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560659"},{"key":"e_1_3_1_20_2","doi-asserted-by":"crossref","unstructured":"Vishesh Karwa Sofya Raskhodnikova Adam D. Smith and Grigory Yaroslavtsev. 2011. Private analysis of graph structure. Proc. VLDB Endow. 4 11 (2011) 1146\u20131157. Retrieved from http:\/\/www.vldb.org\/pvldb\/vol4\/p1146-karwa.pdf","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00136"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/BIGDATA55660.2022.10020435"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","unstructured":"Yuhan Liu Tianhao Wang Yixuan Liu Hong Chen and Cuiping Li. 2024. Edge-protected triangle count estimation under relationship local differential privacy. IEEE Trans. Knowl. Data Eng. 36 10 (2024) 5138\u20135152. DOI:10.1109\/TKDE.2024.3381832","DOI":"10.1109\/TKDE.2024.3381832"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134086"},{"key":"e_1_3_1_27_2","doi-asserted-by":"crossref","unstructured":"Stanley L. Warner. 1965. Randomized response: A survey technique for eliminating evasive answer bias. J. Amer. Statist. Assoc. 60 309 (1965) 63\u201369.","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","unstructured":"Chengkun Wei Shouling Ji Changchang Liu Wenzhi Chen and Ting Wang. 2020. AsgLDP: Collecting and generating decentralized attributed graphs with local differential privacy. IEEE Trans. Inf. Forensics Secur. 15 (2020) 3239\u20133254. DOI:10.1109\/TIFS.2020.2985524","DOI":"10.1109\/TIFS.2020.2985524"},{"key":"e_1_3_1_29_2","unstructured":"Liangliang Xiao I-Ling Yen and Dung T. Huynh. 2012. Extending order preserving encryption for multi-user systems. IACR Cryptol. ePrint Arch. (2012) 192. Retrieved from http:\/\/eprint.iacr.org\/2012\/192"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","unstructured":"Qingqing Ye Haibo Hu Man Ho Au Xiaofeng Meng and Xiaokui Xiao. 2022. LF-GDPR: A framework for estimating graph metrics with local differential privacy. IEEE Trans. Knowl. Data Eng. 34 10 (2022) 4905\u20134920. DOI:10.1109\/TKDE.2020.3047124","DOI":"10.1109\/TKDE.2020.3047124"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3799795","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T11:23:44Z","timestamp":1776165824000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3799795"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,14]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,31]]}},"alternative-id":["10.1145\/3799795"],"URL":"https:\/\/doi.org\/10.1145\/3799795","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,14]]},"assertion":[{"value":"2025-06-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-24","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}