An Exact and Efficient Privacy-Preserving Spatiotemporal Matching in Mobile Social Networks

1. Introduction

Nowadays, mobile devices, such as smartphones, tablets, laptops, and e-Readers, company with the built-in location-aware devices, are ubiquitous. People could easily establish trust relationships with each other by exchanging and matching their interests, hobbies, experiences, or spatiotemporal profiles. Then, they can choose the well-matched ones for further interaction, such as making friends, sharing news or other funny things. However, since there contains many sensitive information in their personal profiles, revealing it will incur serious consequences. To address this problem, plenty of privacy-preserving matching schemes were proposed over recently years (Von Arb, Bader, Kuhn, & Wattenhofer, 2008; Li, Cao, Yu, & Lou, 2011; Zhang, R., Zhang, Y., Sun, & Yan, 2012; Sarpong & Xu, 2014). These schemes adopt different methods to ensure users choice on the candidates without revealing extra personal information. Yet, it is inevitable that they introduce more computation overhead and communication traffic comparing with direct matching schemes. Furthermore, the work on privacy-preserving profile matching mainly targets non-spatiotemporal user profiles such as hobbies or interests, and it is unclear how to extend these schemes for spatiotemporal profiles. In addition, some solutions are available for privacy-preserving proximity test (Narayanan, Thiagarajan, Lakhani, Hamburg, & Boneh, 2011; Lin, Kune, & Hopper, 2012) which aims at testing the physical proximity of two users at some discrete time points in a privacy-preserving fashion. In contrast, spatiotemporal matching in this work evaluates the proximity of two users for any desired continuous time period. Directly applying the mechanisms in Narayanan et al. (2011) and Lin et al. (2012) to the above problem will be inefficient and impractical. Sun et al. carefully discussed this problem and proposed two protocols for privacy-preserving spatiotemporal matching in Sun, Zhang, R., and Zhang, Y. (2013). One protocol is based on Private Set Intersection Cardinality (PSI-CA) (Cristofaro, Gasti, & Tsudik, 2012) and another one is based on the Bloom filter (Bloom, 1970). Nevertheless, the former is less efficient when users’ spatiotemporal profiles are large, and the latter one make a tradeoff between accuracy and privacy, which lead to the accuracy and privacy in this protocol unable to achieve optimization simultaneously. In addition, both of the protocols are based on the assumption that the physical region of interest can be divided into many square cells, and two users who locate in the same cell are regarded as an encounter. However, this assumption is often imprecise, just like the situations illustrated in Section III-C.

• Contributions: To address the aforementioned problems, we propose an exact and efficient scheme to realize spatiotemporal matching by utilizing overlapping grid system and private set intersection. The contributions of this paper can be summarized as follows:

  • •

    The proposed scheme improves the accuracy problem of existing privacy-preserving spatiotemporal matching. We consider the fact that two users were neighboring with each other actually but been wrongly regarded as have never encounter, or have never close to each other but been wrongly judged as have encountered.

  • •

    The proposed scheme improves the efficiency of spatiotemporal matching. The authors notice that people usually stay at some places (office or home for instance) for a long time, as a result there must be some locations been recorded many times in a user’s spatiotemporal profile during a period. In the matching stage, if each item is taken as an independent location to compare, the computation overhead must be very high. In this paper, the authors take the items with a same location during a period as one element to make matching. In this way, the efficiency has been improved greatly.

  • •

    The authors design a private set intersection protocol for spatiotemporal matching by utilizing the commutative encryption technique (Agrawal, Evfimievski, & Srikant, 2003). Our protocol is secure under Honest but Curious model and can resist against several active attacks. Through thorough analysis, we show that our scheme can achieve our target effectively and efficiently.