KNN on Encrypted Geospatial Data

Description

This work presents an application where certain algorithms can be run on encrypted,

geospatial data. One algorithm is the k-nearest neighbour (kNN) search, that finds the

k closest points of interest to a given location. The other is a routing algorithm on a graph

to find shortest paths.

The application works with data that represents the public transportation system of Munich.

The kNN algorithm thereby finds close stations to a given location and the routing

algorithm calculates how to travel between two stations efficiently. The kNN algorithm is

implemented with an R-Tree as index structure to speed up computation.

The application consists of a data owner, server and client. The data owner encrypts the

data, which is then stored on the server, and the client then queries the server. The data on

the server and the client’s queries are encrypted to ensure confidentiality.

The following cryptographic schemes are used: The Paillier cryposystem, which supports

homomorphic encryption, the Advanced Encryption Standard (AES), Structured Encryption

(SE), and the hOPE scheme, which provides order preserving encryption and

homomorphic support.

The homomorphic and order preserving properties that some of these schemes provide

are necessary so that the server is able to run its computations on the encrypted data.

The functionality of the application is evaluated by checking a list of requirements for

their fulfillment

 Type of work: Master’s thesis
kNN on Encrypted Geospatial Data
Motivation
The search over encrypted data is an important technique in the area of cloud computing. Fully
homomorphic encryption (FHE) is able to provide full computation over encrypted data, but lacks in
efficiency and is not applicable for very large data sets until now. Somewhat homomorphic encryption
(SHE) on the other hand, provides the ability to do efficient partial computation on encrypted data.
In combination with other cryptographic techniques like Order Preserving Encryption (hOPE) and
Structured Encryption (SE) this allows us, to compute operations on encrypted graph data. In this
master thesis a query operation on encrypted graph data, a so called kNN query, shall be conceived,
developed, tested and evaluated. In a kNN query the k next neighbours to a point are returned on
request. Testing shall be done on real world encrypted geospatial data.
Topic
The goal of this thesis is to develop an encrypted kNN query, based on the Paillier crpytosystem
in combination with hOPE and SE. In order to conceived such an encrypted kNN query, various
steps have to be completed. The query has to be adopted to the requirements of the encrypted
schemes. While adopting the query, an encrypted index structure might be created and tested. After
the creation of the encrypted index and the adoption of the query, a user should be able to query the
encrypted spatial data using kNN. If a point of interes matches the kNN query, it will be returned to
the user. The user should now able to decrypt the result. Finally, the efficiency of the query should
be tested and the security should be evaluated.
Topic Description
adopt a kNN query to the encrypted graph setting
if necessary, implement an encrypted index structure
implement the protocol
evaluate the result regarding efficiency and security
Requirements
Good general programming skills (Rust, Java or Python)
Interest in Cryptography
Ability to work self-directed and systematically
The thesis can be written in English or German.
Contact
Georg Bramm
Telefon: +49 89 322-9986-147
E-Mail: georg.bramm@aisec.fraunhofer.de
Fraunhofer Research Institution for Applied and Integrated Security (AISEC)
Service & Application Security
Lichtenbergstrasse 11, 85748 Garching (near Munich), Germany
https://www.aisec.fraunhofer.de Ausschreibungsdatum: 19. November 2019