Building and Evaluating Geospatial Cryptographic Schemes

Real-world maps contain geospatial data, which can be represented as 2-dimensional

graph structures. In real-world applications, security plays an important role. 

However, the security of geospatial data does not get much research interest. Symmetric

Searchable Encryption was first introduced by Song et al. [18]. It allows querying in an

encrypted database to search documents containing certain keywords. In 2010, Chase

and Kamara [4] introduced a structured encryption scheme, which can be used to

encrypt structured data, including graphs. After that, many graph encryption schemes

were developed. They can encrypt graphs in a way so that the encrypted data can still

be queried. This thesis gives an overview of some state-of-the-art graph encryption

schemes. We built two graph encryption schemes that support querying the exact

shortest path problem.

We tested their time and memory consumption using graph datasets and real-world

maps. Their leakage profiles are also informally analyzed. We hope that our evaluation

can help researchers to understand their real-world potentials.