nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Privacy Preserving Queries of Shortest Path Distances

verfasst von : Ernst Althaus, Stefan Funke, Moritz Schrauth

Erschienen in: Algorithmic Aspects of Cloud Computing

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel 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_4CrossRef

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

Titel: Privacy Preserving Queries of Shortest Path Distances
verfasst von: Ernst Althaus
Stefan Funke
Moritz Schrauth
Verlag: Springer International Publishing
Buch: Algorithmic Aspects of Cloud Computing
Print ISBN: 978-3-031-33436-8

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner