›› 2017, Vol. 32 ›› Issue (5): 905-918.doi: 10.1007/s11390-017-1772-5

Special Issue: Data Management and Data Mining

• Special Section on Crowdsourced Data Management • Previous Articles     Next Articles

Privacy-preserving Task Assignment in Spatial Crowdsourcing

An Liu1,2, Member, CCF, Zhi-Xu Li1,*, Member, CCF, Guan-Feng Liu1, Member, CCF, Kai Zheng1,3, Member, CCF, Min Zhang1, Member, CCF, Qing Li4, Senior Member, IEEE Xiangliang Zhang2, Member, IEEE   

  1. 1 School of Computer Science and Technology, Soochow University, Suzhou 215006, China;
    2 King Abdullah University of Science and Technology, Thuwal 23955, Saudi Arabia;
    3 Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing 100872, China;
    4 Department of Computer Science, City University of Hong Kong, Hong Kong, China
  • Received:2017-03-01 Revised:2017-08-11 Online:2017-09-05 Published:2017-09-05
  • Contact: Zhi-Xu Li,zhixuli@suda.edu.cn E-mail:zhixuli@suda.edu.cn
  • About author:An Liu is an associate professor in the School of Computer Science and Technology at Soochow University, Suzhou. He received his Ph.D. degree in computer science from both City University of Hong Kong (CityU), Hong Kong, and University of Science and Technology of China (USTC), Hefei, in 2009. His research interests include spatial databases, crowdsourcing, data security and privacy, and cloud/service computing.
  • Supported by:

    This work was partially supported by King Abdullah University of Science and Technology (KAUST) and the National Natural Science Foundation of China under Grant Nos. 61572336, 61632016, 61402313, 61572335, and 61472337.

PDF

1074

With the progress of mobile devices and wireless networks, spatial crowdsourcing (SC) is emerging as a promising approach for problem solving. In SC, spatial tasks are assigned to and performed by a set of human workers. To enable effective task assignment, however, both workers and task requesters are required to disclose their locations to untrusted SC systems. In this paper, we study the problem of assigning workers to tasks in a way that location privacy for both workers and task requesters are preserved. We first combine Paillier cryptosystem with Yao's garbled circuits to construct a secure protocol that assigns the nearest worker to a task. Considering that this protocol cannot scale to a large number of workers, we then make use of Geohash, a hierarchical spatial index to design a more efficient protocol that can securely find approximate nearest workers. We theoretically show that these two protocols are secure against semi-honest adversaries. Through extensive experiments on two real-world datasets, we demonstrate the efficiency and effectiveness of our protocols.

[1] Kazemi L, Shahabi C. GeoCrowd:Enabling query answering with spatial crowdsourcing. In Proc. the 20th Int. Conf. Advances in Geographic Information Systems, November 2012, pp.189-198.

[2] Deng D X, Shahabi C, Demiryurek U, Zhu L H. Task selection in spatial crowdsourcing from worker's perspective. GeoInformatica, 2016, 20(3):529-568.

[3] Cheng P, Lian X, Chen Z, Fu R, Chen L, Han J S, Zhao J Z. Reliable diversity-based spatial crowdsourcing by moving workers. Proceedings of the VLDB Endowment, 2015, 8(10):1022-1033.

[4] Cheng P, Lian X, Chen L, Han J S, Zhao J Z. Task assignment on multi-skill oriented spatial crowdsourcing. IEEE Trans. Knowledge and Data Engineering, 2016, 28(8):2201-2215.

[5] Ghinita G, Kalnis P, Khoshgozaran A, Shahabi C, Tan K L. Private queries in location based services:Anonymizers are not necessary. In Proc. the ACM SIGMOD Int. Conf. Management of Data, June 2008, pp.121-132.

[6] Paulet R, Kaosar M G, Yi X, Bertino E. Privacy-preserving and content-protecting location based queries. In Proc. the 28th IEEE Int. Conf. Data Engineering, April 2012, pp.44-53.

[7] Paulet R, Kaosar M G, Yi X, Bertino E. Privacy-preserving and content-protecting location based queries. IEEE Trans. Knowledge and Data Engineering, 2014, 26(5):1200-1210.

[8] Yi X, Paulet R, Bertino E, Varadharajan V. Practical k nearest neighbor queries with location privacy. In Proc. the 30th IEEE Int. Conf. Data Engineering, March 31-April 4, 2014, pp.640-651.

[9] Yi X, Paulet R, Bertino E, Varadharajan V. Practical approximate k nearest neighbor queries with location and query privacy. IEEE Trans. Knowledge and Data Engineering, 2016, 28(6):1546-1559.

[10] Liu S S, Liu A, Zhao L, Liu G F, Li Z X, Zhao P P, Zheng K, Qin L. Efficient query processing with mutual privacy protection for location-based services. In Proc. the 21st Int. Conf. Database Systems for Advanced Applications, April 2016, pp.299-313.

[11] To H, Ghinita G, Shahabi C. A framework for protecting worker location privacy in spatial crowdsourcing. Proceedings of the VLDB Endowment, 2014, 7(10):919-930.

[12] To H, Ghinita G, Shahabi C. PrivGeoCrowd:A toolbox for studying private spatial crowdsourcing. In Proc. the 31st IEEE Int. Conf. Data Engineering, April 2015, pp.1404-1407.

[13] Liu B Z, Chen L, Zhu X Q, Zhang Y, Zhang C Q, Qiu W D. Protecting location privacy in spatial crowdsourcing using encrypted data. In Proc. the 20th Int. Conf. Extending Database Technology, March 2017, pp.478-481.

[14] Liu A, Wang W Q, Shang S, Li Q, Zhang X L. Efficient task assignment in spatial crowdsourcing with worker and task privacy protection. Geoinformatica, 2017. DOI:101007/s10707-017-0305-2.

[15] Dwork C. Differential privacy:A survey of results. In Proc. the 5th Int. Conf. Theory and Applications of Models of Computation, April 2008.

[16] Hightower J, Borriello G. Location systems for ubiquitous computing. Computer, 2001, 34(8):57-66.

[17] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In Proc. the 17th Int. Conf. Theory and Application of Cryptographic Techniques, May 1999, pp.223-238.

[18] Yao A C C. How to generate and exchange secrets. In Proc. the 27th Annual Symp. Foundations of Computer Science, October 1986, pp.162-167.

[19] Lindell Y, Pinkas B. A proof of security of Yao's protocol for two-party computation. Journal of Cryptology, 2009, 22(2):161-188.

[20] Gentry C. Fully homomorphic encryption using ideal lattices. In Proc. the 41st Annual ACM Symp. Theory of Computing, May 31-June 2, 2009, pp.169-178.

[21] Gentry C, Halevi S. Implementing Gentry's fullyhomomorphic encryption scheme. In Proc. the 30th Annual Int. Conf. Theory and Applications of Cryptographic Techniques:Advances in Cryptology, May 2011, pp.129-148.

[22] Elmehdwi Y, Samanthula B K, Jiang W. Secure k-nearest neighbor query over encrypted data in outsourced environments. In Proc. the 30th IEEE Int. Conf. Data Engineering, March 31-April 4, 2014, pp.664-675.

[23] Liu A, Zheng K, Li L, Liu G F, Zhao L, Zhou X F. Efficient secure similarity computation on encrypted trajectory data. In Proc. the 31st IEEE Int. Conf. Data Engineering, April 2015, pp.66-77.

[24] Liu J F, Yang J C, Xiong L, Pei J. Secure skyline queries on cloud platform. In Proc. the 33rd IEEE Int. Conf. Data Engineering, April 2017, pp.633-644.

[25] Goldreich O. Foundations of Cryptography:Volume 2, Basic Applications. Cambridge University Press, 2004.

[26] Samanthula B K, Rao F Y, Bertino E, Yi X. Privacypreserving protocols for shortest path discovery over outsourced encrypted graph data. In Proc. Int. Conf. Information Reuse and Integration, August 2015, pp.427-434.

