TUM Logo

Range Query over Encrypted Geospatial Data

Range Query over Encrypted Geospatial Data

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


Smart phones enable us to navigate our surroundings anytime, by utilizing online mappingservices. To optimize navigation, users have to share their current location. Information about locations and user queries are gathered for commercial purposes by the service providers.The gathering of this data represents an invasion of privacy. Renouncing web mapping services is, at present, the only effective option to protect user privacy. This work presents an alternative approach. Geodata is encrypted and stored on a remote server. User queries are encrypted as well and their real contents stay hidden from the server. The focus of this work is on developing a concept for a range query over encrypted geodata. The concept utilizes different cryptosystems to transform geospatial data into a format, that can be privately queried. For this purpose we combine structured, partially homomorphic and order preserving encryption. A prototype is further implemented, in order to evaluate the feasibility of the concept. The result shows, that the concept enables a range query over encrypted geodata, while minimizing the information a server can gain through analysis of the data or the queries.


Type of work: Master’s thesis
Range Query over Encrypted Geospatial Data
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 range query, shall be conceived,
developed, tested and evaluated. Testing shall be done on real world encrypted geospatial
The goal of this thesis is to develop an encrypted range query, based on the Paillier crpytosystem in
combination with hOPE and SE. In order to conceived such an encrypted range query protocol, 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 a specific range. If a range query matches an entry in the SE data, 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 Range query to the encrypted graph setting
if necessary implement an encrypted index structure
implement the protocol
evaluate the result regarding efficiency and security
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.
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