1. bookVolume 2018 (2018): Issue 2 (April 2018)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

Privacy-preserving Wi-Fi Analytics

Published Online: 20 Feb 2018
Page range: 4 - 26
Received: 31 Aug 2017
Accepted: 16 Dec 2017
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

As communications-enabled devices are becoming more ubiquitous, it becomes easier to track the movements of individuals through the radio signals broadcasted by their devices. Thus, while there is a strong interest for physical analytics platforms to leverage this information for many purposes, this tracking also threatens the privacy of individuals. To solve this issue, we propose a privacy-preserving solution for collecting aggregate mobility patterns while satisfying the strong guarantee of ε-differential privacy. More precisely, we introduce a sanitization mechanism for efficient, privacy-preserving and non-interactive approximate distinct counting for physical analytics based on perturbed Bloom filters called Pan-Private BLIP. We also extend and generalize previous approaches for estimating distinct count of events and joint events (i.e., intersection and more generally t-out-of-n cardinalities). Finally, we evaluate expirementally our approach and compare it to previous ones on real datasets.


[1] M. Abadi, A. Chu, I. J. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C. Myers, and S. Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, Vienna, Austria, October 2016. ACM.10.1145/2976749.2978318Search in Google Scholar

[2] U. G. Acer, G. Vanderhulst, A. Masshadi, A. Boran, C. Forlivesi, P. M. Scholl, and F. Kawsar. Capturing Personal and Crowd Behavior with Wi-Fi Analytics. In Proceedings of the 3rd International on Workshop on Physical Analytics, WPA ’16, pages 43–48, New York, NY, USA, 2016. ACM.10.1145/2935651.2935656Search in Google Scholar

[3] M. Alaggan, S. Gambs, and A.-M. Kermarrec. BLIP: Non-Interactive Differentially-Private Similarity Computation on Bloom Filters. In Proceedings of the 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS’12), Toronto, Canada, October, 2012.10.1007/978-3-642-33536-5_20Search in Google Scholar

[4] M. Alaggan, S. Gambs, S. Matwin, and M. Tuhin. Sanitization of Call Detail Records via Differentially-Private Bloom Filters. In P. Samarati, editor, Data and Applications Security and Privacy XXIX - 29th Annual IFIP WG 11.3 Working Conference, DBSec 2015, Fairfax, VA, USA, July 13-15, 2015, Proceedings, volume 9149 of Lecture Notes in Computer Science, pages 223–230. Springer, 2015.10.1007/978-3-319-20810-7_15Search in Google Scholar

[5] M. Alaggan, M. Cunche, and M. Minier. Non-interactive (t, n)-Incidence Counting from Differentially Private Indicator Vectors. In Proceedings of the 2017 ACM on International Workshop on Security And Privacy Analytics, IWSPA@CODASPY 2017, Scottsdale, AZ, USA, March 2017. ACM.10.1145/3041008.3041017Search in Google Scholar

[6] M. S. Alvim, M. E. Andrés, K. Chatzikokolakis, and C. Palamidessi. On the relation between differential privacy and quantitative information flow. In L. Aceto, M. Henzinger, and J. Sgall, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, volume 6756 of Lecture Notes in Computer Science, pages 60–76. Springer, 2011.Search in Google Scholar

[7] M. Arlitt and T. Jin. 1998 World Cup Web Site Access Logs, August 1998. URL http://www.acm.org/sigcomm/ITA/.Search in Google Scholar

[8] R. Balu, T. Furon, and S. Gambs. Challenging Differential Privacy: The Case of Non-Interactive Mechanisms. In ESORICS, pages 146–164, 2014.10.1007/978-3-319-11212-1_9Search in Google Scholar

[9] S. Bera and K. Rao. Estimation of origin-destination matrix from traffic counts: the state of the art. European Transport/Trasporti Europei, 49:3–23, 2011.Search in Google Scholar

[10] G. Bianchi, L. Bracciale, and P. Loreti. “Better Than Nothing” Privacy with Bloom Filters: To What Extent? In International Conference on Privacy in Statistical Databases, pages 348–363. Springer, 2012.10.1007/978-3-642-33627-0_27Search in Google Scholar

[11] B. H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM, 13(7):422–426, July 1970. ISSN 0001-0782.10.1145/362686.362692Open DOISearch in Google Scholar

[12] P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin, J. Morrison, M. H. M. Smid, and Y. Tang. On the falsepositive rate of bloom filters. Inf. Process. Lett., 108(4): 210–213, 2008.10.1016/j.ipl.2008.05.018Search in Google Scholar

[13] C. Bouchenard. JC Decaux’s pedestrian tracking system blocked by french data regulator. Marketinglaw, 2015. URL http://marketinglaw.osborneclarke.com/advertising-regulation/jc-decauxs-pedestrian-tracking-system-blocked-by-french-data-regulator/.Search in Google Scholar

