research-article

Practical privacy-preserving location-sharing based services with aggregate statistics

Authors:

Michael Herrmann,

Bart PreneelAuthors Info & Claims

WiSec '14: Proceedings of the 2014 ACM conference on Security and privacy in wireless & mobile networks

Pages 87 - 98

https://doi.org/10.1145/2627393.2627414

Published: 23 July 2014 Publication History

Abstract

Location-sharing-based services (LSBSs) allow users to share their location with their friends in a sporadic manner. In currently deployed LSBSs users must disclose their location to the service provider in order to share it with their friends. This default disclosure of location data introduces privacy risks. We define the security properties that a privacy-preserving LSBS should fulfill and propose two constructions. First, a construction based on identity based broadcast encryption (IBBE) in which the service provider does not learn the user's location, but learns which other users are allowed to receive a location update. Second, a construction based on anonymous IBBE in which the service provider does not learn the latter either. As advantages with respect to previous work, in our schemes the LSBS provider does not need to perform any operations to compute the reply to a location data request, but only needs to forward IBBE ciphertexts to the receivers. We implement both constructions and present a performance analysis that shows their practicality. Furthermore, we extend our schemes such that the service provider, performing some verification work, is able to collect privacy-preserving aggregate statistics on the locations users share with each other.

References

[1]

Michel Abdalla, Mihir Bellare, Dario Catalano, Eike Kiltz, Tadayoshi Kohno, Tanja Lange, John Malone-Lee, Gregory Neven, Pascal Paillier, and Haixia Shi. Searchable encryption revisited: Consistency properties, relation to anonymous ibe, and extensions. In Advances in Cryptology--CRYPTO 2005, pages 205--222. Springer, 2005.

Digital Library

[2]

Niranjan Balasubramanian, Aruna Balasubramanian, and Arun Venkataramani. Energy consumption in mobile phones: a measurement study and implications for network applications. In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement, pages 280--293. ACM, 2009.

Digital Library

[3]

Adam Barth, Dan Boneh, and Brent Waters. Privacy in encrypted content distribution using private broadcast encryption. Financial Cryptography and Data Security, pages 52--64, 2006.

Digital Library

[4]

A.R. Beresford and F. Stajano. Mix zones: User Privacy in Location-aware Services. In Pervasive Computing and Communications Workshops, 2004. Proceedings of the Second IEEE Annual Conference on, pages 127--131, march 2004.

Digital Library

[5]

Igor Bilogrevic, Murtuza Jadliwala, Kübra Kalkan, Jean-Pierre Hubaux, and Imad Aad. Privacy in mobile computing for location-sharing-based services. In Privacy Enhancing Technologies, volume 6794 of Lecture Notes in Computer Science, pages 77--96. Springer Berlin Heidelberg, 2011.

Digital Library

[6]

Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Advances in Cryptology-EUROCRYPT 2004, pages 56--73. Springer, 2004.

[7]

Dan Boneh and Matt Franklin. Identity-based encryption from the weil pairing. In Advances in Cryptology-CRYPTO 2001, pages 213--229. Springer, 2001.

[8]

Dan Boneh, Craig Gentry, and Brent Waters. Collusion resistant broadcast encryption with short ciphertexts and private keys. In Advances in Cryptology--CRYPTO 2005, pages 258--275. Springer, 2005.

Digital Library

[9]

Xavier Boyen and Brent Waters. Anonymous hierarchical identity-based encryption (without random oracles). In Advances in Cryptology-CRYPTO 2006, pages 290--307. Springer, 2006.

Digital Library

[10]

Stefan Brands. Rapid demonstration of linear relations connected by boolean operators. In Walter Fumy, editor, Advances in Cryptology | EUROCRYPT '97, volume 1233 of LNCS, pages 318--333. Springer Verlag, 1997.

Digital Library

[11]

Jan Camenisch. Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. PhD thesis, ETH Zürich, 1998.

[12]

Jan Camenisch, Nathalie Casati, Thomas Groß, and Victor Shoup. Credential authenticated identification and key exchange. In CRYPTO, pages 255--276, 2010.

Digital Library

[13]

Jan Camenisch, Stephan Krenn, and Victor Shoup. A framework for practical universally composable zero-knowledge protocols. In ASIACRYPT, pages 449--467, 2011.

Digital Library

[14]

Jan Camenisch, Stephan Krenn, and Victor Shoup. A framework for practical universally composable zero-knowledge protocols. Cryptology ePrint Archive, Report 2011/228, 2011. http://eprint.iacr.org/.

[15]

