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

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

Xiuguang Li (National Key Laboratory of Integrated Networks Services, Xidian University, Xi'an, China), Yuanyuan He (Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China), Ben Niu (Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China), Kai Yang (Key Laboratory of Information and Network Security of Chinese Armed Police Force, Engineering University of Chinese Armed Police Force, Xi'an, China) and Hui Li (National Key Laboratory of Integrated Networks Services, Xidian University, Xi'an, China)
Copyright: © 2016 |Pages: 12
DOI: 10.4018/IJTHI.2016040103


With the rapid development of mobile smartphone and its built-in location-aware devices, people are possible to establish trust relationships and further interaction with each other based their matched interests, hobbies, experiences, or spatiotemporal profiles. However, the possibility of sensitive information leakage and heavy computation overhead constrain the widespread use of the matching schemes in mobile social networks. Many privacy-preserving matching schemes were proposed recently years, but how to achieve privacy-preserving spatiotemporal matching exactly and efficiently remains an open question. In this paper, the authors propose a novel spatiotemporal matching scheme. The overlapping grid system is introduced into the scheme to improve the accuracy of spatiotemporal matching, and many repetitive records in a user's spatiotemporal profile are counted as one item so as to cut down the computation overhead. Their scheme decreases the spatiotemporal matching error, and promotes the efficiency of private matchmaking simultaneously. Thorough security analysis and evaluation results indicate that our scheme is effective and efficient.
Article Preview

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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 16: 4 Issues (2020): Forthcoming, Available for Pre-Order
Volume 15: 4 Issues (2019): 3 Released, 1 Forthcoming
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing