Abstract—Although location-based applications have seen fast growth in the last decade due to pervasive adoption of GPS enabled mobile devices, their use raises privacy concerns. To mitigate these concerns, a number of approaches have been proposed in literature, many of which rely on a trusted party to regulate user privacy. However, trusted parties are known to be prone to data breaches [1]. Consequently, a novel solution, called Position Sharing, was proposed in [2] to secure location privacy in fully non-trusted systems. In Position Sharing, obfuscated position shares of the actual user location are distributed among several location servers, each from a different provider, such that there is no single point of failure if the servers get breached. While Position Sharing can exhibit useful properties such as graceful degradation of privacy, it incurs significant communication overhead as position shares are sent to several location servers instead of one.

To this end, we propose a set of location update protocols to minimize the communication overhead of Position Sharing while maintaining the privacy guarantees that it originally provided. As we consider the scenario of frequent location updates, i.e., movement trajectories, our protocols additionally add protection against an attack based on spatio-temporal correlation in published locations. By evaluating on a set of real-world GPS traces, we show that our protocols can reduce the communication overhead by 75% while significantly improving the security guarantees of the original Position Sharing algorithm.