Jan Camenisch and Markus Michels. Proving in zero-knowledge that a number n is the product of two safe primes. In Jacques Stern, editor, Advances in Cryptology | EUROCRYPT '99, volume 1592 of LNCS, pages 107--122. Springer Verlag, 1999.

Digital Library

[16]

Bogdan Carbunar, Radu Sion, Rahul Potharaju, and Moussa Ehsan. The shy mayor: Private badges in geosocial networks. In Feng Bao, Pierangela Samarati, and Jianying Zhou, editors, Applied Cryptography and Network Security, volume 7341 of Lecture Notes in Computer Science, pages 436--454. Springer Berlin Heidelberg, 2012.

Digital Library

[17]

D. Chaum and T. Pedersen. Wallet databases with observers. In CRYPTO '92, volume 740 of LNCS, pages 89--105, 1993.

Digital Library

[18]

R. Cramer, I. Damgåard, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In CRYPTO, pages 174--187, 1994.

Digital Library

[19]

Joan Daemen and Vincent Rijmen. The design of Rijndael: AES-the advanced encryption standard. Springer, 2002.

Digital Library

[20]

C--ecile Delerabl--ee. Identity-based broadcast encryption with constant size ciphertexts and private keys. Advances in Cryptology--ASIACRYPT 2007, pages 200--215, 2007.

Digital Library

[21]

Yevgeniy Dodis and Nelly Fazio. Public key trace and revoke scheme secure against adaptive chosen ciphertext attack. Public Key Cryptographyâ A TPKC 2003, pages 100--115, 2002.

Digital Library

[22]

Changyu Dong and Naranker Dulay. Longitude: A privacy-preserving location sharing protocol for mobile applications. In Trust Management V, volume 358 of IFIP Advances in Information and Communication Technology, pages 133--148. Springer Berlin Heidelberg, 2011.

[23]

Nelly Fazio and Irippuge Perera. Outsider-anonymous broadcast encryption with sublinear ciphertexts. Public Key Cryptography--PKC 2012, pages 225--242, 2012.

Digital Library

[24]

Amos Fiat and Moni Naor. Broadcast encryption. In Advances in Cryptologyâ "Cryptoâ" Z93, pages 480--491. Springer, 1994.

Digital Library

[25]

J. Freudiger, R. Shokri, and J. Hubaux. Evaluating the Privacy Risk of Location-Based Services. In Financial Cryptography and Data Security, volume 7035 of LNCS, pages 31--46. Springer Berlin, 2012.

Digital Library

[26]

Julien Freudiger, Raoul Neu, and Jean-Pierre Hubaux. Private sharing of user location over online social networks. 3rd Hot Topics in Privacy Enhancing Technologies (HotPETs 2010), 2010.

[27]

Sébastien Gambs, Olivier Heen, and Christophe Potin. A comparative privacy analysis of geosocial networks. In Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS, SPRINGL '11, pages 33--40, New York, NY, USA, 2011. ACM.

Digital Library

[28]

Craig Gentry and Brent Waters. Adaptive security in broadcast encryption systems (with short ciphertexts). Advances in Cryptology-EUROCRYPT 2009, pages 171--188, 2009.

[29]

Gabriel Ghinita, Maria Luisa Damiani, Claudio Silvestri, and Elisa Bertino. Preventing velocity-based linkage attacks in location-aware applications. GIS '09, pages 246--255, New York, NY, USA, 2009. ACM.

Digital Library

[30]

Gabriel Ghinita, Panos Kalnis, Ali Khoshgozaran, Cyrus Shahabi, and Kian-Lee Tan. Private queries in location based services: anonymizers are not necessary. SIGMOD '08, pages 121--132, New York, NY, USA, 2008. ACM.

Digital Library

[31]

M. Gruteser and D. Grunwald. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. MobiSys '03, pages 31--42, New York, NY, USA, 2003. ACM.

Digital Library

[32]

Leping Huang, Hiroshi Yamane, Kanta Matsuura, and Kaoru Sezaki. Towards modeling wireless location privacy. In George Danezis and David Martin, editors, Privacy Enhancing Technologies, volume 3856 of Lecture Notes in Computer Science, pages 59--77. Springer Berlin Heidelberg, 2006.

Digital Library

[33]

Markulf Kohlweiss and Alfredo Rial. Optimally private access control. In Proceedings of the 12th ACM workshop on Workshop on privacy in the electronic society, pages 37--48. ACM, 2013.

Digital Library

[34]

John Krumm. Inference attacks on location tracks. In Anthony LaMarca, Marc Langheinrich, and KhaiN. Truong, editors, Pervasive Computing, volume 4480 of Lecture Notes in Computer Science, pages 127--143. Springer Berlin Heidelberg, 2007.

