Privacy and accountability for location-based aggregate statistics

ABSTRACT

A significant and growing class of location-based mobile applications aggregate position data from individual devices at a server and compute aggregate statistics over these position streams. Because these devices can be linked to the movement of individuals, there is significant danger that the aggregate computation will violate the location privacy of individuals. This paper develops and evaluates PrivStats, a system for computing aggregate statistics over location data that simultaneously achieves two properties: first, provable guarantees on location privacy even in the face of any side information about users known to the server, and second, privacy-preserving accountability (i.e., protection against abusive clients uploading large amounts of spurious data). PrivStats achieves these properties using a new protocol for uploading and aggregating data anonymously as well as an efficient zero-knowledge proof of knowledge protocol we developed from scratch for accountability. We implemented our system on Nexus One smartphones and commodity servers. Our experimental results demonstrate that PrivStats is a practical system: computing a common aggregate (e.g., count) over the data of 10,000 clients takes less than 0.46 s at the server and the protocol has modest latency (0.6 s) to upload data from a Nexus phone. We also validated our protocols on real driver traces from the CarTel project.

References

1. M. Abadi, A. Birrell, M. Burrows, F. Dabek, and T. Wobber. Bankable postage for network services. In ASIAN, 2003.
2. J. Balasch, A. Rial, C. Troncoso, B. Preneel, I. Verbauwhede, and C. Geuens. PrETP: Privacy-preserving electronic toll pricing. Usenix Security, 2010.
3. M. Bellare and O. Goldreich. On defining proofs of knowledge. CRYPTO, 1992.
4. A. Boldyreva, N. Chenette, Y. Lee, and A. O'Neill. Order-preserving symmetric encryption. In EUROCRYPT, 2009.
5. F. Boudot. Efficient proofs that a committed number lies in an interval. EUROCRYPT, 2000.
6. M. Burkhart, M. Strasser, D. Many, and X. Dimitropoulos. SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics. Usenix Security, 2010.
7. California Department of Transportation. Caltrans guide for the preparation of traffic impact studies.
8. J. Camenisch, S. Hohenberger, M. Kohlweiss, A. Lysyanskaya, and M. Meyerovich. How to win the clonewars: Efficient periodic n-times anonymous authentication. In CCS, 2006.
9. J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Balancing accountability and privacy using e-cash. Security and Cryptography for Networks, 2006.
10. J. Camenisch and A. Lysyanskaya. A Signature Scheme with Efficient Protocols. Security and Cryptography for Networks, 2002.
11. C. Dwork. Differential privacy: A survey of results. In TAMC 1--19, 2008.
12. E-ZPass. How it works. http://www.ezpass.com/index.html.
13. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. CRYPTO, 1986.
14. B. Gedik and L. Liu. Location privacy in mobile systems: A personalized anonymization model. In ICDCS, 2005.
15. S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. Symposium on the Theory of Computation, 1985.
16. M. Gruteser and D. Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking. In MobiSys, 2003.
17. M. Gruteser and B. Hoh. On the anonymity of periodic location samples. In IEEE Pervasive Computing, 2005.
18. B. Hoh, M. Gruteser, R. Herring, J. Ban, D. Work, J.-C. Herrera, A. Bayen, M. Annavaram, and Q. Jacobson. Virtual trip lines for distributed privacy-preserving traffic monitoring. In Mobisys, 2008.
19. B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady. Enhancing security and privacy in traffic-monitoring systems. In IEEE Pervasive Computing, 2006.
20. B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady. Preserving privacy in GPS traces via uncertainty-aware path cloaking. In CCS, 2007.
21. B. Hull, V. Bychkovsky, K. Chen, M. Goraczko, A. Miu, E. Shih, Y. Zhang, H. Balakrishnan, and S. Madden. CarTel: A Distributed Mobile Sensor Computing System. Sensys, 2006.
22. N. Husted and S. Myers. Mobile location tracking in metro areas: Malnets and others. In CCS, 2010.
23. D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In STOC, 1997.
24. J. Krumm. Inference attacks on location tracks. In IEEE Pervasive Computing, 2007.
25. J. Lowensohn. Apple sued over location tracking in iOS. http://news.cnet.com/8301--27076\_3--20057245--248.html, 2011. CNET News.
26. E. Mills. Google sued over Android data location collection. http://news.cnet.com/8301--27080\_3--20058493--245.html, 2011. CNET News.
27. Mobile Millennium. http://traffic.berkeley.edu/.
28. M. Mun, S. Reddy, K. Shilton, N. Yau, P. Boda, J. Burke, D. Estrin, M. Hansen, E. Howard, and R. West. PEIR, the personal environmental impact report, as a platform for participatory sensing systems research. In MobiSys, 2009.
29. A. Narayanan, N. Thiagarajan, M. Lakhani, M. Hamburg, and D. Boneh. Location privacy via private proximity testing. NDSS, 2011.
30. P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, 1999.
31. T. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. CRYPTO, 1991.
32. R. A. Popa, H. Balakrishnan, and A. J. Blumberg. VPriv: Protecting privacy in location-based vehicular services. Usenix Security, 2009.
33. K. Puttaswamy and B. Zhao. Preserving privacy in location-based mobile social applications. International Workshop on Mobile Computing and Applications, 2010.
34. R. Reid. TomTom admits to sending your routes and speed information to the police, 2011. CNET UK.
35. P. Riley. The tolls of privacy: An underestimated roadblock for electronic toll collection usage. In Third International Conference on Legal, Security, and Privacy Issues in IT, 2008.
36. C. P. Schnorr. Efficient identification and signatures for smart cards. CRYPTO, 1989.
37. E. Shi, T.-H. H. Chan, E. Rieffel, R. Chow, and D. Song. Privacy-preserving aggregation of time-series data. In NDSS, 2011.
38. R. Shokri, G. Theodorakopoulos, J.-Y. L. Boudec, and J.-P. Hubaux. Quantifying location privacy. In IEEE Symposium on Security and Privacy, 2011.
39. M. Walfish, J. Zamfirescu, H. Balakrishnan, D. Karger, and S. Shenker. Distributed quota enforcement for spam control. In NSDI, 2006.
40. WMUR. Police: Thieves robbed home based on Facebook, 2010. http://www.wmur.com/r/24943582/detail.html.
41. G. Zhong, I. Goldberg, and U. Hengartner. Louis, Lester, and Pierre: Three protocols for location privacy. International Conference on Privacy-Enhancing Technologies, 2007.

Index Terms

• Security and privacy

  • Network security