[14] A. Z. Broder and M. Mitzenmacher. Survey: Network Applications of Bloom Filters: A Survey. Internet Mathematics, 1(4): 485–509, 2003.Search in Google Scholar

[15] J. W. S. Brown, O. Ohrimenko, and R. Tamassia. Haze: Privacy-preserving real-time traffic statistics. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL’ 13, pages 540–543, New York, NY, USA, 2013. ACM.10.1145/2525314.2525323Search in Google Scholar

[16] J. Cao, B. Carminati, E. Ferrari, and K. L. Tan. CASTLE: A delay-constrained scheme for ks-anonymizing data streams. In 2008 IEEE 24th International Conference on Data Engineering, pages 1376–1378, Apr. 2008.10.1109/ICDE.2008.4497561Search in Google Scholar

[17] K. Chung, M. Mitzenmacher, and S. P. Vadhan. Why simple hash functions work: Exploiting the entropy in a data stream. Theory of Computing, 9:897–945, 2013.Search in Google Scholar

[18] S. Clifford and Q. Hardy. Attention, Shoppers: Store Is Tracking Your Cell. The New York Times, 2013. URL http://www.nytimes.com/2013/07/15/business/attention-shopper-stores-are-tracking-your-cell.html?pagewanted=all.Search in Google Scholar

[19] A. De. Lower bounds in differential privacy. In R. Cramer, editor, Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings, volume 7194 of Lecture Notes in Computer Science, pages 321–338. Springer, 2012.Search in Google Scholar

[20] L. Demir, M. Cunche, and C. Lauradoux. Analysing the privacy policies of Wi-Fi trackers. pages 39–44. ACM Press, 2014.10.1145/2611264.2611266Search in Google Scholar

[21] I. Dinur and K. Nissim. Revealing information while preserving privacy. In F. Neven, C. Beeri, and T. Milo, editors, Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 202–210. ACM, 2003.10.1145/773153.773173Search in Google Scholar

[22] C. Dwork. Differential Privacy. In M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors, Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP’06), Part II, volume 4052 of Lecture Notes in Computer Science, pages 1–12, Venice, Italy, 2006. Springer.Search in Google Scholar

[23] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. Differential privacy under continual observation. In L. J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 715–724. ACM, 2010.10.1145/1806689.1806787Search in Google Scholar

[24] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715–724. ACM, 2010.10.1145/1806689.1806787Search in Google Scholar

[25] C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum, and S. Yekhanin. Pan-Private Streaming Algorithms. In A. C. Yao, editor, Proceedings of the 1st Symposium on Innovations in Computer Science (ICS’10), pages 66–80, Tsinghua University, Beijing, China, 2010. Tsinghua University Press.Search in Google Scholar

[26] U. Erlingsson, V. Pihur, and A. Korolova. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. pages 1054–1067. ACM Press, 2014.10.1145/2660267.2660348Search in Google Scholar

[27] K. Fawaz, K.-H. Kim, and K. G. Shin. Privacy vs. Reward in Indoor Location-Based Services. Proceedings on Privacy Enhancing Technologies, 2016(4):102–122, 2016. ISSN 2299-0984. 00000.10.1515/popets-2016-0031Search in Google Scholar

[28] Federal Trade Commisioin. Retail tracking firm settles ftc charges it misled consumers about opt out choices, 2015. URL https://www.ftc.gov/news-events/press-releases/2015/04/retail-tracking-firm-settles-ftc-charges-it-misled-consumers.Search in Google Scholar

[29] Future of Privacy Forum. Mobile location analytics code of conduct, 2013. URL https://fpf.org/wp-content/uploads/10.22.13-FINAL-MLA-Code.pdf.Search in Google Scholar

[30] N. Gonçalves, R. José, and C. Baquero. Privacy Preserving Gate Counting with Collaborative Bluetooth Scanners. In R. Meersman, T. Dillon, and P. Herrero, editors, On the Move to Meaningful Internet Systems: OTM 2011 Workshops, number 7046 in Lecture Notes in Computer Science, pages 534–543. Springer Berlin Heidelberg, Oct. 2011.10.1007/978-3-642-25126-9_65Search in Google Scholar

[31] P. Higgins and L. Tien. Mobile tracking code of conduct falls short of protecting consumers. Electronic Frontier Foundation, 2013. URL https://www.eff.org/fr/deeplinks/2013/10/mobile-tracking-code-conduct-falls-short-protecting-consumers.Search in Google Scholar

[32] C. Kopp, M. Mock, and M. May. Privacy-preserving distributed monitoring of visit quantities. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’12, pages 438–441, New York, NY, USA, 2012. ACM.10.1145/2424321.2424384Search in Google Scholar