Digital Library

[35]

John Krumm. Realistic driving trips for location privacy. In Hideyuki Tokuda, Michael Beigl, Adrian Friday, A. Brush, and Yoshito Tobe, editors, Pervasive Computing, volume 5538 of Lecture Notes in Computer Science, pages 25--41. Springer Berlin / Heidelberg, 2009.

Digital Library

[36]

Allison Lewko, Amit Sahai, and Brent Waters. Revocation systems with very small private keys. In Security and Privacy (SP), 2010 IEEE Symposium on, pages 273--285. IEEE, 2010.

Digital Library

[37]

Mingyan Li, Krishna Sampigethaya, Leping Huang, and Radha Poovendran. Swing & swap: User-centric approaches towards maximizing location privacy. WPES '06, pages 19--28, New York, NY, USA, 2006. ACM.

Digital Library

[38]

Benoît Libert, Kenneth Paterson, and Elizabeth Quaglia. Anonymous broadcast encryption: adaptive security and efficient constructions in the standard model. Public Key Cryptography--PKC 2012, pages 206--224, 2012.

Digital Library

[39]

Zi Lin, Denis Foo Kune, and Nicholas Hopper. Efficient private proximity testing with gsm location sketches. In AngelosD. Keromytis, editor, Financial Cryptography and Data Security, volume 7397 of Lecture Notes in Computer Science, pages 73--88. Springer Berlin Heidelberg, 2012.

[40]

Dalit Naor, Moni Naor, and Je Lotspiech. Revocation and tracing schemes for stateless receivers. In Advances in Cryptology-CRYPTO 2001, pages 41--62. Springer, 2001.

Digital Library

[41]

Arvind Narayanan, Narendran Thiagarajan, Mugdha Lakhani, Michael Hamburg, and Dan Boneh. Location privacy via private proximity testing. In NDSS, 2011.

[42]

Femi Olumon, Piotr Tysowski, Ian Goldberg, and Urs Hengartner. Achieving efficient query privacy for location based services. In Privacy Enhancing Technologies, pages 93--110. Springer, 2010.

Digital Library

[43]

Tatiana Pontes, Marisa Vasconcelos, Jussara Almeida, Ponnurangam Kumaraguru, and Virgilio Almeida. We know where you live: Privacy characterization of foursquare behavior. In 4th International Workshop on Location-Based Social Networks (LBSN 2012), 2012.

Digital Library

[44]

Raluca Ada Popa, Andrew J Blumberg, Hari Balakrishnan, and Frank H Li. Privacy and accountability for location-based aggregate statistics. In Proceedings of the 18th ACM conference on Computer and communications security, pages 653--666. ACM, 2011.

Digital Library

[45]

K.P.N. Puttaswamy, Shiyuan Wang, T. Steinbauer, D. Agrawal, A. El Abbadi, C. Kruegel, and B.Y. Zhao. Preserving location privacy in geosocial applications. Mobile Computing, IEEE Transactions on, 13(1):159--173, Jan 2014.

Digital Library

[46]

C. Schnorr. Efficient signature generation for smart cards. Journal of Cryptology, 4(3):239--252, 1991.

Digital Library

[47]

R. Shokri, G. Theodorakopoulos, J. Le Boudec, and J. Hubaux. Quantifying Location Privacy. In Security and Privacy (SP), pages 247 --262, May 2011.

Digital Library

[48]

C.R. Vicente, D. Freni, C. Bettini, and Christian S. Jensen. Location-related privacy in geo-social networks. Internet Computing, IEEE, 15(3):20--27, 2011.

Digital Library

[49]

Brent Waters. Dual system encryption: Realizing fully secure ibe and hibe under simple assumptions. Advances in Cryptology-CRYPTO 2009, pages 619--636, 2009.

Digital Library

[50]

Ge Zhong, Ian Goldberg, and Urs Hengartner. Louis, lester and pierre: Three protocols for location privacy. In Nikita Borisov and Philippe Golle, editors, Privacy Enhancing Technologies, volume 4776 of Lecture Notes in Computer Science, pages 62--76. Springer Berlin Heidelberg, 2007.

Digital Library

Cited By

Camenisch JDubovitskaya MRial A(2021)Concise UC Zero-Knowledge Proofs for Oblivious Updatable Databases2021 IEEE 34th Computer Security Foundations Symposium (CSF)10.1109/CSF51468.2021.00008(1-16)Online publication date: Jun-2021
https://doi.org/10.1109/CSF51468.2021.00008
Zhao KTu ZXu FLi YZhang PPei DSu LJin D(2019)Walking Without Friends: Publishing Anonymized Trajectory Dataset Without Leaking Social RelationshipsIEEE Transactions on Network and Service Management10.1109/TNSM.2019.290754216:3(1212-1225)Online publication date: Sep-2019
https://doi.org/10.1109/TNSM.2019.2907542
Chakraborty BVerma SSingh K(2019)Differentially Private Location Privacy Preservation in Wireless Sensor NetworksWireless Personal Communications: An International Journal10.1007/s11277-018-6026-5104:1(387-406)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s11277-018-6026-5
Show More Cited By

