Candidacy - Columbia University

Candidacy - Columbia University

CANDIDACY EXAM TOPIC: PRIVACY IN LOCATION BASED SERVICES Wonsang Song Columbia University AGENDA Introduction of LBS Threats to location privacy Privacy protection techniques

Conclusion WHAT IS LBS? Location service, location-aware service, location-based service * A. Brimicombe. GIS Where are the frontiers now? GIS, 2002. * S. Steiniger, M. Neun, and A. Edwards. Foundations of Location Based Services. Lecture Notes on LBS, 2006. LBS APPLICATIONS LBS Applications Information Service POI

Advertising - Yellow page - SMS alert - Restaurant search - Target marketing Tracking Service Navigatio Navigatio n n - Car navigation - Geocaching Emergenc Emergenc y y - 9-1-1

call People / Vehicle Tracking -Children monitoring - Fleet management Tolling - Highway tolling (GPS-based) LOCATION PRIVACY Location privacy the ability to prevent other parties from learning ones current or past location - Beresford and Stajano Critical in context

Location + time + identity Why important? Physical security Location tells more. THREATS TO LOCATION PRIVACY Revealing identity Pseudonymity is not enough. Inference attack1)

Tracking and predicting movement Collecting LBS queries to track location Data mining2) And more More privacy-sensitive information e.g., medical condition, political/religious affiliation Linkage attack 1) J. Krumm. Inference Attacks on Location Tracks. Pervasive, 2007. 2) Y. Ye, Y. Zheng, Y. Chen, J. Feng, X. Xie. Mining Individual Life Pattern Based on Location History. MDM, 2009. CHALLENGES IN LBS Balance between convenience and privacy

To prevent improper or unauthorized use of location Gathering location without notice or users consent Using location beyond the permission Reidentification and tracking SOLUTIONS FOR LOCATION PRIVACY Policy-based Solutions Anonymity-based solutions PIR-based solutions SOLUTIONS FOR LOCATION PRIVACY Policy-based Solutions Anonymity-based solutions PIR-based solutions

W3C GEOLOCATION API Scripting API for device location getCurrentPosition(): one-shot location watchPosition() / clearWatch(): start/stop repeated position update Implementations Firefox 3.5+, Google Chrome, IE 7 with Google Gears Google location service (IP, Wi-Fi fingerprint) Mobile Safari in iPhone

Wi-Fi (Skyhook), cellular, GPS * Geolocation API Specification. W3C, 2009. * N. Doty, D. Mulligan, E. Wilde. Privacy Issues of the W3C Geolocation API. UC Berkeley: School of Information. Report 2010-038, 2010. W3C GEOLOCATION PRIVACY REQUIREMENT User Agents Send with permission Express permission Persistent permission Recipients Request when necessary Use for the task

Dont retain without permission Dont retransmit without permission Disclose privacy practices ? e.g., purpose, duration, storage security Allow revocation Allow prearranged trust relationship e.g., 9-1-1

* Geolocation API Specification. W3C, 2009. * N. Doty, D. Mulligan, E. Wilde. Privacy Issues of the W3C Geolocation API. UC Berkeley: School of Information. Report 2010-038, 2010. IETF GEOPRIV ARCHITECTURE Providing standard mechanism for Transmission of location Privacy-preserving Protocol independent Basic architecture Binding rules to data LO = location + privacy rule Conveying users

preference with location * R. Barnes, M. Lepinski, A. Cooper, J. Morris, H. Tschofenig, H. Schulzrinne. An Architecture for Location and Location Privacy in Internet Applications. IETF Internet Draft, 2009. IETF GEOPRIV ARCHITECTURE Privacy rule Basic ruleset e.g., retransmission-allowed, retention-expiry, Enhanced ruleset Rule set = list of rules Rule = condition + action + transformation

Default-deny, adding permission only Privacy paradigm Decision maker: recipient user Non-technical forces can enforce it. * H. Schulzrinne, H. Tschofenig, J. Morris, J. Cuellar, J. Polk, J. Rosenberg. Common Policy: A Document Format for Expressing Privacy Preferences. RFC 4745, 2007. * H. Schulzrinne, H. Tschofenig, J. Morris, J. Cuellar, J. Polk. Geolocation Policy: A Document Format for Expressing Privacy Preferences for Location Information. IETF Internet Draft, 2009. POLICY-BASED SOLUTIONS + W3C Geolocation IETF Geopriv

Applicable service Information / Tracking Information / Tracking Target application Web-based service Generic service Creator of privacy policy Recipients (web sites) Users Role of users Grant permission

Set privacy ruleset Supporting location type Geodetic Civic and Geodetic Needs trusted 3rd party No Yes (location server) Needs non-technical enforcement Yes Yes SOLUTIONS FOR LOCATION PRIVACY Policy-based Solutions

Anonymity-based solutions PIR-based solutions ANONYMITY-BASED SOLUTIONS Anonymity and anonymity set the state of being not identifiable within a set of subjects, the anonymity set* anonymity set anonymity Anonymize data before collection * A. Pfitzmann, Marit Kohntopp. Anonymity, Unobservability, and Pseudonymity - A Proposal for Terminology. LNCS, 2001.

MIX ZONE Middleware architecture Users register/sending location to the proxy. Proxy sends/receives queries to/from LBS providers. Solution Mix zone Changing pseudonym in the mix zone Not sending queries in the mix zone Adversary cannot link what are going into and what are coming

out. p1 p2 p3 Mix Zone p2 p3 p1 * A. Beresford, F. Stajano. Location Privacy in Pervasive Computing. IEEE Pervasive Computing, 2003. MIX ZONE Limitations Need to trust the proxy

Single point of failure Need enough users Size of anonymity set = # of users in the mix zone at the time Cannot preserve users reputation at LBS providers Same as services without any pseudonym K-ANONYMITY Location k-anonymity Iff location of the subject is indistinguishable from location of at least k - 1 other subjects. Pr = 1 / k

Middleware architecture * M. F. Mokbel, C. Chow, W. G. Aref. The new Casper: query processing for location services without compromising privacy. VLDB, 2006. CLOAKING ALGORITHM Input: location of all users kmin: desired minimum anonymity Output: quadrant containing k users kmin = 3 * M. Gruteser, D. Grunwald. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. MobiSys, 2003.

CASPER: QUERY PROCESSING Privacy-aware query processor Embedded in the LBS provider Deals with cloaked spatial area Input: cloaked spatial region + search parameters Output: candidate list inclusive and minimal * M. F. Mokbel, C. Chow, W. G. Aref. The new Casper: query processing for location services without compromising privacy. VLDB, 2006. USING DUMMIES Drawbacks of k-anonymity

Needs at least k - 1 users nearby Needs to trust 3rd party Client sends false location with true location Dummy generation algorithm How realistic? Just random? Moving in neighborhood Location of dummy = previous loc margin * H. Kido, Y. Yanagisawa, T. Satoh. An anonymous communication technique using dummies for location-based services. ICPS, 2005. ANONYMITY-BASED SOLUTIONS +

Mix-zone k-anonymity Using dummies Applicable service Information Information Information service with userid Target of obfuscation pseudonym location

location Possibility of failure Yes Yes No Necessity of trusted Yes 3rd party Yes No Security risk High High

Low Waste of resource No No Yes Privacy risk Sender address is not revealed. Sender address is not revealed. Sender address can be revealed.

Re-identification is possible but in very limited area. Re-identification is not possible. Re-identification is possible.* Location tracking is not possible. Location tracking is not possible. Location tracking is not possible. SOLUTIONS FOR LOCATION PRIVACY Policy-based Solutions

Anonymity-based solutions PIR-based solutions WHAT IS PRIVATE INFORMATION RETRIEVAL? Problem DB: n bits, (X1, X2, , Xn) Client: wants Xi Requirement Privacy: Server does not learn i. Maybe: Client learns nothing more than X i. * E. Kushilevitz, R. Ostrovsky. Replication Is Not Needed: Single Database, Computationally-Private

Information Retrieval. FOCS, 1997. SPIRAL: HARDWARE-BASED PIR Hardware-based PIR Secure coprocessor Push trusted entity to LBS provider Preprocessing generates , shuffles DB into DB, and encrypts DB written back encrypted DB to the server

DB = {o1, o2, o3} DB = {o3, o1, o2} = {2, 3, 1} DB[i] = DB[[i]] Online query processing gets encrypted query, and decrypts it performs query returns encrypted result * A. Khoshgozaran, H. Shirani-Mehr, C. Shahibi. SPIRAL:A Scalable Private Information Retrieval Approach to Location Privacy. PALMS, 2008. COMPUTATIONAL PIR Quadratic Residuosity Assumption

x2 a (mod N), for some x, then a is QR mod N e.g., 12 = 1 1 (mod 7) 22 = 4 4 (mod 7) 32 = 9 2 (mod 7) 42 = 16 2 (mod 7) 52 = 25 4 (mod 7) 62 = 36 1 (mod 7) QR predicate QN (i.e., a function to determine a given number is QR mod N) is assumed to be super-polynomial when N = pq, p and q are two primes. Procedure of cPIR

