{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T18:55:13Z","timestamp":1771959313593,"version":"3.50.1"},"reference-count":46,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2024,12,26]],"date-time":"2024-12-26T00:00:00Z","timestamp":1735171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Regional Development Fund through the Estonian Centre of Excellence in ICT Research\u2014EXCITE","award":["PRG1780"],"award-info":[{"award-number":["PRG1780"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Secure secret-sharing Single-Source Shortest Distance (SSSD) protocols, based on secure multiparty computation (SMC), offer a promising solution for securely distributing and managing sensitive information among multiple parties. However, formal security proofs for these protocols have largely been unexplored. This paper addresses this gap by providing the first security proof for the SSSD protocols using the privacy-preserving Bellman\u2013Ford protocols. These new protocols offer significant enhancements in efficiency, particularly in handling large-scale graphs due to parallel computation. In our previous work, published in MDPI Cryptography, we introduced these protocols and presented extensive experiments on the Sharemind system that demonstrated their efficiency. However, that work did not include security proofs. Building on this foundation, the current paper rigorously proves the security of these protocols, offering valuable insights into their robustness and reliability. Furthermore, we discuss the adversarial model, security definitions, cryptographic assumptions, and sophisticated reduction techniques employed in the proof. This paper not only validates the security of the proposed protocols but also provides a detailed comparison of their performance with existing methods, highlighting their strengths and potential for future research in the field.<\/jats:p>","DOI":"10.3390\/cryptography9010001","type":"journal-article","created":{"date-parts":[[2024,12,26]],"date-time":"2024-12-26T19:33:07Z","timestamp":1735241587000},"page":"1","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Security Proof of Single-Source Shortest Distance Protocols Built on Secure Multiparty Computation Protocols"],"prefix":"10.3390","volume":"9","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"}]},{"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"}]}],"member":"1968","published-online":{"date-parts":[[2024,12,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Bogdanov, D., Laur, S., and Willemson, J. (2008, January 6\u20138). Sharemind: A framework for fast privacy-preserving computations. Proceedings of the Computer Security-ESORICS 2008: 13th European Symposium on Research in Computer Security, M\u00e1laga, Spain. Proceedings 13.","DOI":"10.1007\/978-3-540-88313-5_13"},{"key":"ref_2","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_3","doi-asserted-by":"crossref","unstructured":"Bogdanov, D., Jagom\u00e4gis, R., and Laur, S. (2012). A universal toolkit for cryptographically secure privacy-preserving data mining. Pacific-Asia Workshop on Intelligence and Security Informatics, Springer.","DOI":"10.1007\/978-3-642-30428-6_9"},{"key":"ref_4","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_5","doi-asserted-by":"crossref","first-page":"886","DOI":"10.1093\/bioinformatics\/btt066","article-title":"A new way to protect privacy in large-scale genome-wide association studies","volume":"29","author":"Kamm","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_6","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 International Conference on Information Systems Security and Privacy, ICISSP, Virtual Event.","DOI":"10.5220\/0010255701810190"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1007\/s42979-022-01331-6","article-title":"Privacy-Preserving Parallel Computation of Minimum Spanning Forest","volume":"3","author":"Anagreh","year":"2022","journal-title":"SN Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Pankova, A., and J\u00e4\u00e4ger, J. (2020, January 13). Short Paper: Secure multiparty logic programming. Proceedings of the 15th Workshop on Programming Languages and Analysis for Security, Virtual Event.","DOI":"10.1145\/3411506.3417597"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"J\u00e4\u00e4ger, J., and Pankova, A. (2021, January 7\u20139). PrivaLog: A privacy-aware logic programming language. Proceedings of the 23rd International Symposium on Principles and Practice of Declarative Programming, Virtual Event.","DOI":"10.1145\/3479394.3479410"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1515\/popets-2016-0019","article-title":"Students and taxes: A privacy-preserving social study using secure computation","volume":"2016","author":"Bogdanov","year":"2015","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Bogdanov, D., Kamm, L., Laur, S., Pruulmann-Vengerfeldt, P., Talviste, R., and Willemson, J. (2014, January 20\u201321). Privacy-preserving statistical data analysis on federated databases. Proceedings of the Privacy Technologies and Policy: Second Annual Privacy Forum, APF 2014, Athens, Greece. Proceedings 2.","DOI":"10.1007\/978-3-319-06749-0_3"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Anagreh, M., Laud, P., and Vainikko, E. (2021). Parallel privacy-preserving shortest path algorithms. Cryptography, 5.","DOI":"10.3390\/cryptography5040027"},{"key":"ref_13","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_14","doi-asserted-by":"crossref","unstructured":"Anagreh, M., Laud, P., and Vainikko, E. (2022, January 9\u201311). Privacy-preserving Parallel Computation of Shortest Path Algorithms with Low Round Complexity. Proceedings of the International Conference on Information Systems Security and Privacy, ICISSP, Virtual Event.","DOI":"10.5220\/0010775700003120"},{"key":"ref_15","unstructured":"Anagreh, M., and Laud, P. (2022, January 29\u201330). A Parallel Privacy-Preserving Shortest Path Protocol from a Path Algebra Problem. Proceedings of the 17th International Workshop on Data Privacy Management (DPM 2022), DPM 2022\/CBT, Copenhagen, Denmark. LNCS 13619."},{"key":"ref_16","unstructured":"Bogdanov, D., Laud, P., and Randmets, J. (August, January 28). Domain-polymorphic programming of privacy-preserving applications. Proceedings of the Ninth Workshop on Programming Languages and Analysis for Security, Uppsala, Sweden."},{"key":"ref_17","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_18","first-page":"26","article-title":"Stateful abstractions of secure multiparty computation","volume":"13","author":"Laud","year":"2015","journal-title":"Appl. Secur. Multiparty Comput."},{"key":"ref_19","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_20","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_21","doi-asserted-by":"crossref","unstructured":"Cramer, R., and Damg\u00e5rd, I.B. (2015). Secure Multiparty Computation, Cambridge University Press.","DOI":"10.1017\/CBO9781107337756"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Yao, A.C. (1982, January 3\u20135). Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), Chicago, IL, USA.","DOI":"10.1109\/SFCS.1982.38"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., and Damgard, I. (1988, January 2\u20134). Multiparty unconditionally secure protocols. Proceedings of the twentieth annual ACM symposium on Theory of computing, Chicago, IL, USA.","DOI":"10.1145\/62212.62214"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., and Wigderson, A. (2019). How to play any mental game, or a completeness theorem for protocols with honest majority. Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, Association for Computing Machinery.","DOI":"10.1145\/3335741.3335759"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., and Nielsen, J.B. (2003, January 17\u201321). Universally composable efficient multiparty computation from threshold homomorphic encryption. Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-540-45146-4_15"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Henecka, W., K \u00f6gl, S., Sadeghi, A.R., Schneider, T., and Wehrenberg, I. (2010, January 4\u20138). TASTY: Tool for automating secure two-party computations. Proceedings of the 17th ACM conference on Computer and Communications Security, Chicago IL, USA.","DOI":"10.1145\/1866307.1866358"},{"key":"ref_27","unstructured":"Gennaro, R., Rabin, M.O., and Rabin, T. (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, Puerto Vallarta, Mexico."},{"key":"ref_28","unstructured":"Burkhart, M., Strasser, M., Many, D., and Dimitropoulos, X. (2010, January 11\u201313). SEPIA:Privacy-Preserving Aggregation of Multi-Domain Network Events and Statistics. Proceedings of the 19th USENIX Security Symposium (USENIX Security 10), Washington, DC, USA."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Geisler, M., Kr\u00f8igaard, M., and Nielsen, J.B. (2009, January 18\u201320). Asynchronous multiparty computation: Theory and implementation. Proceedings of the International Workshop on Public Key Cryptography, Irvine, CA, USA.","DOI":"10.1007\/978-3-642-00468-1_10"},{"key":"ref_30","unstructured":"Pankova, A. (2017). Efficient Multiparty Computation Secure Against Covert and Active Adversaries. [Ph.D. Thesis, University of Tartu]."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Canetti, R. (2001, January 8\u201311). Universally composable security: A new paradigm for cryptographic protocols. Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, Newport Beach, CA, USA.","DOI":"10.1109\/SFCS.2001.959888"},{"key":"ref_32","unstructured":"West, D.B. (2001). Introduction to Graph Theory, Prentice Hall."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (1998). Modern Graph Theory, Springer Science & Business Media.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"ref_34","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2022). Introduction to Algorithms, MIT Press."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Dijkstra, E.W. (2022). A note on two problems in connexion with graphs. Edsger Wybe Dijkstra: His Life, Work, and Legacy, Association for Computing Machinery.","DOI":"10.1145\/3544585.3544600"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1090\/qam\/64563","article-title":"Heat transfer by free convection across a closed cavity between vertical boundaries at different temperatures","volume":"12","author":"Batchelor","year":"1954","journal-title":"Q. Appl. Math."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Thorup, M. (2003, January 9\u201311). Integer priority queues with decrease key in constant time and the single source shortest paths problem. Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA.","DOI":"10.1145\/780564.780566"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/S0196-6774(03)00076-2","article-title":"\u03b4-stepping: A parallelizable shortest path algorithm","volume":"49","author":"Meyer","year":"2003","journal-title":"J. Algorithms"},{"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","unstructured":"Fink, E. (2024, September 25). A Survey of Sequential and Systolic Algorithms for the Algebraic Path Problem. Available online: https:\/\/kilthub.cmu.edu\/articles\/journal_contribution\/A_survey_of_sequential_and_systolic_algorithms_for_the_algebraic_path_problem\/6602726?file=12092768."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Bogdanov, D., Laur, S., and Talviste, R. (2014). A practical analysis of oblivious sorting algorithms for secure multi-party computation. Nordic Conference on Secure IT Systems, Springer International Publishing.","DOI":"10.1007\/978-3-319-11599-3_4"},{"key":"ref_42","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 (JACM)"},{"key":"ref_43","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_44","unstructured":"Anagreh, M. (2023). Privacy-Preserving Parallel Computations for Graph Problems. [Ph.D. Thesis, University of Tartu]."},{"key":"ref_45","unstructured":"Riivo, T. (2016). Applying Secure Multi-Party Computation in Practice. [Ph.D. Thesis, University of Tartu]."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"137","DOI":"10.3233\/JCS-150540","article-title":"Secure outsourced garbled circuit evaluation for mobile devices","volume":"24","author":"Carter","year":"2016","journal-title":"J. Comput. Secur."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/1\/1\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T17:00:49Z","timestamp":1760115649000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/1\/1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,26]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["cryptography9010001"],"URL":"https:\/\/doi.org\/10.3390\/cryptography9010001","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,26]]}}}