{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T20:09:09Z","timestamp":1778789349633,"version":"3.51.4"},"reference-count":63,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,10,14]],"date-time":"2021-10-14T00:00:00Z","timestamp":1634169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Regional Development Fund via Estonian Research Council","award":["TK148"],"award-info":[{"award-number":["TK148"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>In this paper, we propose and present secure multiparty computation (SMC) protocols for single-source shortest distance (SSSD) and all-pairs shortest distance (APSD) in sparse and dense graphs. Our protocols follow the structure of classical algorithms\u2014Bellman\u2013Ford and Dijkstra for SSSD; Johnson, Floyd\u2013Warshall, and transitive closure for APSD. As the computational platforms offered by SMC protocol sets have performance profiles that differ from typical processors, we had to perform extensive changes to the structure (including their control flow and memory accesses) and the details of these algorithms in order to obtain good performance. We implemented our protocols on top of the secret sharing based protocol set offered by the Sharemind SMC platform, using single-instruction-multiple-data (SIMD) operations as much as possible to reduce the round complexity. We benchmarked our protocols under several different parameters for network performance and compared our performance figures against each other and with ones reported previously.<\/jats:p>","DOI":"10.3390\/cryptography5040027","type":"journal-article","created":{"date-parts":[[2021,10,14]],"date-time":"2021-10-14T23:02:16Z","timestamp":1634252536000},"page":"27","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Parallel Privacy-Preserving Shortest Path Algorithms"],"prefix":"10.3390","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7037-6562","authenticated-orcid":false,"given":"Mohammad","family":"Anagreh","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Tartu, Narva Mnt. 18, 51009 Tartu, Estonia"},{"name":"Cybernetica AS, M\u00e4ealuse 2\/1, 12618 Tallinn, Estonia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9030-8142","authenticated-orcid":false,"given":"Peeter","family":"Laud","sequence":"additional","affiliation":[{"name":"Cybernetica AS, M\u00e4ealuse 2\/1, 12618 Tallinn, Estonia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1902-9383","authenticated-orcid":false,"given":"Eero","family":"Vainikko","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Tartu, Narva Mnt. 18, 51009 Tartu, Estonia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Brickell, J., and Shmatikov, V. (2005). Privacy-preserving graph algorithms in the semi-honest model. International Conference on the Theory and Application of Cryptology and Information Security, Springer.","DOI":"10.1007\/11593447_13"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Yao, A.C. (1982, January 3\u20135). Protocols for Secure Computations (Extended Abstract). Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, Chicago, IL, USA.","DOI":"10.1109\/SFCS.1982.38"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., and Damg\u00e5rd, I. (1988). Multiparty Unconditionally Secure Protocols (Extended Abstract). Symposium on Theory of Computing (STOC), ACM.","DOI":"10.1145\/62212.62214"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., and Wigderson, A. (1987). How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. Symposium on Theory of Computing (STOC), ACM.","DOI":"10.1145\/28395.28420"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","article-title":"Relations among complexity measures","volume":"26","author":"Pippenger","year":"1979","journal-title":"J. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/359168.359176","article-title":"How to Share a Secret","volume":"22","author":"Shamir","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_7","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Aly, A., Cuvelier, E., Mawet, S., Pereira, O., and Van Vyve, M. (2013). Securely Solving Simple Combinatorial Graph Problems. Financial Cryptography, Springer.","DOI":"10.1007\/978-3-642-39884-1_21"},{"key":"ref_9","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","year":"2017","journal-title":"Cryptol. EPrint Arch. Rep."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1145\/233551.233553","article-title":"Software Protection and Simulation on Oblivious RAMs","volume":"43","author":"Goldreich","year":"1996","journal-title":"J. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Keller, M., and Scholl, P. (2014). Efficient, oblivious data structures for MPC. International Conference on the Theory and Application of Cryptology and Information Security, Springer.","DOI":"10.1007\/978-3-662-45608-8_27"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Liu, C., Huang, Y., Shi, E., Katz, J., and Hicks, M. (2014, January 18\u201321). Automating Efficient RAM-Model Secure Computation. In Proceedings of 2014 IEEE Symposium on Security and Privacy, Berkeley, CA, USA.","DOI":"10.1109\/SP.2014.46"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a routing problem","volume":"16","author":"Bellman","year":"1985","journal-title":"Q. Appl. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1515\/popets-2015-0011","article-title":"Parallel oblivious array access for secure multiparty computation and privacy-preserving minimum spanning trees","volume":"2015","author":"Laud","year":"2015","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/s10207-012-0177-2","article-title":"High-performance secure multi-party computation for data mining applications","volume":"11","author":"Bogdanov","year":"2012","journal-title":"Int. J. Inf. Secur."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Bogdanov, D., Laur, S., and Willemson, J. (2008). Sharemind: A framework for fast privacy-preserving computations. European Symposium on Research in Computer Security (ESORICS), Springer.","DOI":"10.1007\/978-3-540-88313-5_13"},{"key":"ref_18","unstructured":"Boneh, D. (2003, January 17\u201321). Universally Composable Efficient Multiparty Computation from Threshold Homomorphic Encryption. Proceedings of the Advances in Cryptology\u2014CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, CA, USA. Proceedings (Lecture Notes in Computer Science, Vol. 2729)."},{"key":"ref_19","unstructured":"Yehuda Afek, B.A.C. (July, January 28). Simplified VSS and Fast-Track Multiparty Computations with Applications to Threshold Cryptography. Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC \u201998, Puerto Vallarta, Mexico."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Agrawal, R., and Srikant, R. (2000, January 15\u201318). Privacy-preserving data mining. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, TX, USA.","DOI":"10.1145\/342009.335438"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s00145-001-0019-2","article-title":"Privacy Preserving Data Mining","volume":"15","author":"Lindell","year":"2000","journal-title":"J. Cryptol."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"10562","DOI":"10.1109\/ACCESS.2017.2706947","article-title":"Privacy-preserving data mining: Methods, metrics, and applications","volume":"5","author":"Mendes","year":"2017","journal-title":"IEEE Access"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ostrak, A., Randmets, J., Sokk, V., Laur, S., and Kamm, L. (2021). Implementing Privacy-Preserving Genotype Analysis with Consideration for Population Stratification. Cryptography, 5.","DOI":"10.3390\/cryptography5030021"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Freedman, M.J., Nissim, K., and Pinkas, B. (2004). Efficient private matching and set intersection. International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"ref_25","unstructured":"Saldamli, G., Ertaul, L., Dholakia, K., and Sanikommu, U. (August, January 29). An Efficient Private Matching and Set Intersection Protocol: Implementation PM-Malicious Server. Proceedings of the International Conference on Security and Management (SAM), The Steering Committee of the World Congress in Computer Science, Las Vegas, NV, USA."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Naor, M., Pinkas, P., and Sumner, R. (1999, January 3\u20135). Privacy preserving auctions and mechanism design. Proceedings of the 1st ACM Conference on Electronic Commerce, Denver, CO, USA.","DOI":"10.1145\/336992.337028"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Kissner, L., and Song, D. (2005). Privacy-preserving set operations. Annual International Cryptology Conference, Springer.","DOI":"10.21236\/ADA457144"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Anagreh, M., Vainikko, E., and Laud, P. (2021, January 11\u201313). Parallel Privacy-preserving Computation of Minimum Spanning Trees. Proceedings of the 7th International Conference on Information Systems Security and Privacy\u2014ICISSP, online. ISSN 2184-4356.","DOI":"10.5220\/0010255701810190"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Laud, P., and Kamm, L. (2015). Basic Constructions of Secure Multiparty Computation. Applications of Secure Multiparty Computation, IOS Press.","DOI":"10.1515\/popets-2015-0011"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Laud, P., and Kamm, L. (2015). Stateful abstractions of secure multiparty computation. Applications of Secure Multiparty Computation, IOS Press.","DOI":"10.1515\/popets-2015-0011"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s001459910006","article-title":"Security and composition of multiparty cryptographic protocols","volume":"13","author":"Canetti","year":"2000","journal-title":"J. Cryptol."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Laur, S., and Pullonen-Raudvere, P. (2021). Foundations of Programmable Secure Computation. Cryptography, 5.","DOI":"10.3390\/cryptography5030022"},{"key":"ref_33","unstructured":"Russo, A., and Tripp, O. (2014, January 29). Domain-Polymorphic Programming of Privacy-Preserving Applications. Proceedings of the Ninth Workshop on Programming Languages and Analysis for Security, PLAS@ECOOP2014, Uppsala, Sweden."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Reihaneh Safavi-Naini, R., and Canetti, R. (2012, January 19\u201323). Multi-party Computation from Somewhat Homomorphic Encryption. Proceedings of the Advances in Cryptology\u2014CRYPTO 2012\u201432nd Annual Cryptology Conference, Santa Barbara, CA, USA. Proceedings (Lecture Notes in Computer Science, Vol. 7417).","DOI":"10.1007\/978-3-642-32009-5"},{"key":"ref_35","unstructured":"Lai, X., Zhou, J., and Li, H. (2011, January 26\u201329). Round-Efficient Oblivious Database Manipulation. Proceedings of the Information Security, 14th International Conference, ISC 2011, Xi\u2019an, China. Proceedings (Lecture Notes in Computer Science, Vol. 7001)."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Laud, P. (2021). Linear-time oblivious permutations for SPDZ, submitted.","DOI":"10.1007\/978-3-030-92548-2_13"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Bernsmed, K., and Fischer-H\u00fcbner, S. (2014, January 15\u201317). A Practical Analysis of Oblivious Sorting Algorithms for Secure Multi-party Computation. Proceedings of the Secure IT Systems-19th Nordic Conference, NordSec 2014, Troms\u00f8, Norway. Proceedings (Lecture Notes in Computer Science, Vol. 8788).","DOI":"10.1007\/978-3-319-11599-3"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Anagreh, M., Vainikko, E., and Laud, P. (2021, January 10\u201312). Parallel Privacy-Preserving Shortest Paths by Radius-Stepping. Proceedings of the 2021 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), Valladolid, Spain.","DOI":"10.1109\/PDP52278.2021.00051"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Gu, Y., Sun, Y., and Tangwongsan, K. (2016, January 11\u201313). Parallel shortest paths using radius stepping. Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, Pacific Grove, CA, USA.","DOI":"10.1145\/2935764.2935765"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/S0196-6774(03)00076-2","article-title":"\u0394-stepping: A parallelizable shortest path algorithm","volume":"49","author":"Meyer","year":"2003","journal-title":"J. Algorithms"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Wu, D.J., Zimmerman, J., Planul, J., and Mitchell, J.C. (2016, January 21\u201324). Privacy-Preserving Shortest Path Computation. Proceedings of the 23rd Annual Network and Distributed System Security Symposium, NDSS 2016, San Diego, CA, USA.","DOI":"10.14722\/ndss.2016.23052"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Ramezanian, S., Meskanen, T., and Niemi, V. (2018, January 15\u201318). Privacy Preserving Shortest Path Queries on Directed Graph. Proceedings of the 2018 22nd Conference of Open Innovations Association (FRUCT), Jyvaskyla, Finland.","DOI":"10.23919\/FRUCT.2018.8468303"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"2759","DOI":"10.1587\/transinf.E95.D.2759","article-title":"Blocked united algorithm for the all-pairs shortest paths problem on hybrid CPU-GPU systems","volume":"95","author":"Matsumoto","year":"2012","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_44","first-page":"61","article-title":"Concurrent selection of the shortest paths and distances in directed graphs using vertical processing systems","volume":"19","author":"Nepomniaschaya","year":"2003","journal-title":"Bull. Novosib. Comput. Cent."},{"key":"ref_45","unstructured":"Han, S.C., and Kang, S.C. (2021, October 12). Optimizing All Pairs Shortest Path Algorithm Using Vector Instructions. Project Report, Carnegie-Mellon University. Available online: https:\/\/users.ece.cmu.edu\/~pueschel\/teaching\/18-799B-CMU-spring05\/material\/sungchul-sukchan.pdf."},{"key":"ref_46","unstructured":"Takei, Y., Hariyama, M., and Kameyama, M. (2015, January 27\u201330). Evaluation of an FPGA-based shortest-path-search accelerator. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), Las Vegas, USA."},{"key":"ref_47","unstructured":"Nagavalli, S. (2021, October 12). Dynamic Optimization\u2014Using Hardware Parallelism for Faster Search via Dynamic Programming. Project Report, Carnegie-Mellon University. Available online: https:\/\/www.andrew.cmu.edu\/user\/snagaval\/16-745\/Project\/16-745-Project-Report-SasankaNagavalli.pdf."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.1997.0888","article-title":"A randomized parallel algorithm for single-source shortest paths","volume":"25","author":"Klein","year":"1997","journal-title":"J. Algorithms"},{"key":"ref_49","unstructured":"Meyer, U. (2002). Design and Analysis of Sequential and Parallel Single-Source Shortest-Paths Algorithms. [Ph.D. Dissertation, University of Saarland]."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Tr\u00e4ff, J.L., and Zaroliagis, C.D. (1996, January 19\u201321). A simple parallel algorithm for the single-source shortest path problem on planar digraphs. Proceedings of the International Workshop on Parallel Algorithms for Irregularly Structured Problems, Santa Barbara, CA, USA.","DOI":"10.1007\/BFb0030108"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q., and Oswald, E. (2014, January 11\u201315). Garbled RAM Revisited. Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2014\u201433rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark. Proceedings (Lecture Notes in Computer Science, Vol. 8441).","DOI":"10.1007\/978-3-642-55220-5"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","article-title":"Parallel prefix computation","volume":"27","author":"Ladner","year":"1980","journal-title":"J. ACM"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.1145\/7902.7903","article-title":"Data parallel algorithms","volume":"29","author":"Hillis","year":"1986","journal-title":"Commun. ACM"},{"key":"ref_54","unstructured":"Atluri, V., and Winslett, M. (2008, January 27). Privacy-preserving social network analysis for criminal investigations. Proceedings of the 2008 ACM Workshop on Privacy in the Electronic Society, WPES 2008, Alexandria, VA, USA."},{"key":"ref_55","unstructured":"Geisler, M. (2010). Cryptographic Protocols: Theory and Implementation. [Ph.D. Dissertation, Aarhus University]."},{"key":"ref_56","unstructured":"Simon, J. (1988, January 2\u20134). Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA."},{"key":"ref_57","unstructured":"Toft, T. (2007). Primitives and Applications for Multi-Party Computation. [Ph.D. Dissertation, University of Aarhus]."},{"key":"ref_58","unstructured":"King, S.T. (2013, January 14\u201316). Secure Outsourced Garbled Circuit Evaluation for Mobile Devices. Proceedings of the 22th USENIX Security Symposium, Washington, DC, USA."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Liu, C., Wang, X.S., Nayak, N., Huang, Y., and Shi, E. (2015, January 17\u201321). ObliVM: A Programming Framework for Secure Computation. Proceedings of the 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA.","DOI":"10.1109\/SP.2015.29"},{"key":"ref_60","unstructured":"Ahn, G.J., Yung, M., and Li, N. (2014, January 3\u20137). Oblivious Data Structures. Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA."},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Bellare, M., Hoang, V.T., Keelveedhi, S., and Rogaway, P. (2013, January 19\u201322). Efficient Garbling from a Fixed-Key Block cipher. Proceedings of the 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA.","DOI":"10.1109\/SP.2013.39"},{"key":"ref_62","unstructured":"Chen, K., Xie, Q., Qiu, W., Li, N., and Tzeng, W.G. (2013, January 8\u201310). Data-oblivious graph algorithms for secure computation and outsourcing. Proceedings of the 8th ACM Symposium on Information, Computer and Communications Security, ASIA CCS \u201913, Hangzhou, China."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1145\/78607.78614","article-title":"Measuring Parallel Processor Performance","volume":"33","author":"Karp","year":"1990","journal-title":"Commun. ACM"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/5\/4\/27\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:14:49Z","timestamp":1760166889000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/5\/4\/27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,14]]},"references-count":63,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["cryptography5040027"],"URL":"https:\/\/doi.org\/10.3390\/cryptography5040027","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,14]]}}}