[27] Nikolaenko V, Ioannidis S, Weinsberg U, Joye M, Taft N, Boneh D. Privacy-preserving matrix factorization. In Proc. the ACM SIGSAC Conf. Computer & Communications Security, November 2013, pp.801-812.

[28] Zhu H H, Meng X R, Kollios G. Privacy preserving similarity evaluation of time series data. In Proc. the 17th Int. Conf. Extending Database Technology, March 2014, pp.499-510.

[29] Kolesnikov V, Sadeghi A R, Schneider T. Improved garbled circuit building blocks and applications to auctions and computing minima. In Proc. the 8th Int. Conf. Cryptology and Network Security, December 2009, pp.1-20.

[30] Mokbel M F, Chow C Y, Aref W G. The new Casper:Query processing for location services without compromising privacy. In Proc. the 32nd Int. Conf. Very Large Data Bases, September 2006, pp.763-774.

[31] Huang Y, Evans D, Katz J, Malka L. Faster secure twoparty computation using garbled circuits. In Proc. the 20th USENIX Conf. Security, August 2011.

[32] Li G L, Wang J N, Zheng Y D, Franklin M J. Crowdsourced data management:A survey. IEEE Trans. Knowledge and Data Engineering, 2016, 28(9):2296-2319.

[33] Chen L, Shahabi C. Spatial crowdsourcing:Challenges and opportunities. Bulletin of the Technical Committee on Data Engineering, 2016, 39(4):14-25.

[34] Tong Y X, She J Y, Ding B L, Wang L B, Chen L. Online mobile micro-task allocation in spatial crowdsourcing. In Proc. the 32nd IEEE Int. Conf. Data Engineering, May 2016, pp.49-60.

[35] Zheng L, Chen L. Mutual benefit aware task assignment in a bipartite labor market. In Proc. the 32nd IEEE Int. Conf. Data Engineering, May 2016, pp.73-84.

[36] Yiu M L, Ghinita G, Jensen C S, Kalnis P. Enabling search services on outsourced private spatial data. The VLDB Journal, 2010, 19(3):363-384.

[37] Yao B, Li F F, Xiao X K. Secure nearest neighbor revisited. In Proc. the 29th IEEE Int. Conf. Data Engineering, April 2013, pp.733-744.

[38] Shin M, Cornelius C, Peebles D, Kapadia A, Kotz D, Triandopoulos N. AnonySense:A system for anonymous opportunistic sensing. Pervasive and Mobile Computing, 2011, 7(1):16-30.

[39] Boutsis I, Kalogeraki V. Privacy preservation for participatory sensing data. In Proc. IEEE Int. Conf. Pervasive Computing and Communications, March 2013, pp.103-113.

[40] Agir B, Papaioannou T G, Narendula R, Aberer K, Hubaux J P. User-side adaptive protection of location privacy in participatory sensing. GeoInformatica, 2014, 18(1):165-191.

[41] Vergara-Laurens I J, Mendez D, Labrador M A. Privacy, quality of information, and energy consumption in participatory sensing systems. In Proc. IEEE Int. Conf. Pervasive Computing and Communications, March 2014, pp.199-207.

[42] Zhang F, He L, He W B, Liu X. Data perturbation with state-dependent noise for participatory sensing. In Proc. IEEE INFOCOM, March 2012, pp.2246-2254.

[43] Li Q H, Cao G H. Efficient and privacy-preserving data aggregation in mobile sensing. In Proc. the 20th IEEE Int. Conf. Network Protocols, October 30-November 2, 2012.

[44] Kazemi L, Shahabi C. A privacy-aware framework for participatory sensing. ACM SIGKDD Explorations Newsletter, 2011, 13(1):43-51.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[7] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[8] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[9] Shang Lujun; Xu Lihui;. Notes on the Design of an Integrated Object-Oriented DBMS Family[J]. , 1991, 6(4): 389 -394 .
[10] Xu Jianguo; Gou Yuchai; Lin Zongkai;. HEPAPS:A PCB Automatic Placement System[J]. , 1992, 7(1): 39 -46 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved