Enhancing Privacy in Profile-Based Ad Targeting Strategies
Explore the nuances of privacy in profile-based ad targeting, including user-profile targeting methods, examples of targeted advertising, and strategies for protecting sensitive information through the use of noise perturbation techniques.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Privacy of profile-based ad targeting Alexander Smal and Ilya Mironov
2 Privacy of profile-based targeting User-profile targeting Goal: increase impact of your ads by targeting a group potentially interested in your product. Examples: Social Network Profile = user s personal information + friends Search Engine Profile = search queries + webpages visited by user
3 Privacy of profile-based targeting Facebook ad targeting
4 Privacy of profile-based targeting Characters Advertising company Privacy researcher My system is private!
5 Privacy of profile-based targeting Simple attack [Korolova 10] Amazing cat food for $0.99! Nice! - 32 y.o. single man - Mountain View, CA . - has cat - likes fishing Targeted ad Likes fishing noise Show Jon # of impressions Public: - 32 y.o. single man - Mountain View, CA - . - has cat Eve Private: - likes fishing
6 Privacy of profile-based targeting Advertising company Privacy researcher My system is private! Unless your targeting is not private, it is not! How can I target privately?
7 Privacy of profile-based targeting How to protect information? Basic idea: add some noise Explicitly Implicit in the data noiseless privacy [BBGLT11] natural privacy [BD11] Two types of explicit noise Output perturbation Dynamically add noise to answers Input perturbation Modify the database
8 Privacy of profile-based targeting Advertising company Privacy researcher I like input perturbation better
9 Privacy of profile-based targeting Input perturbation Pro: Pan-private (not storing initial data) Do it once Simpler architecture
10 Privacy of profile-based targeting Advertising company Privacy researcher I like input perturbation better Signal is sparse and non-random
11 Privacy of profile-based targeting Adding noise Two main difficulties in adding noise: Sparse profiles Dependent bits 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 differential privacy Smart noise deniability
12 Privacy of profile-based targeting Advertising company Privacy researcher I like input perturbation better Signal is sparse and non-random Let s shoot for deniability, and add smart noise !
13 Privacy of profile-based targeting Smart noise Consider two extreme cases All bits are independent independent noise All bits are correlated with correlation coefficient 1 correlated noise Aha! Smart noise hypothesis: If we know the exact model we can add right noise
14 Privacy of profile-based targeting Dependent bits in real data Netflix prize competition data ~480k users, ~18k movies, ~100m ratings Estimate movie-to-movie correlation Fact that a user rated a movie Visualize graph of correlations Edge correlation with correlation coefficient > 0.5
15 Privacy of profile-based targeting Netflix movie correlations
16 Privacy of profile-based targeting Advertising company Privacy researcher Let s shoot for deniability, and add smart noise ! Let s construct models where smart noise fails
17 Privacy of profile-based targeting How can smart noise fail? large large = relative distance (1)
18 Privacy of profile-based targeting Models of user profiles ? hidden bits 1 0 1 0 1 ? hidden independent bits ? public bits ? ? public bits 1 1 0 1 0 1 0 1 Public bits are some functions of hidden bits Are users well separated?
19 Privacy of profile-based targeting Error-correcting codes Constant relative distance Unique decoding Explicit, efficient
20 Privacy of profile-based targeting Advertising company Privacy researcher See unless the noise is >25%, no privacy But this model is unrealistic! Let me see what I can do with monotone functions
21 Privacy of profile-based targeting Monotone functions Monotone function: for all ? and for all values of ??, ? ? ?(?1, ,?? 1,1,??+1, ,??) ?(?1, ,?? 1,0,??+1, ,??) Monotonicity is a natural property ????? ?????? ????? ??????? + ????? ??????? ???? ?????? Monotone functions are bad for constructing error- correcting codes
22 Privacy of profile-based targeting Approximate error-correcting codes ?-approximate error-correcting code with distance ?: function ?: 0,1? 0,1? ?,? , such that ? ? ? ? ? ? 1 ??: 1 ??. If less than ? fraction of ?(?) is corrupted then we can reconstruct ? within ? fraction of bits. We need ?(1)-approximate error-correcting code with constant distance. blatant non- privacy
23 Privacy of profile-based targeting Noise sensitivity Noise sensitivity of function ?: NS?? = ???? ? ? ? , where ? is chosen uniformly at random, ? is formed by flipping each bit of ? with probability ?. ? hidden bits 1 1 0 1 1 1 0 0 1 0 If NS?? is big ? ? public bits 1 1 1 0 0 0 1 0 0 1 1 1 0 1 1 1 ? hidden bits 1 1 0 1 1 1 0 0 1 0 If NS?? is small ? ? public bits 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1
24 Privacy of profile-based targeting Monotone functions There exist highly sensitive monotone functions [MO 03]. Theorem: there exists monotone ? 1 -approximate error- correcting code with constant distance on average. Idea of proof: Let ?1,?2, ,?? be random independent monotone boolean functions, such that NS??? ? and ?? depends only on ? ? bits of ?. Let ? ? = ?1? , ,??? . With high probability for random ? there is no ? such that ? ? 1 ?? 1 ?? and ? ? ? ? For Talagrand ? 1/ ? -approximate error-correcting code with constant distance on average. 2.
25 Privacy of profile-based targeting Advertising company Privacy researcher If the model is monotone, blatant non-privacy is still possible Hmmm. Does smart noise ever work?
26 Privacy of profile-based targeting Linear threshold model Function ?: 1,1? 0,1 is a linear threshold function, if there exist real numbers ?? s such that ? ? = sgn ?0+ ?1?1+ + ????. Theorem[Peres 04]: Let ? be a linear threshold function, then NS?? 2 ?. No o(1)-approximate error-correcting code with O(1) distance
27 Privacy of profile-based targeting Conclusion Two separate issues with input perturbation: Sparseness Dependencies Smart noise hypothesis: Even for a publicly known, relatively simple model, constant corruption of profiles may lead to blatant non-privacy. Connection between noise sensitivity of boolean functions and privacy Open questions: Linear threshold privacy-preserving mechanism? Existence of interactive privacy-preserving solutions? Arbitrary Monotone Linear threshold fallacy
28 Privacy of profile-based targeting Thank for your attention! Special thanks for Cynthia Dwork, Moises Goldszmidt, Parikshit Gopalan, Frank McSherry, Moni Naor, Kunal Talwar, and Sergey Yekhanin.
