Position sharing for location privacy in non-trusted systems

Abstract

Currently, many location-aware applications are available for mobile users of location-based services. Applications such as Google Now, Trace4You or FourSquare are being widely used in various environments where privacy is a critical issue for users. A general solution for preserving location privacy for a user is to degrade the quality of his or her position information. In this work, we propose an approach that uses spatial obfuscation to secure the users’ position information. By revealing the user’s position with a certain degree of obfuscation, the first crucial issue is the tradeoff between privacy and precision. This tradeoff problem is caused by limited trust in the location service providers: higher obfuscation increases privacy but leads to lower quality of service. We overcome this problem by introducing the position sharing approach. Our main idea is that position information is distributed amongst multiple providers in the form of separate data pieces called position shares. Our approach allows for the usage of non-trusted providers and flexibly manages the user’s location privacy level based on probabilistic privacy metrics. In this work, we present the multi-provider based position sharing approach, which includes algorithms for the generation of position shares and share fusion algorithms.

The second challenge that must be addressed is that the user’s environmental context can significantly decrease the level of obfuscation. For example, a plane, a boat and a car create different requirements for the obfuscated region. Therefore, it is very important to consider map-awareness in selecting the obfuscated areas. We assume that a static map is known to an adversary, which may help in deriving the user’s true position. We analyze both how map-awareness affects the generation and fusion of position shares and the difference between the map-aware position sharing approach and its open space based version. Our security analysis shows that the proposed position sharing approach provides good security guarantees for both open space and constrained space based models.

The third challenge is that multiple location servers and/or their providers may have different trustworthiness from the user’s point of view. In this case, the user would prefer not to reveal an equal level (precision) of position information to every server. We propose a placement optimization approach that ensures that risk is balanced among the location servers according to their individual trust levels. Our evaluation shows significant improvement of privacy guarantees after applying the optimized share distribution, in comparison with the equal share distribution.

The fourth related problem is the location update algorithm. A high number of different location servers n (corresponding to n privacy levels) may lead to significant communication overhead. Each update would require n messages from the mobile user to the location servers, especially in cases of high update rate. Therefore, we propose an optimized location update algorithm to decrease the number of messages sent without reducing the number of privacy levels and the user’s privacy.

Ortsbezogene Dienste (engl. location-based services) dienen dazu, die aktuelle geographische Position des Nutzers zu bestimmen und im Rahmen einer Anwendung zu nutzen. Heutzutage sind viele ortsbezogene Anwendungen für Nutzer mobiler Endgeräte verfügbar und weit verbreitet, wie z.B. Google Now, Trace4You oder FourSquare. Diese Anwendungen sind auch in verschiedenen Umgebungen eingesetzt, in denen Positionsprivatheit ein kritisches Thema für Benutzer ist. Eine allgemeine Lösung für die Sicherung der Positionsprivatheit eines Benutzers ist, seine Positionsinformationen von geringerer Genauigkeit zu veröffentlichen. In dieser Arbeit schlagen wir einen Ansatz vor, der räumliche Verschleierung benutzt, um Positionsprivatheit mobiler Nutzer zu sichern.

Nach der Offenlegung der Position des Benutzers mit einem bestimmten Verschleierungsgrad ist der Kompromiss zwischen Datenschutz und Genauigkeit sehr wichtig, da das Vertrauen in die Dienstanbieter begrenzt ist. Eine höhere Verschleierung erhöht Positionsprivatheit, führt aber zu geringerer Qualität der Dienstleistung. Wir bieten das “Position Sharing”-Verfahren an, um dieses Problem zu lösen. Die Grundidee ist, dass Positionsinformationen zwischen mehreren Dienstanbietern in Form von separaten Datenstücken (in dieser Arbeit als Positionsshares bezeichnet) verteilt werden. Unser Ansatz ermöglicht die Nutzung von nichtvertrauenswürdigen Dienstanbietern und verwaltet flexibel mehrere Stufen des Datenschutzes für Benutzerpositionen, die auf probabilistischen Privatheitsmetriken basieren. In dieser Arbeit präsentieren wir den “Position Sharing” Ansatz für mehrere Dienstanbieter der ortsbezogenen Dienste, der die Algorithmen zur Erzeugung und Kombination von Positionsshares beinhaltet.

Eine wichtige Herausforderung im Rahmen des Ansatzes ist, dass der Umgebungskontext des Benutzers deutlich das Niveau der Verschleierung verringern kann. D.h., ein Flugzeug, ein Boot oder ein Auto stellt unterschiedliche Anforderungen an die zu verschleiernden Gebiete dar. Deswegen ist es nötig, die Karteninformationen bei der Auswahl der verschleierten Gebiete zu berücksichtigen. Wir gehen davon aus, dass eine statische Karte einem Angreifer bekannt ist, die die echte Benutzerposition enthüllen kann. Wir analysieren, wie sich die Karteninformation auf die Erzeugung und Fusion der Positionsshares auswirkt. Wir zeigen auch den Unterschied zwischen dem kartebewussten “Position Sharing” Ansatz und seiner Version für unstrukturierte Gebiete. Unsere Sicherheitsanalyse zeigt, dass der vorgeschlagene “Position Sharing”-Ansatz gute Sicherheitsgarantien für unstrukturierte sowie strukturierte Raummodelle anbietet.

Die nächste Herausforderung ist, dass mehrere Positionsserver bzw. Serveranbieter unterschiedliche Vertrauenswürdigkeitswerte aus der Sicht des Benutzers haben können. In diesem Fall möchte der Benutzer unterschiedliche Genauigkeitsgrade der Positionsinformationen an jedem einzelnen Positionsserver offenlegen. Wir schlagen einen Ansatz für Platzierungsoptimierung vor, der sicherstellt, dass das Risiko der Positionsserver nach den individuellen Vertrauensniveaus ausgeglichen wird. Unsere Evaluierung zeigt eine signifikante Verbesserung der Positionsprivatheit nach der Anwendung der optimierten Shareverteilung, im Vergleich zu der Gleichverteilung der Shares.

Das letzte betrachtete Problem ist das Lokationsupdateverfahren. Laut unserem Basisansatz kann dies zu einem erheblichen Kommunikationsaufwand führen, wenn die Anzahl der unterschiedlichen Positionsserver (und der entsprechenden Privatheitsniveaus) n hoch ist: Jedes Update würde n Nachrichten von jedem mobilen Nutzer an die Positionsserver erfordern, vor allem im Fall einer hohen Aktualisierungsrate. Wir bieten daher ein optimiertes Lokationsupdateverfahren an, um die Anzahl der Nachrichten so zu verringern, dass die Positionsprivatheit der mobilen Nutzer unverändert bleibt.