TUM Logo

KNN on Encrypted Geospatial Data

KNN on Encrypted Geospatial Data

Supervisor(s): Georg Bramm
Status: inprogress
Topic: Others
Author: Julia Dahmen
Submission: 2020-06-15
Type of Thesis: Masterthesis
Thesis topic in co-operation with the Fraunhofer Institute for Applied and Integrated Security AISEC, Garching

Description

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