Data-driven methodologies offer many exciting upsides, but they also introduce new challenges, particularly in the realm of user privacy. Specifically, the way data is collected can pose privacy risks to end users. In many routing services, a single entity (e.g., the routing service provider) collects and manages user trajectory data. When it comes to user privacy, these systems have a central point of failure since users have to trust that this entity will not sell or use their data to infer sensitive private information. With this as motivation, we study the problem of using location data for routing services in a privacy-preserving way. Rather than having users report their location to a central operator, we present a protocol in which users participate in a decentralized and privacy-preserving computation to estimate travel times for the roads in the network in a way that no individuals' location is ever observed by any other party. The protocol uses the Laplace mechanism in conjunction with secure multi-party computation to ensure that it is cryptogrpahically secure and that its output is differentially private. The protocol is computationally efficient and does not require specialized hardware; all it needs is GPS, which is included in most mobile devices. A natural question is if privacy necessitates degradation in accuracy or system performance. We show that if a road has sufficiently high capacity, then the travel time estimated by our protocol is provably close to the ground truth travel time. We validate the protocol through numerical experiments which show that using the protocol as a routing service provides privacy guarantees with minimal overhead to user travel time.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Private Location Sharing for Decentralized Routing Services


    Beteiligte:
    Tsao, Matthew (Autor:in) / Yang, Kaidi (Autor:in) / Gopalakrishnan, Karthik (Autor:in) / Pavone, Marco (Autor:in)


    Erscheinungsdatum :

    2022-10-08


    Format / Umfang :

    1105610 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Decentralized enforcement of k-anonymity for location privacy using secret sharing

    Forster, David / Lohr, Hans / Kargl, Frank | IEEE | 2015


    Establishing location-privacy in decentralized long-distance geocast services

    Florian, Martin / Pieper, Felix / Baumgart, Ingmar | IEEE | 2014


    The decentralized field service routing problem

    Avraham, Edison / Raviv, Tal / Khmelnitsky, Eugene | Elsevier | 2017


    Two-Echelon Location-Routing Problem with Time Windows and Transportation Resource Sharing

    Yong Wang / Yaoyao Sun / Xiangyang Guan et al. | DOAJ | 2021

    Freier Zugriff