Index Terms

Practical privacy-preserving location-sharing based services with aggregate statistics
1. Applied computing
  1. Electronic commerce
    1. E-commerce infrastructure
    2. Secure online transactions
2. Security and privacy
  1. Human and societal aspects of security and privacy
  2. Software and application security
    1. Domain-specific security and privacy architectures

Recommendations

Resilient Privacy Protection for Location-Based Services through Decentralization

Location-Based Services (LBSs) provide valuable services, with convenient features for mobile users. However, the location and other information disclosed through each query to the LBS erodes user privacy. This is a concern especially because LBS ...
Preserving location privacy without exact locations in mobile services

Privacy preservation has recently received considerable attention in location-based services (LBSs). A large number of location cloaking algorithms have been proposed for protecting the location privacy of mobile users. However, most existing cloaking ...
Collaborative trajectory privacy preserving scheme in location-based services

Location-based services (LBSs) have been gaining considerable popularity and are becoming the fastest growing activity-related services that people use in their daily life. While users benefit from LBSs, the collection and analysis of participators ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WiSec '14: Proceedings of the 2014 ACM conference on Security and privacy in wireless & mobile networks

July 2014

246 pages

ISBN:9781450329729

DOI:10.1145/2627393

Conference Chair:
Gergely Acs
Inria, France
,
General Chairs:
Andrew Martin
Oxford University, UK
,
Ivan Martinovic
Oxford University, UK
,
Program Chairs:
Claude Castelluccia
Inria, France
,
Patrick Traynor
University of Florida, USA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

In-Cooperation

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

WiSec'14

Sponsor:

SIGSAC

WiSec'14: 7th ACM Conference on Security & Privacy in Wireless and Mobile Networks

July 23 - 25, 2014

Oxford, United Kingdom

Acceptance Rates

WiSec '14 Paper Acceptance Rate 25 of 96 submissions, 26%;

Overall Acceptance Rate 98 of 338 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
367
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Camenisch JDubovitskaya MRial A(2021)Concise UC Zero-Knowledge Proofs for Oblivious Updatable Databases2021 IEEE 34th Computer Security Foundations Symposium (CSF)10.1109/CSF51468.2021.00008(1-16)Online publication date: Jun-2021
https://doi.org/10.1109/CSF51468.2021.00008
Zhao KTu ZXu FLi YZhang PPei DSu LJin D(2019)Walking Without Friends: Publishing Anonymized Trajectory Dataset Without Leaking Social RelationshipsIEEE Transactions on Network and Service Management10.1109/TNSM.2019.290754216:3(1212-1225)Online publication date: Sep-2019
https://doi.org/10.1109/TNSM.2019.2907542
Chakraborty BVerma SSingh K(2019)Differentially Private Location Privacy Preservation in Wireless Sensor NetworksWireless Personal Communications: An International Journal10.1007/s11277-018-6026-5104:1(387-406)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s11277-018-6026-5
(2018)A new scheme of preserving user privacy for location-based serviceInternational Journal of Electronic Security and Digital Forensics10.5555/3292811.329281810:4(417-433)Online publication date: 16-Dec-2018
https://dl.acm.org/doi/10.5555/3292811.3292818
Becker DGuajardo JZimmermann KThuraisingham BLee A(2017)SOMARProceedings of the 2017 on Workshop on Privacy in the Electronic Society10.1145/3139550.3139563(21-30)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.1145/3139550.3139563
Schlegel RChow CHuang QWong D(2017)Privacy-Preserving Location Sharing Services for Social NetworksIEEE Transactions on Services Computing10.1109/TSC.2016.251433810:5(811-825)Online publication date: 1-Sep-2017
https://doi.org/10.1109/TSC.2016.2514338
Chen XMu YWang XShi R(2016)Privacy-enhanced distance computation with applicationsInternational Journal of Electronic Security and Digital Forensics10.1504/IJESDF.2016.0774488:3(234-249)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJESDF.2016.077448
Gramaglia MFiore MHuici FBianchi G(2015)Hiding mobile traffic fingerprints with GLOVEProceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies10.1145/2716281.2836111(1-13)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1145/2716281.2836111

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents