{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T07:11:05Z","timestamp":1763968265897,"version":"3.41.0"},"reference-count":44,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"4","license":[{"start":{"date-parts":[[2017,10,1]],"date-time":"2017-10-01T00:00:00Z","timestamp":1506816000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The continuously increasing use of location-based services poses an important threat to the privacy of users. A natural defense is to employ an obfuscation mechanism, such as those providing geo-indistinguishability, a framework for obtaining formal privacy guarantees that has become popular in recent years.<\/jats:p><jats:p>Ideally, one would like to employ an optimal obfuscation mechanism, providing the best utility among those satisfying the required privacy level. In theory optimal mechanisms can be constructed via linear programming. In practice, however, this is only feasible for a radically small number of locations. As a consequence, all known applications of geo-indistinguishability simply use noise drawn from a planar Laplace distribution.<\/jats:p><jats:p>In this work, we study methods for substantially improving the utility of location obfuscation, while maintaining practical applicability as a main goal. We provide such solutions for both infinite (continuous or discrete) as well as large but finite domains of locations, using a Bayesian remapping procedure as a key ingredient. We evaluate our techniques in two real world complete datasets, without any restriction on the evaluation area, and show important utility improvements with respect to the standard planar Laplace approach.<\/jats:p>","DOI":"10.1515\/popets-2017-0051","type":"journal-article","created":{"date-parts":[[2017,10,17]],"date-time":"2017-10-17T10:01:46Z","timestamp":1508234506000},"page":"308-328","source":"Crossref","is-referenced-by-count":42,"title":["Efficient Utility Improvement for Location Privacy"],"prefix":"10.56553","volume":"2017","author":[{"given":"Konstantinos","family":"Chatzikokolakis","sequence":"first","affiliation":[{"name":"CNRS, Inria and LIX , \u00c9cole Polytechnique , France"}]},{"given":"Ehab","family":"ElSalamouny","sequence":"additional","affiliation":[{"name":"Inria, France and Faculty of Computers and Informatics , Suez Canal University , Egypt"}]},{"given":"Catuscia","family":"Palamidessi","sequence":"additional","affiliation":[{"name":"Inria and LIX , \u00c9cole Polytechnique , France"}]}],"member":"35752","published-online":{"date-parts":[[2017,10,10]]},"reference":[{"unstructured":"[1] K. Orland, \u201cStalker Victims Should Check For GPS.\u201d The Associated Press, 2003. http:\/\/www.cbsnews.com\/news\/stalker-victims-should-check-for-gps\/.","key":"2021040701551520377_j_popets-2017-0051_ref_001_w2aab3b7c16b1b6b1ab1ab1Aa"},{"unstructured":"[2] J. Brownlee, \u201cThis Creepy App Isn\u2019t Just Stalking Women Without Their Knowledge, It\u2019s A Wake-Up Call About Facebook Privacy (Update),\u201d 2012. http:\/\/www.cultofmac.com\/157641\/.","key":"2021040701551520377_j_popets-2017-0051_ref_002_w2aab3b7c16b1b6b1ab1ab2Aa"},{"unstructured":"[3] J. Simerman, \u201cFasTrak to courthouse.\u201d East Bay Times, 2007. http:\/\/www.eastbaytimes.com\/2007\/06\/05\/fastrak-to-courthouse\/.","key":"2021040701551520377_j_popets-2017-0051_ref_003_w2aab3b7c16b1b6b1ab1ab3Aa"},{"doi-asserted-by":"crossref","unstructured":"[4] D. Ashbrook and T. Starner, \u201cUsing gps to learn significant locations and predict movement across multiple users,\u201d Personal and Ubiquitous Computing, vol. 7, no. 5, pp. 275\u2013286, 2003.10.1007\/s00779-003-0240-0","key":"2021040701551520377_j_popets-2017-0051_ref_004_w2aab3b7c16b1b6b1ab1ab4Aa","DOI":"10.1007\/s00779-003-0240-0"},{"doi-asserted-by":"crossref","unstructured":"[5] R. Shokri, G. Theodorakopoulos, C. Troncoso, J.-P. Hubaux, and J.-Y. L. Boudec, \u201cProtecting location privacy: optimal strategy against localization attacks,\u201d in Proc. of CCS, pp. 617\u2013627, ACM, 2012.","key":"2021040701551520377_j_popets-2017-0051_ref_005_w2aab3b7c16b1b6b1ab1ab5Aa","DOI":"10.1145\/2382196.2382261"},{"doi-asserted-by":"crossref","unstructured":"[6] M. E. Andr\u00e9s, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, \u201cGeo-indistinguishability: differential privacy for location-based systems,\u201d in Proc. of CCS, pp. 901\u2013914, ACM, 2013.","key":"2021040701551520377_j_popets-2017-0051_ref_006_w2aab3b7c16b1b6b1ab1ab6Aa","DOI":"10.1145\/2508859.2516735"},{"doi-asserted-by":"crossref","unstructured":"[7] N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, \u201cOptimal geo-indistinguishable mechanisms for location privacy,\u201d in Proc. of CCS, 2014.","key":"2021040701551520377_j_popets-2017-0051_ref_007_w2aab3b7c16b1b6b1ab1ab7Aa","DOI":"10.1145\/2660267.2660345"},{"unstructured":"[8] R. Shokri, \u201cPrivacy games: Optimal user-centric data obfuscation,\u201d Proceedings on Privacy Enhancing Technologies, vol. 2015, no. 2, pp. 299\u2013315, 2015.","key":"2021040701551520377_j_popets-2017-0051_ref_008_w2aab3b7c16b1b6b1ab1ab8Aa"},{"unstructured":"[9] C. Dwork, \u201cDifferential privacy,\u201d in Proc. of ICALP, vol. 4052 of LNCS, pp. 1\u201312, Springer, 2006.","key":"2021040701551520377_j_popets-2017-0051_ref_009_w2aab3b7c16b1b6b1ab1ab9Aa"},{"unstructured":"[10] \u201cLocation guard.\u201d https:\/\/github.com\/chatziko\/location-guard.","key":"2021040701551520377_j_popets-2017-0051_ref_010_w2aab3b7c16b1b6b1ab1ac10Aa"},{"doi-asserted-by":"crossref","unstructured":"[11] K. Fawaz and K. G. Shin, \u201cLocation privacy protection for smartphone users,\u201d in Proc. of CCS, pp. 239\u2013250, ACM Press, 2014.","key":"2021040701551520377_j_popets-2017-0051_ref_011_w2aab3b7c16b1b6b1ab1ac11Aa","DOI":"10.1145\/2660267.2660270"},{"unstructured":"[12] K. Fawaz, H. Feng, and K. G. Shin, \u201cAnatomization and protection of mobile apps\u2019 location privacy threats,\u201d in Proc. of USENIX Security 2015, pp. 753\u2013768, USENIX Association, 2015.","key":"2021040701551520377_j_popets-2017-0051_ref_012_w2aab3b7c16b1b6b1ab1ac12Aa"},{"doi-asserted-by":"crossref","unstructured":"[13] C. Ma and C. W. Chen, \u201cNearby friend discovery with geo-indistinguishability to stalkers,\u201d Procedia Computer Science, vol. 34, pp. 352 \u2013 359, 2014.","key":"2021040701551520377_j_popets-2017-0051_ref_013_w2aab3b7c16b1b6b1ab1ac13Aa","DOI":"10.1016\/j.procs.2014.07.036"},{"unstructured":"[14] \u201cQgis processing provider plugin.\u201d https:\/\/github.com\/SpatialVision\/differential_privacy.","key":"2021040701551520377_j_popets-2017-0051_ref_014_w2aab3b7c16b1b6b1ab1ac14Aa"},{"unstructured":"[15] L. Pournajaf, L. Xiong, V. Sunderam, and X. Xu, \u201cStac: Spatial task assignment for crowd sensing with cloaked participant locations,\u201d in Proceedings of the 23rd SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems, GIS \u201915, pp. 90:1\u201390:4, ACM, 2015.","key":"2021040701551520377_j_popets-2017-0051_ref_015_w2aab3b7c16b1b6b1ab1ac15Aa"},{"unstructured":"[16] Y. Xiao and L. Xiong, \u201cProtecting locations with differential privacy under temporal correlations,\u201d in Proc. of CCS, pp. 1298\u20131309, ACM, 2015.","key":"2021040701551520377_j_popets-2017-0051_ref_016_w2aab3b7c16b1b6b1ab1ac16Aa"},{"doi-asserted-by":"crossref","unstructured":"[17] A. Ghosh, T. Roughgarden, and M. Sundararajan, \u201cUniversally utility-maximizing privacy mechanisms,\u201d in Proc. of STOC, pp. 351\u2013360, ACM, 2009.","key":"2021040701551520377_j_popets-2017-0051_ref_017_w2aab3b7c16b1b6b1ab1ac17Aa","DOI":"10.1145\/1536414.1536464"},{"unstructured":"[18] K. Chatzikokolakis, C. Palamidessi, and M. Stronati, \u201cConstructing elastic distinguishability metrics for location privacy,\u201d PoPETs, vol. 2015, no. 2, pp. 156\u2013170, 2015.","key":"2021040701551520377_j_popets-2017-0051_ref_018_w2aab3b7c16b1b6b1ab1ac18Aa"},{"unstructured":"[19] E. ElSalamouny, K. Chatzikokolakis, and C. Palamidessi, \u201cGeneralized differential privacy: Regions of priors that admit robust optimal mechanisms,\u201d in Horizons of the Mind, vol. 8464 of LNCS, pp. 292\u2013318, Springer Int. Publishing, 2014.","key":"2021040701551520377_j_popets-2017-0051_ref_019_w2aab3b7c16b1b6b1ab1ac19Aa"},{"doi-asserted-by":"crossref","unstructured":"[20] M. Gruteser and D. Grunwald, \u201cAnonymous usage of location-based services through spatial and temporal cloaking,\u201d in Proc. of MobiSys, USENIX, 2003.","key":"2021040701551520377_j_popets-2017-0051_ref_020_w2aab3b7c16b1b6b1ab1ac20Aa","DOI":"10.1145\/1066116.1189037"},{"doi-asserted-by":"crossref","unstructured":"[21] P. Samarati and L. Sweeney, \u201cGeneralizing data to provide anonymity when disclosing information (abstract),\u201d in Proc. of PODS, pp. 188\u2013188, ACM Press, 1998.","key":"2021040701551520377_j_popets-2017-0051_ref_021_w2aab3b7c16b1b6b1ab1ac21Aa","DOI":"10.1145\/275487.275508"},{"doi-asserted-by":"crossref","unstructured":"[22] L. Sweeney, \u201ck-anonymity: A model for protecting privacy,\u201d Int. Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 5, pp. 557\u2013570, 2002.","key":"2021040701551520377_j_popets-2017-0051_ref_022_w2aab3b7c16b1b6b1ab1ac22Aa","DOI":"10.1142\/S0218488502001648"},{"doi-asserted-by":"crossref","unstructured":"[23] L. Sweeney, \u201cAchieving k-anonymity privacy protection using generalization and suppression,\u201d Int. Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 5, pp. 571\u2013588, 2002.","key":"2021040701551520377_j_popets-2017-0051_ref_023_w2aab3b7c16b1b6b1ab1ac23Aa","DOI":"10.1142\/S021848850200165X"},{"unstructured":"[24] P. Samarati, \u201cProtecting respondents\u2019 identities in microdata release,\u201d IEEE Trans. Knowl. Data Eng, vol. 13, no. 6, pp. 1010\u20131027, 2001.","key":"2021040701551520377_j_popets-2017-0051_ref_024_w2aab3b7c16b1b6b1ab1ac24Aa"},{"doi-asserted-by":"crossref","unstructured":"[25] A. Machanavajjhala, D. Kifer, J. Gehrke, and M. Venkitasubramaniam, \u201cl-diversity: Privacy beyond k-anonymity,\u201d ACM Trans. on Knowledge Discovery from Data (TKDD), vol. 1, no. 1, p. 3, 2007.","key":"2021040701551520377_j_popets-2017-0051_ref_025_w2aab3b7c16b1b6b1ab1ac25Aa","DOI":"10.1145\/1217299.1217302"},{"doi-asserted-by":"crossref","unstructured":"[26] N. Li, T. Li, and S. Venkatasubramanian, \u201ct-closeness: Privacy beyond k-anonymity and l-diversity.,\u201d in ICDE, vol. 7, pp. 106\u2013115, 2007.","key":"2021040701551520377_j_popets-2017-0051_ref_026_w2aab3b7c16b1b6b1ab1ac26Aa","DOI":"10.1109\/ICDE.2007.367856"},{"doi-asserted-by":"crossref","unstructured":"[27] A. Solanas, F. Seb\u00e9, and J. Domingo-Ferrer, \u201cMicroaggregation-based heuristics for p-sensitive k-anonymity: one step beyond,\u201d in Proc. of PAIS 2008, ACM Int. Conf. Proceeding Series, pp. 61\u201369, ACM, 2008.","key":"2021040701551520377_j_popets-2017-0051_ref_027_w2aab3b7c16b1b6b1ab1ac27Aa","DOI":"10.1145\/1379287.1379300"},{"doi-asserted-by":"crossref","unstructured":"[28] A. R. Beresford and F. Stajano, \u201cLocation privacy in pervasive computing,\u201d IEEE Pervasive Computing, vol. 2, no. 1, pp. 46\u201355, 2003.","key":"2021040701551520377_j_popets-2017-0051_ref_028_w2aab3b7c16b1b6b1ab1ac28Aa","DOI":"10.1109\/MPRV.2003.1186725"},{"doi-asserted-by":"crossref","unstructured":"[29] A. Machanavajjhala, D. Kifer, J. M. Abowd, J. Gehrke, and L. Vilhuber, \u201cPrivacy: Theory meets practice on the map,\u201d in Proc. of ICDE, pp. 277\u2013286, IEEE, 2008.","key":"2021040701551520377_j_popets-2017-0051_ref_029_w2aab3b7c16b1b6b1ab1ac29Aa","DOI":"10.1109\/ICDE.2008.4497436"},{"doi-asserted-by":"crossref","unstructured":"[30] S.-S. Ho and S. Ruan, \u201cDifferential privacy for location pattern mining,\u201d in Proc. of SPRINGL, pp. 17\u201324, ACM, 2011.","key":"2021040701551520377_j_popets-2017-0051_ref_030_w2aab3b7c16b1b6b1ab1ac30Aa","DOI":"10.1145\/2071880.2071884"},{"unstructured":"[31] R. Dewri, \u201cLocal differential perturbations: Location privacy under approximate knowledge attackers,\u201d IEEE Trans. on Mobile Computing, vol. 99, no. PrePrints, p. 1, 2012.","key":"2021040701551520377_j_popets-2017-0051_ref_031_w2aab3b7c16b1b6b1ab1ac31Aa"},{"doi-asserted-by":"crossref","unstructured":"[32] F. Durr, P. Skvortsov, and K. Rothermel, \u201cPosition sharing for location privacy in non-trusted systems,\u201d in Proc. of PerCom 2011, pp. 189\u2013196, IEEE, 2011.","key":"2021040701551520377_j_popets-2017-0051_ref_032_w2aab3b7c16b1b6b1ab1ac32Aa","DOI":"10.1109\/PERCOM.2011.5767584"},{"unstructured":"[33] E. ElSalamouny and S. Gambs, \u201cDifferential privacy models for location-based services,\u201d Trans. on Data Privacy, vol. 9, no. 1, pp. 15\u201348, 2016.","key":"2021040701551520377_j_popets-2017-0051_ref_033_w2aab3b7c16b1b6b1ab1ac33Aa"},{"unstructured":"[34] C. A. Ardagna, M. Cremonini, E. Damiani, S. D. C. di Vimercati, and P. Samarati, \u201cLocation privacy protection through obfuscation-based techniques,\u201d in Proc. of DAS, vol. 4602 of LNCS, pp. 47\u201360, Springer, 2007.","key":"2021040701551520377_j_popets-2017-0051_ref_034_w2aab3b7c16b1b6b1ab1ac34Aa"},{"doi-asserted-by":"crossref","unstructured":"[35] B. Bamba, L. Liu, P. Pesti, and T. Wang, \u201cSupporting anonymous location queries in mobile environments with privacygrid,\u201d in Proc. of WWW, pp. 237\u2013246, ACM, 2008.","key":"2021040701551520377_j_popets-2017-0051_ref_035_w2aab3b7c16b1b6b1ab1ac35Aa","DOI":"10.21236\/ADA470490"},{"unstructured":"[36] M. Duckham and L. Kulik, \u201cA formal model of obfuscation and negotiation for location privacy,\u201d in Proc. of PERVASIVE, vol. 3468 of LNCS, pp. 152\u2013170, Springer, 2005.","key":"2021040701551520377_j_popets-2017-0051_ref_036_w2aab3b7c16b1b6b1ab1ac36Aa"},{"unstructured":"[37] M. Xue, P. Kalnis, and H. Pung, \u201cLocation diversity: Enhanced privacy protection in location based services,\u201d in Proc. of LoCA, vol. 5561 of LNCS, pp. 70\u201387, Springer, 2009.","key":"2021040701551520377_j_popets-2017-0051_ref_037_w2aab3b7c16b1b6b1ab1ac37Aa"},{"doi-asserted-by":"crossref","unstructured":"[38] B. Gedik and L. Liu, \u201cLocation privacy in mobile systems: A personalized anonymization model,\u201d in Proc. of ICDCS, pp. 620\u2013629, IEEE, 2005.","key":"2021040701551520377_j_popets-2017-0051_ref_038_w2aab3b7c16b1b6b1ab1ac38Aa","DOI":"10.1109\/ICDCS.2005.48"},{"unstructured":"[39] K. Chatzikokolakis, M. E. Andr\u00e9s, N. E. Bordenabe, and C. Palamidessi, \u201cBroadening the scope of Differential Privacy using metrics,\u201d in Proc. of PETS, vol. 7981 of LNCS, pp. 82\u2013102, Springer, 2013.","key":"2021040701551520377_j_popets-2017-0051_ref_039_w2aab3b7c16b1b6b1ab1ac39Aa"},{"doi-asserted-by":"crossref","unstructured":"[40] C. Dwork, A. Roth, et al., \u201cThe algorithmic foundations of differential privacy,\u201d Foundations and Trends\u00ae in Theor. Comp. Sci., vol. 9, no. 3\u20134, pp. 211\u2013407, 2014.","key":"2021040701551520377_j_popets-2017-0051_ref_040_w2aab3b7c16b1b6b1ab1ac40Aa","DOI":"10.1561\/0400000042"},{"doi-asserted-by":"crossref","unstructured":"[41] L. Cooper and I. Katz, \u201cThe weber problem revisited,\u201d Computers & Mathematics with Applications, vol. 7, no. 3, pp. 225 \u2013 234, 1981.10.1016\/0898-1221(81)90082-1","key":"2021040701551520377_j_popets-2017-0051_ref_041_w2aab3b7c16b1b6b1ab1ac41Aa","DOI":"10.1016\/0898-1221(81)90082-1"},{"unstructured":"[42] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, \u201cOur data, ourselves: Privacy via distributed noise generation,\u201d in Proc. of EUROCRYPT, vol. 4004 of LNCS, pp. 486\u2013503, Springer, 2006.","key":"2021040701551520377_j_popets-2017-0051_ref_042_w2aab3b7c16b1b6b1ab1ac42Aa"},{"doi-asserted-by":"crossref","unstructured":"[43] R. Shokri, G. Theodorakopoulos, J.-Y. L. Boudec, and J.-P. Hubaux, \u201cQuantifying location privacy,\u201d in Proc. of S&P, pp. 247\u2013262, IEEE, 2011.","key":"2021040701551520377_j_popets-2017-0051_ref_043_w2aab3b7c16b1b6b1ab1ac43Aa","DOI":"10.1109\/SP.2011.18"},{"unstructured":"[44] K. Chatzikokolakis, C. Palamidessi, and M. Stronati, \u201cA predictive differentially-private mechanism for mobility traces,\u201d in Proc. of PETS, vol. 8555 of LNCS, pp. 21\u201341, Springer, 2014.","key":"2021040701551520377_j_popets-2017-0051_ref_044_w2aab3b7c16b1b6b1ab1ac44Aa"}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/popets\/2017\/4\/article-p308.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/popets-2017-0051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T14:50:36Z","timestamp":1750949436000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2017\/popets-2017-0051.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,1]]},"references-count":44,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,10,10]]},"published-print":{"date-parts":[[2017,10,1]]}},"alternative-id":["10.1515\/popets-2017-0051"],"URL":"https:\/\/doi.org\/10.1515\/popets-2017-0051","relation":{},"ISSN":["2299-0984"],"issn-type":[{"type":"electronic","value":"2299-0984"}],"subject":[],"published":{"date-parts":[[2017,10,1]]}}}