Print Email Facebook Twitter Cryptpath Title Cryptpath: Data-oblivious Shortest Path Discovery in Outsourced Settings Author Geadău, Andrei (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Erkin, Z. (mentor) Dekker, Florine (mentor) Proksch, S. (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science Date 2023-07-18 Abstract Cloud computing and storage solutions have been credited with increasing competitiveness through cost savings, greater flexibility, elasticity and optimal resource allocation. However, the data outsourced to the cloud may contain private information that must be protected from misuse. In such cases, the data can only be outsourced after encryption. Graphs are widely used to model and represent data in various applications, including geographic information systems. Yet performing the shortest path algorithm over such encrypted outsourced graphs represents a challenge. Current approaches rely on trusted third parties, employ weaker security measures, or treat the cloud as a storage medium rather than addressing the algorithmic complexities directly. This makes the adoption of such protocols difficult in practice.In this work, we develop two privacy-preserving navigation protocols to compute the shortest path over encrypted outsourced graphs, under different security and efficiency guarantees. The first protocol enables one to retrieve the shortest path in an oblivious manner, that is, without the cloud learning any information about the outsourced graph or the returned path. The second protocol assumes that the topology of the outsourced graph is public knowledge, and obtains retrieval times orders of magnitude faster. The evaluation results on a proof-of-concept implementation indicate that the condition number of the node-incidence matrix of the graph being outsourced serves as a determining factor for the number of iterations. Dense graphs exhibit a low condition number. In such cases, the high number of iterations required for convergence, quadratic time complexity with respect to the number of edges in the graph, and the inherently slow homomorphic operations results in impractical retrieval times. Conversely, sparse graphs allow for trivial resolution of shortest paths within a single iteration. Subject privacycloud computingshortest path To reference this document use: http://resolver.tudelft.nl/uuid:1a93b73a-2dae-4d37-9a6d-55ce2c0a9b1e Part of collection Student theses Document type master thesis Rights © 2023 Andrei Geadău Files PDF Master_Thesis_Andrei_Geadau.pdf 1.61 MB Close viewer /islandora/object/uuid:1a93b73a-2dae-4d37-9a6d-55ce2c0a9b1e/datastream/OBJ/view