Privacy amplification by shuffling
This research delves into privacy amplification through shuffling techniques, exploring how Vitaly Feldman, Ulfar Erlingsson, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta contribute to the field. The study focuses on enhancing privacy measures by shuffling, providing insights that can bolster data protection strategies.
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 amplification by shuffling Vitaly Feldman Ulfar Erlingsson Ilya Mironov Ananth Raghunathan Kunal Talwar Abhradeep Thakurta
Local Differential Privacy (LDP) ?1 ?1 For all ?, ?? is a local ?-DP randomizer: for all ?,? ? ?2 ?2 ?3 ?3 Server ??(??= ?) ??(??= ? ) [Warner 65; EGS 03; KLNRS 08] ?? ?? Compute (approximately) ?(?1,?2, ,??)
Encode-Shuffle-Analyze (ESA) [Bittau et al. 17] ?1 ?1 ?2 ?2 ?3 ?3 Server ?? ?? Shuffler 3
Warm-up: binary randomized response RR: For ? 0,1 , return ? flipped with probability 1/3. Satisfies (log2)-LDP Output distribution is determined by ? = #1(RR(?1), ,RR(??)) ? Bin ?,2 3+ Bin ? ?,1 3, where ? = #1(?1, ,??) For a neighboring dataset: ? = ? 1 Bin ?,2 + Bin ? ?,1 ,? Bin ? + 1,2 + Bin ? ? 1,1 log 1/? ? 3 3 3 3 [DKMMN 06] [Cheu,Smith,Ullman,Zeber,Zhilyaev 19] (independent) 4
Privacy amplification by shuffling For any ? = ?(1) and any sequence of ?-LDP algorithms (?1, ,??), let ?shuffle?1, ,?? = ?1?? 1 ,?2?? 2 , ,???? ? for a random and uniform permutation ?: ? ? ? log 1/? Then ?shuffle is ? ,? -DP in the central model for ? = ? ? Holds for adaptive case: ??may depend on outputs of ?1, ,?? 1 Generalizes to ?-DP algorithms on disjoint subsets of data 5
Implications for ESA ?1 ?1 ?2 ?2 Set ? [?] with the same randomizer ?3 ?3 Server ?? ?? Shuffler ? log 1/? For every ? ?, the output is ? ,? -DP for element at position ? ? 6
Comparison with subsampling Running ?-DP algorithm on random ?-fraction of elements is ??-DP (? 1)[KLNRS 08] Shuffling includes all elements so ? = 1 Output ?1??1,?2??2, ,????? ? log 1/? where ?1,?2, ,?? [?] (independently) is ? ,? -DP for ? = ? ? e.g. [BST 14] Advantages of shuffling: does not affect the statistics of the dataset does not increase LDP cost 7
Online monitoring time ??,? {0,1} ?1,1 ?1,2 ?1,3 ?1,? Status of user ? on day ? ?2,1 ?2,2 ?2,3 ?2,? Assume that each user s status changes at most ? times only for utility ?3,1 ?3,2 ?3,3 ?3,? ??,1 ??,2 ??,3 ??,? ?? ?1 ?2 ?3 Estimate the daily counts ??= ?=1 ??,? for all ? [?] ? 9
Monitoring with LDP There exists an ?-LDP algorithm that constructs estimates ?1, ?2, , ??such that with high prob. for all ? [?], ??(log?)2 ? ?(log?)2 log 1/? ?? ?? = ? = ? ???????? Report the status changes (only first ?) Maintains a tree of counters each over an interval of time Based on [DNPR 10; CSS 11] 10
Conclusions General privacy amplification technique o For some problems achieves state of the art in the central model o Can be used to derive lower bounds for LDP Provable benefits of anonymity for ESA-like architectures Same algorithm, different attack/trust models 11
