Successive Refinement of Privacy. Girgis, A. M, Data, D., Chaudhuri, K., Fragouli, C., & Diggavi, S. IEEE Journal on Selected Areas in Information Theory (JSAIT), 1(3):745-759, 2020. ![Successive Refinement of Privacy [link]](https://bibbase.org/img/filetypes/link.svg "link")
Arxiv doi abstract bibtex 2 downloads This work examines a novel question: how much randomness is needed to achieve local differential privacy (LDP)? A motivating scenario is providing \em multiple levels of privacy to multiple analysts, either for distribution or for heavy-hitter estimation, using the \emphsame (randomized) output. We call this setting \emphsuccessive refinement of privacy, as it provides hierarchical access to the raw data with different privacy levels. For example, the same randomized output could enable one analyst to reconstruct the input, while another can only estimate the distribution subject to LDP requirements. This extends the classical Shannon (wiretap) security setting to local differential privacy. We provide (order-wise) tight characterizations of privacy-utility-randomness trade-offs in several cases for distribution estimation, including the standard LDP setting under a randomness constraint. We also provide a non-trivial privacy mechanism for multi-level privacy. Furthermore, we show that we cannot reuse random keys over time while preserving privacy of each user.
@article{girgis2020successive,
abstract = {This work examines a novel question: how much randomness is needed to achieve local differential privacy (LDP)? A motivating scenario is providing {\em multiple levels of privacy} to multiple analysts, either for distribution or for heavy-hitter estimation, using the \emph{same} (randomized) output. We call this setting \emph{successive refinement of privacy}, as it provides hierarchical access to the raw data with different privacy levels. For example, the same randomized output could enable one analyst to reconstruct the input, while another can only estimate the distribution subject to LDP requirements. This extends the classical Shannon (wiretap) security setting to local differential privacy. We provide (order-wise) tight characterizations of privacy-utility-randomness trade-offs in several cases for distribution estimation, including the standard LDP setting under a randomness constraint. We also provide a non-trivial privacy mechanism for multi-level privacy. Furthermore, we show that we cannot reuse random keys over time while preserving privacy of each user.},
author = {Girgis, Antonious M and Data, Deepesh and Chaudhuri, Kamalika and Fragouli, Christina and Diggavi, Suhas},
journal = {IEEE Journal on Selected Areas in Information Theory (JSAIT)},
tags = {journal,DML,PDL},
title = {Successive Refinement of Privacy},
type = {2},
url_arxiv = {https://arxiv.org/abs/2005.11651},
year = {2020},
doi={10.1109/JSAIT.2020.3040403},
volume={1},
number={3},
pages={745-759},
}
Downloads: 2
{"_id":"FCxHB7zvdce8JemBG","bibbaseid":"girgis-data-chaudhuri-fragouli-diggavi-successiverefinementofprivacy-2020","author_short":["Girgis, A. M","Data, D.","Chaudhuri, K.","Fragouli, C.","Diggavi, S."],"bibdata":{"bibtype":"article","type":"2","abstract":"This work examines a novel question: how much randomness is needed to achieve local differential privacy (LDP)? A motivating scenario is providing \\em multiple levels of privacy to multiple analysts, either for distribution or for heavy-hitter estimation, using the \\emphsame (randomized) output. We call this setting \\emphsuccessive refinement of privacy, as it provides hierarchical access to the raw data with different privacy levels. For example, the same randomized output could enable one analyst to reconstruct the input, while another can only estimate the distribution subject to LDP requirements. This extends the classical Shannon (wiretap) security setting to local differential privacy. We provide (order-wise) tight characterizations of privacy-utility-randomness trade-offs in several cases for distribution estimation, including the standard LDP setting under a randomness constraint. We also provide a non-trivial privacy mechanism for multi-level privacy. Furthermore, we show that we cannot reuse random keys over time while preserving privacy of each user.","author":[{"propositions":[],"lastnames":["Girgis"],"firstnames":["Antonious","M"],"suffixes":[]},{"propositions":[],"lastnames":["Data"],"firstnames":["Deepesh"],"suffixes":[]},{"propositions":[],"lastnames":["Chaudhuri"],"firstnames":["Kamalika"],"suffixes":[]},{"propositions":[],"lastnames":["Fragouli"],"firstnames":["Christina"],"suffixes":[]},{"propositions":[],"lastnames":["Diggavi"],"firstnames":["Suhas"],"suffixes":[]}],"journal":"IEEE Journal on Selected Areas in Information Theory (JSAIT)","tags":"journal,DML,PDL","title":"Successive Refinement of Privacy","url_arxiv":"https://arxiv.org/abs/2005.11651","year":"2020","doi":"10.1109/JSAIT.2020.3040403","volume":"1","number":"3","pages":"745-759","bibtex":"@article{girgis2020successive,\n abstract = {This work examines a novel question: how much randomness is needed to achieve local differential privacy (LDP)? A motivating scenario is providing {\\em multiple levels of privacy} to multiple analysts, either for distribution or for heavy-hitter estimation, using the \\emph{same} (randomized) output. We call this setting \\emph{successive refinement of privacy}, as it provides hierarchical access to the raw data with different privacy levels. For example, the same randomized output could enable one analyst to reconstruct the input, while another can only estimate the distribution subject to LDP requirements. This extends the classical Shannon (wiretap) security setting to local differential privacy. We provide (order-wise) tight characterizations of privacy-utility-randomness trade-offs in several cases for distribution estimation, including the standard LDP setting under a randomness constraint. We also provide a non-trivial privacy mechanism for multi-level privacy. Furthermore, we show that we cannot reuse random keys over time while preserving privacy of each user.},\n author = {Girgis, Antonious M and Data, Deepesh and Chaudhuri, Kamalika and Fragouli, Christina and Diggavi, Suhas},\n journal = {IEEE Journal on Selected Areas in Information Theory (JSAIT)},\n tags = {journal,DML,PDL},\n title = {Successive Refinement of Privacy},\n type = {2},\n url_arxiv = {https://arxiv.org/abs/2005.11651},\n year = {2020},\n doi={10.1109/JSAIT.2020.3040403},\n volume={1},\n number={3},\n pages={745-759},\n}\n\n","author_short":["Girgis, A. M","Data, D.","Chaudhuri, K.","Fragouli, C.","Diggavi, S."],"key":"girgis2020successive","id":"girgis2020successive","bibbaseid":"girgis-data-chaudhuri-fragouli-diggavi-successiverefinementofprivacy-2020","role":"author","urls":{" arxiv":"https://arxiv.org/abs/2005.11651"},"metadata":{"authorlinks":{}},"downloads":2},"bibtype":"article","biburl":"https://bibbase.org/network/files/e2kjGxYgtBo8SWSbC","dataSources":["xHWpCrSGkLBjtz7P2","hicKnsKYNEFXC4CgH","jxCYzXXYRqw2fiEXQ","wCByFFrQMyRwfzrJ6","yuqM5ah4HMsTyDrMa","YaM87hGQiepg5qijZ","n9wmfkt5w8CPqCepg","soj2cS6PgG8NPmWGr","FaDBDiyFAJY5pL28h","ycfdiwWPzC2rE6H77","2BHqTGHtDg7BjRAJQ","XpqzCLvCgsYBqbTpK","QNNZyNQzfeETJyTbL","Z6bBhKezwKd3pPWRc"],"keywords":[],"search_terms":["successive","refinement","privacy","girgis","data","chaudhuri","fragouli","diggavi"],"title":"Successive Refinement of Privacy","year":2020,"downloads":2}