{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:47:15Z","timestamp":1775594835141,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>\n                    Shortest distance computation is a fundamental problem in graph data analysis, with critical applications in financial fraud detection, website ranking, and social network analysis. In real-world settings, however, graph data is often distributed across multiple mutually untrusted organizations, making accurate shortest path computation under strict privacy constraints a major challenge. Existing solutions face two key limitations: (1) traditional distributed algorithms lack privacy protection; and (2) secure multi-party computation (MPC)-based methods, though privacy-preserving, suffer from high computational overhead and poor scalability, restricting them to graphs with only tens of thousands of nodes. To address these challenges, we propose PrivHop, a novel algorithm that integrates 2-hop labeling with MPC in a two-phase framework. In the offline phase, PrivHop constructs an optimized boundary graph index to reduce global queries to small-scale boundary graph queries. In the online phase, it introduces a privacy-aware dynamic pruning strategy based on differential privacy to substantially reduce iteration complexity with privacy guarantees. Extensive experiments on eight real-world datasets show that PrivHop preserves privacy while scaling to million-node graphs, achieving up to 10\n                    <jats:sup>6<\/jats:sup>\n                    x reductions in both runtime and communication compared to state-of-the-art methods.\n                  <\/jats:p>","DOI":"10.1145\/3786695","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-2133-5271","authenticated-orcid":false,"given":"Huizhong","family":"Wang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3764-6476","authenticated-orcid":false,"given":"Yuanyuan","family":"Zeng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2370-5372","authenticated-orcid":false,"given":"Kun","family":"Chen","sequence":"additional","affiliation":[{"name":"Ant Group, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0394-4125","authenticated-orcid":false,"given":"Wei","family":"Dong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-8512","authenticated-orcid":false,"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling. CoRR","author":"Akiba Takuya","year":"2013","unstructured":"Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013a. Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling. CoRR, Vol. abs\/1304.4661 (2013). arXiv:1304.4661 http:\/\/arxiv.org\/abs\/1304.4661"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_3_1","first-page":"971","article-title":"An Improved Protocol for Securely Solving the Shortest Path Problem and its Application to Combinatorial Auctions","volume":"2017","author":"Aly Abdelrahaman","year":"2017","unstructured":"Abdelrahaman Aly and Sara Cleemput. 2017. An Improved Protocol for Securely Solving the Shortest Path Problem and its Application to Combinatorial Auctions. IACR Cryptol. ePrint Arch., Vol. 2017 (2017), 971. https:\/\/api.semanticscholar.org\/CorpusID:3990412","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39884-1_21"},{"key":"e_1_2_1_5_1","volume-title":"Securely Solving Classical Network Flow Problems. LIDAM Reprints CORE 3192. Universit\u00e9 catholique de Louvain","author":"Aly Abdelrahaman","unstructured":"Abdelrahaman Aly and Mathieu Van Vyve. 2022. Securely Solving Classical Network Flow Problems. LIDAM Reprints CORE 3192. Universit\u00e9 catholique de Louvain, Center for Operations Research and Econometrics (CORE). https:\/\/ideas.repec.org\/p\/cor\/louvrp\/3192.html"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.3390\/cryptography5040027"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484560"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484560"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560695"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46766-1_34"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Michael Ben-Or Shafi Goldwasser and Avi Wigderson. 1988. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). 1-10. doi:10.1145\/62212.62213","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484313.2484341"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi Marco Rosa Massimo Santini and Sebastiano Vigna. 2011. Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks. arXiv:1011.5425 [cs.DS] https:\/\/arxiv.org\/abs\/1011.5425","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11593447_13"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_2_1_17_1","volume-title":"TFHE: Fast Fully Homomorphic Encryption over the Torus. Cryptology ePrint Archive, Paper 2018\/421. https:\/\/eprint.iacr.org\/2018\/421","author":"Chillotti Ilaria","year":"2018","unstructured":"Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabach\u00e8ne. 2018. TFHE: Fast Fully Homomorphic Encryption over the Torus. Cryptology ePrint Archive, Paper 2018\/421. https:\/\/eprint.iacr.org\/2018\/421"},{"key":"e_1_2_1_18_1","volume-title":"Smart, and Younes Talibi Alaoui","author":"Cozzo Daniele","year":"2021","unstructured":"Daniele Cozzo, Nigel P. Smart, and Younes Talibi Alaoui. 2021. Secure Fast Evaluation of Iterative Methods: With an Application to Secure PageRank. Cryptology ePrint Archive, Paper 2021\/207. https:\/\/eprint.iacr.org\/2021\/207"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_38"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/322358.322360"},{"key":"e_1_2_1_21_1","volume-title":"ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In 22nd Annual Network and Distributed System Security Symposium, NDSS 2015","author":"Demmler Daniel","year":"2015","unstructured":"Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, California, USA, February 8-11, 2015. The Internet Society. https:\/\/www.ndss-symposium.org\/ndss2015\/aby--framework-efficient-mixed-protocol-secure-two-party-computation"},{"key":"e_1_2_1_22_1","volume-title":"Differential Privacy","author":"Dwork Cynthia","unstructured":"Cynthia Dwork. 2006. Differential Privacy. In Automata, Languages and Programming, Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1-12."},{"key":"e_1_2_1_23_1","first-page":"17844","volume-title":"Oh (Eds.)","volume":"35","author":"Fan Chenglin","year":"2022","unstructured":"Chenglin Fan, Ping Li, and Xiaoyun Li. 2022. Private Graph All-Pairwise-Shortest-Path Distance Release with Improved Error Rate. In Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35. Curran Associates, Inc., 17844-17856. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/71b17f00017da0d73823ccf7fbce2d4f-Paper-Conference.pdf"},{"key":"e_1_2_1_24_1","unstructured":"Ada Wai-Chee Fu Huanhuan Wu James Cheng Shumo Chu and Raymond Chi-Wing Wong. 2012. IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying on Large Graphs. arXiv:1211.2367 [cs.DB] https:\/\/arxiv.org\/abs\/1211.2367"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28420"},{"key":"e_1_2_1_27_1","unstructured":"Bernhard Haeupler Richard Hlad\u00edk V\u00e1clav Rozhon Robert E. Tarjan and Jakub Tetek. 2025. Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps. arXiv:2311.11793 [cs.DS] https:\/\/arxiv.org\/abs\/2311.11793"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983731"},{"key":"e_1_2_1_29_1","unstructured":"Jacob Imola Takao Murakami and Kamalika Chaudhuri. 2024. Communication-Efficient Triangle Counting under Local Differential Privacy. arXiv:2110.06485 [cs.CR] https:\/\/arxiv.org\/abs\/2110.06485"},{"key":"e_1_2_1_30_1","first-page":"137","article-title":"Efficient, Oblivious Data Structures for MPC","volume":"2014","author":"Keller Marcel","year":"2014","unstructured":"Marcel Keller and Peter Scholl. 2014. Efficient, Oblivious Data Structures for MPC. IACR Cryptol. ePrint Arch., Vol. 2014 (2014), 137. https:\/\/api.semanticscholar.org\/CorpusID:17251251","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_2_1_31_1","volume-title":"Jaspal Singh Saini, and S. R. S. Iyengar","author":"Kukkala Varsha Bhat","year":"2016","unstructured":"Varsha Bhat Kukkala, Jaspal Singh Saini, and S. R. S. Iyengar. 2016. Privacy Preserving Network Analysis of Distributed Social Networks. Cryptology ePrint Archive, Paper 2016\/427. https:\/\/eprint.iacr.org\/2016\/427"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.46"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_22"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_33"},{"key":"e_1_2_1_36_1","unstructured":"Benjamin Ostrovsky. 2024. Privacy-Preserving Dijkstra. Cryptology ePrint Archive Paper 2024\/988. https:\/\/eprint.iacr.org\/2024\/988"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_38_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report 1999-66. Stanford InfoLab. http:\/\/ilpubs.stanford.edu:8090\/422\/ Previous number = SIDL-WP-1999-0120."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756123.1756146"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322138"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73014"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417274"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_16"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02837777"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.38"},{"key":"e_1_2_1_47_1","first-page":"160","article-title":"b. Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfcs 1982)","author":"Yao Andrew C","year":"1982","unstructured":"Andrew C Yao. 1982 b. Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfcs 1982). IEEE, 160-164.","journal-title":"IEEE"},{"key":"e_1_2_1_48_1","first-page":"160","article-title":"c. Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfcs 1982)","author":"Yao Andrew C","year":"1982","unstructured":"Andrew C Yao. 1982 c. Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfcs 1982). IEEE, 160-164.","journal-title":"IEEE"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3734839.3734840"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675053"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00019"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00132"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T19:55:13Z","timestamp":1775591713000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786695"],"URL":"https:\/\/doi.org\/10.1145\/3786695","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}