Top

Hint

Swipe to navigate through the chapters of this book

Published in:

Read chapter Read first chapter

2023 | OriginalPaper | Chapter

Privacy Preserving Queries of Shortest Path Distances

Authors : Ernst Althaus, Stefan Funke, Moritz Schrauth

Published in: Algorithmic Aspects of Cloud Computing

Publisher: Springer International Publishing

Abstract

Consider a user with a very limited hardware and internet connection who wants to query a shortest path distance from a web service, but doesn’t want to reveal the source and destination to the server. Using state-of-the-art methods, we show that we can privately query shortest path distances in this case, if we are allowed to use three non-cooperating servers of moderate compute and communication power. We argue that this is not possible with classical shortest path algorithms. Finally, we give some experiments showing the feasibility of the approach.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter More Sparking Soundex-Based Privacy-Preserving Record Linkage

Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 24–35. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33090-2_4 CrossRef

Adams, S., et al.: Privacy-preserving training of tree ensembles over continuous data. Proc. Priv. Enhancing Technol. 2022(2), 205–226 (2022). https://doi.org/10.2478/popets-2022-0042

Akavia, A., Leibovich, M., Resheff, Y.S., Ron, R., Shahar, M., Vald, M.: Privacy-preserving decision trees training and prediction. IACR Cryptol. ePrint Arch. 768 (2021). https://eprint.iacr.org/2021/768

Anagreh, M., Laud, P., Vainikko, E.: Privacy-preserving parallel computation of shortest path algorithms with low round complexity. In: Mori, P., Lenzini, G., Furnell, S. (eds.) Proceedings of the 8th International Conference on Information Systems Security and Privacy, ICISSP 2022, Online Streaming, February 9–11, 2022, pp. 37–47. SCITEPRESS (2022). https://doi.org/10.5220/0010775700003120

Bahrdt, D., Funke, S., Makolli, S., Proissl, C.: Distance closures: unifying search- and lookup-based shortest path speedup techniques. In: Phillips, C.A., Speckmann, B. (eds.) Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Alexandria, VA, USA, 9–10 January 2022, pp. 1–12. SIAM (2022). https://doi.org/10.1137/1.9781611977042.1

Chatterjee, A., Aung, K.M.M.: Fully homomorphic encryption in real world applications. Computer Architecture and Design Methodologies, vol. 295. Springer, Cham (2021). https://doi.org/10.1007/978-981-13-6393-1

Cramer, R., Damgård, I., Nielsen, J.B.: Secure Multiparty Computation and Secret Sharing. Cambridge University Press (2015), http://www.cambridge.org/de/academic/subjects/computer-science/cryptography-cryptology-and-coding/secure-multiparty-computation-and-secret-sharing?format=HB&isbn=9781107043053

Demmler, D., Herzberg, A., Schneider, T.: RAID-PIR: practical multi-server PIR. In: Ahn, G., Oprea, A., Safavi-Naini, R. (eds.) Proceedings of the 6th edition of the ACM Workshop on Cloud Computing Security, CCSW 2014, Scottsdale, Arizona, USA, November 7, 2014, pp. 45–56. ACM (2014). https://doi.org/10.1145/2664168.2664181

Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transp. Sci. 46(3), 388–404 (2012). https://doi.org/10.1287/trsc.1110.0401

10.

Goss, K., Jiang, W.: Efficient and constant-rounds secure comparison through dynamic groups and asymmetric computations. IACR Cryptol. ePrint Arch. p. 179 (2018). http://eprint.iacr.org/2018/179

11.

Lee, J., et al.: Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access 10, 30039–30054 (2022). https://doi.org/10.1109/ACCESS.2022.3159694

12.

Ramezanian, S., Meskanen, T., Niemi, V.: Privacy-protecting algorithms for digraph shortest path queries. Int. J. Embed. Real Time Commun. Syst. 10(3), 86–100 (2019). https://doi.org/10.4018/IJERTCS.2019070106

13.

Sealfon, A.: Shortest paths and distances with differential privacy. In: Milo, T., Tan, W. (eds.) Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pp. 29–41. ACM (2016). https://doi.org/10.1145/2902251.2902291

14.

Tan, S., Knott, B., Tian, Y., Wu, D.J.: Cryptgpu: Fast privacy-preserving machine learning on the GPU. In: 42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24–27 May 2021. pp. 1021–1038. IEEE (2021). https://doi.org/10.1109/SP40001.2021.00098

15.

Wu, D.J., Zimmerman, J., Planul, J., Mitchell, J.C.: Privacy-preserving shortest path computation. In: 23rd Annual Network and Distributed System Security Symposium, NDSS 2016, San Diego, California, USA, February 21–24, 2016. The Internet Society (2016). http://wp.internetsociety.org/ndss/wp-content/uploads/sites/25/2017/09/privacy-preserving-shortest-path-computation.pdf

16.

Xi, Y., Schwiebert, L., Shi, W.: Privacy preserving shortest path routing with an application to navigation. Pervasive Mob. Comput. 13, 142–149 (2014). https://doi.org/10.1016/j.pmcj.2013.06.002

Title: Privacy Preserving Queries of Shortest Path Distances
Authors: Ernst Althaus
Stefan Funke
Moritz Schrauth
Publisher: Springer International Publishing
Book: Algorithmic Aspects of Cloud Computing
Print ISBN: 978-3-031-33436-8

Electronic ISBN: 978-3-031-33437-5

Copyright Year: 2023
DOI: https://doi.org/10.1007/978-3-031-33437-5_6

Springer Professional

Hint

Swipe to navigate through the chapters of this book

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"