Client sends a random vector y satisfying QN(yi) = false, QN(yji) = true. Server produces and sends back a vector z out of y and the database x using a matrix operation f: z = f (x, y) Client can determine xi if zi QR mod N, xi = 0 zi QR mod N, xi = 1 * G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, K. Tan. Private queries in location based services: anonymizers are not necessary. SIGMOD, 2008. HOW TO APPLY PIR TO LBS? 2D -> 1D Converts

spatial query to PIR using grid structure. Shares grid with users. * A. Khoshgozaran, H. Shirani-Mehr, C. Shahibi. SPIRAL:A Scalable Private Information Retrieval Approach to Location Privacy. PALMS, 2008. * G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, K. Tan. Private queries in location based services: anonymizers are not necessary. SIGMOD, 2008. COMPUTATIONAL PIR Pros No information is revealed to LBS provider. No 3rd party is necessary.

Cons Communication PIR: 2MB (N = 768bits) k-anonymity: 8KB (16K users, k = 50) Overhead cost in server CPU 6sec (N = 768bits, P4 3.0GHz) * G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, K. Tan. Private queries in location based services: anonymizers are not necessary. SIGMOD, 2008.

Policy-based Applicable services Information, Tracking Anonymitybased PIR-based Information Information Requirement for High safeguard Low Low

Needs nontechnical enforcement Yes No No Trusted entity Service provider Anonymizer Hardware maker Cryptography Privacy guarantee

Low High Very high System overhead Low Mid High CONCLUSION Location privacy threats Re-identification Tracking

and prediction Linkage attack Solutions Policy-based solutions Anonymity-based solutions PIR-based Solutions BACKUP SLIDES POSITIONING GPS Radio magnetic wave Unidirectional: only satellite to receiver Endpoint-based: Privacy protected since device

only knows its location Active Badge (indoors) Network-based: Infrastructure knows all users location Cricket (indoors) RF + Infra Red Endpoint-based: Privacy protected INFERENCE ATTACK Goal: Inferring a persons identity from location track Experiment and result

Phase 1 Collecting Location GPS receivers on the cars 172 individuals during 2 weeks Phase 2 Finding Home Coordinates Four algorithms - Last destination - Dwell time - Largest cluster - Best time Median error: 60.7m Problems Inaccuracy of GPS Subject behavior

Parking location home Multi-unit building Inaccuracy of phone book 33% success with known data * J. Krumm. Inference Attacks on Location Tracks. Pervasive, 2007. Phase 3 Identifying Subject Lookup phone book to get the name Success: 5.2%

MINING INDIVIDUAL LIFE PATTERN Goal: Discover ones general life style and regularity from location history LP-Mine framework Modeling phase GPS data stay point sequence location history sequence 30 min 200 m Find out significant places while ignoring transition

Mining phase Result: (P, s) * Y. Ye, Y. Zheng, Y. Chen, J. Feng, X. Xie. Mining Individual Life Pattern Based on Location History. MDM, 2009. MINING INDIVIDUAL LIFE PATTERN Objective experiment Divides GPS data into two One for creating pattern

The other for applying pattern to predict Result * Y. Ye, Y. Zheng, Y. Chen, J. Feng, X. Xie. Mining Individual Life Pattern Based on Location History. MDM, 2009. PSEUDONYM AND ANONYMITY Anonymity is increased Less often pseudonym is used More often pseudonym is changed * A. Pfitzmann, Marit Kohntopp. "Anonymity, Unobservability, and Pseudonymity - A Proposal for Terminology". LNCS, 2001. CUSTOMIZABLE K-ANONYMITY

Customizable framework User can set anonymity constraints in each query. Anonymity constraint k: desired minimum anonymity spatial tolerance temporal tolerance MBR of {m1, m2, m4} Clique-Cloak algorithm Input: anonymity constraints Output: smallest cloaking box while satisfying anonymity constraint. Data structures

Constraint graph Expiration heap * B. Gedik, L. Liu. A Customizable k-Anonymity Model for Protecting Location Privacy. ICDCS, 2005. CUSTOMIZABLE K-ANONYMITY Limitations Centralized AS Can fail even with optimal algorithm. Due to non-optimal algorithm Failure Offline computation only NP-complete

Users are on the border of MBR. * B. Gedik, L. Liu. A Customizable k-Anonymity Model for Protecting Location Privacy. ICDCS, 2005. SPATIAL CLOAKING USING P2P Drawbacks of centralized architecture Bottleneck, single point of failure Having entire knowledge is privacy threat when attacked Distributed architecture using P2P Solution

Each mobile user has: Privacy profile (k, Amin): Amin is anonymous requirement, not the tolerance value. Algorithm Peer searching phase: use broadcast, multi-hop is allowed, receive others location and speed Location adjustment phase: consider the movement of peers Spatial cloaking phase: determine minimum area covering itself and k -1 others Selecting agent, forwarding query, and receiving candidate answers * C. Chow, M. F. Mokbel, X. Liu. A peer-to-peer spatial cloaking algorithm for anonymous locationbased service. GIS, 2006.

PRIVE: DISTRIBUTED ANONYMIZATION Distributed architecture HilbASR B+ tree structure grouping users into k-buckets using Hilbert value index key: Hilbert value of location join, departure, relocation, and krequest

Pros and cons No single point of failure Provides more anonymity Cannot determine sender when knowing location of all Generates smaller cloaked spatial regions Needs to trust others Load at root, cluster headers * G. Ghinita, P. Kalnis, S. Skiadopoulos. PRIVE: anonymous location-based queries in distributed mobile systems. WWW, 2007.

CUSTOMIZABLE K-ANONYMITY relative temporal resolution temporal constraint output interval relative spatial resolution area of spatial constraint area of cloaking box K-ANONYMITY Limitations Need to trust AS. Algorithm is not optimal. Tends to return larger area than necessary.

higher processing cost Low population density? How to decide proper k? Might fail to protect privacy. In some user distributions USING DUMMIES Evaluation Ubiquity F: a scale of all regions where users stayF Anonymity Congestion P: number of users in a specific region P Anonymity 1 Uniformity Var(P): the variance of P Var ( P )

Anonymity Shift(P): difference of P in each region, lower Shift(P) means dummies look like real persons Relationship between dummy generation algorithms and shift(P) Relationship between dummy generation algorithms and Var(P) Comparison of location anonymity and number of dummies Cost comparison for request messages mod N} mod N} SCOPE AND ASSUMPTION secure

anonymity channel network LBS user LBS provider

Recently Viewed Presentations

  • OBJ CUT - Massachusetts Institute of Technology

    OBJ CUT - Massachusetts Institute of Technology

    OBJ CUT M. Pawan Kumar Philip Torr Andrew Zisserman Aim Given an image, to segment the object Challenges Motivation Motivation Motivation Motivation Motivation Motivation Our Method Combine object detection with segmentation Borenstein and Ullman, ECCV '02 Leibe and Schiele, BMVC...
  • Chemistry Chapter 5 Review - Mr. Hoover's Science Classes

    Chemistry Chapter 5 Review - Mr. Hoover's Science Classes

    This review is an overview and does not cover specific details. This does not included everything that you may have covered and may include things you did not cover. Study Tips. Review and correct old tests. Try rewriting them. ......
  • AES022 - Fermilab

    AES022 - Fermilab

    Tested at Fermilab and Jlab with comparable results (see next) ... TTC 2019 Triumf. Also see Anna's talk on High gradient R&D - thanks to Anna, Sam and Daniel . FNAL sent cavity AES-022 to Jlab under vacuum for RF...
  • An Intervention to Reduce Boils in Rural Alaska

    An Intervention to Reduce Boils in Rural Alaska

    An Intervention to Reduce Boilsin Rural Alaska. Ian Plumb, MBBS, MSc. Epidemic Intelligence Service Officer. Arctic Investigations Program. 6th Annual Water and Sanitation Innovations for the Arctic
  • P1 - Describe the Structure & Function of the Skeletal System

    P1 - Describe the Structure & Function of the Skeletal System

    Radius - forearm. thumb side. moves around ulna when turning hand. Carpals - 8 short bones. wrist. 2 rows of 4. Metacarpals - 5 long bones . palm of the hand. run from the carpals to each finger & thumb
  • Methods Panel @ Persuasive 2019

    Methods Panel @ Persuasive 2019

    Assistant professor, Persuasive Design and Applied ethics, Head of Center for Computational Thinking. Regular participant at Persuasive Technology since 2008. Qualitative research methods, User centred design approaches, Participatory design, Persuasion in classical rhetoric
  • Effective Teaching in Diverse Classrooms Lorraine Conroy, Susan

    Effective Teaching in Diverse Classrooms Lorraine Conroy, Susan

    Diversity. US: Racial and ethnic minority population doubled 1970-2016. Will represent more than 50% by 20421. Racial and ethnic minorities remain underrepresented (URM) in higher education, including public health
  • Unit D - Living Systems Chapter 1 The biosphere of Life

    Unit D - Living Systems Chapter 1 The biosphere of Life

    Unit D - Living Systems Chapter 1 The biosphere of Life Section 1.4 Conducting a field study Summary of Terms Field Study Purpose of a Field Study Purpose: to examine abiotic and biotic factors to collect qualitative and quantitative data...