Cryptpath

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.