[33] P. A. Laharotte, R. Billot, E. Come, L. Oukhellou, A. Nantes, and N. E. E. Faouzi. Spatiotemporal Analysis of Bluetooth Data: Application to a Large Urban Network. IEEE Transactions on Intelligent Transportation Systems, 16 (3):1439–1448, June 2015. ISSN 1524-9050.10.1109/TITS.2014.2367165Open DOISearch in Google Scholar

[34] J. Li, B. C. Ooi, and W. Wang. Anonymizing streaming data for privacy protection. In Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on, pages 1367–1369. IEEE, 2008.10.1109/ICDE.2008.4497558Search in Google Scholar

[35] R. Lim, M. Zimmerling, and L. Thiele. Passive, Privacy-Preserving Real-Time Counting of Unmodified Smartphones via ZigBee Interference. In 2015 International Conference on Distributed Computing in Sensor Systems, pages 115–126, June 2015.10.1109/DCOSS.2015.13Search in Google Scholar

[36] Liyue Fan and Li Xiong. Adaptively Sharing Time-Series with Differential Privacy. Technical report, Jan. 2013.Search in Google Scholar

[37] J. O. Malley. Here’s what tfl learned from tracking your phone on the tube. Gizmodo UK, 2017. URL http://www.gizmodo.co.uk/2017/02/heres-what-tfl-learned-from-tracking-your-phone-on-the-tube/.Search in Google Scholar

[38] J. Martin, T. Mayberry, C. Donahue, L. Foppe, L. Brown, C. Riggins, E. C. Rye, and D. Brown. A Study of MAC Address Randomization in Mobile Devices and When it Fails. Proceedings on Privacy Enhancing Technologies, 2017(4): 268–286, 2017.10.1515/popets-2017-0054Search in Google Scholar

[39] F. McSherry. Privacy Integrated Queries: an Extensible Platform for Privacy-Preserving Data Analysis. Commun. ACM, 53(9):89–97, 2010.Search in Google Scholar

[40] L. Melis, G. Danezis, and E. D. Cristofaro. Efficient private statistics with succinct sketches. CoRR, abs/1508.06110, 2015.Search in Google Scholar

[41] A. Musa and J. Eriksson. Tracking unmodified smartphones using wi-fi monitors. In Proceedings of the 10th ACM conference on embedded network sensor systems, pages 281–294. ACM, 2012.10.1145/2426656.2426685Search in Google Scholar

[42] R. A. Popa, A. J. Blumberg, H. Balakrishnan, and F. H. Li. Privacy and accountability for location-based aggregate statistics. In Proceedings of the 18th ACM Conference on Computer and Communications Security, CCS ’11, pages 653–666, New York, NY, USA, 2011. ACM.10.1145/2046707.2046781Search in Google Scholar

[43] A. Pyrgelis, E. De Cristofaro, and G. J. Ross. Privacy-friendly mobility analytics using aggregate location data. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, page 34. ACM, 2016.10.1145/2996913.2996971Search in Google Scholar

[44] A. E. C. Redondi, D. Sanvito, and M. Cesana. Passive Classification of Wi-Fi Enabled Devices. pages 51–58. ACM Press, 2016.10.1145/2988287.2989161Search in Google Scholar

[45] E. Shi, H. T. H. Chan, E. Rieffel, R. Chow, and D. Song. Privacy-preserving aggregation of time-series data. In Annual Network & Distributed System Security Symposium (NDSS). Internet Society., 2011.Search in Google Scholar

[46] S. J. Swamidass and P. Baldi. Mathematical correction for fingerprint similarity measures to improve chemical retrieval. Journal of Chemical Information and Modeling, 47(3):952–964, 2007.10.1021/ci600526a17444629Search in Google Scholar

[47] O. Waltari and J. Kangasharju. The Wireless Shark: Identifying WiFi Devices Based on Probe Fingerprints. In Proceedings of the First Workshop on Mobile Data, MobiData ’16, pages 1–6, New York, NY, USA, 2016. ACM. 00000.10.1145/2935755.2935757Search in Google Scholar

[48] K. Whang, B. T. V. Zanden, and H. M. Taylor. A linear-time probabilistic counting algorithm for database applications. ACM Trans. Database Syst., 15(2):208–229, 1990.10.1145/78922.78925Open DOISearch in Google Scholar

[49] Y. Zeng, P. H. Pathak, and P. Mohapatra. Analyzing Shopper’s Behavior Through WiFi Signals. In Proceedings of the 2Nd Workshop on Workshop on Physical Analytics, WPA ’15, pages 13–18, New York, NY, USA, 2015. ACM.10.1145/2753497.2753508Search in Google Scholar

[50] B. Zhou, Y. Han, J. Pei, B. Jiang, Y. Tao, and Y. Jia. Continuous Privacy Preserving Publishing of Data Streams. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT ’09, pages 648–659, New York, NY, USA, 2009. ACM.10.1145/1516360.1516435Search in Google Scholar

[51] G. Zipf. Human behavior and the principle of least effort: an introduction to human ecology. Addison-Wesley Press, 1949.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo