{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/92686"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/92686","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The fundamental limits of statistical data privacy","abstract":"The Internet is shaping our daily lives. On the one hand, social networks like Facebook and Twitter allow people to share their precious moments and opinions with virtually anyone around the world. On the other, services like Google, Netflix, and Amazon allow people to look up information, watch movies, and shop online anytime, anywhere. However, with this unprecedented level of connectivity comes the danger of being monitored. There is an increasing tension between the need to share data and the need to preserve the privacy of Internet users. The need for privacy appears in three main contexts: (1) the global privacy context, as in when private companies and public institutions release personal information about individuals to the public; (2) the local privacy context, as in when individuals disclose their personal information with potentially malicious service providers; (3) the multi-party privacy context, as in when different parties cooperate to interactively compute a function that is defined over all the parties' data. Differential privacy has recently surfaced as a strong measure of privacy in all three contexts. Under differential privacy, privacy is achieved by randomizing the data before releasing it. This leads to a fundamental tradeoff between privacy and utility. In this thesis, we take a concrete step towards understanding the fundamental structure of privacy mechanisms that achieve the best privacy-utility tradeoff. This tradeoff is formulated as a constrained optimization problem: maximize utility subject to differential privacy constraints. We show, perhaps surprisingly, that in all three privacy contexts, the optimal privacy mechanisms have the same combinatorial staircase structure. This deep result is a direct consequence of the geometry of the constraints imposed by differential privacy on the privatization mechanisms.","abstract_html":"The Internet is shaping our daily lives. On the one hand, social networks like Facebook and Twitter allow people to share their precious moments and opinions with virtually anyone around the world. On the other, services like Google, Netflix, and Amazon allow people to look up information, watch movies, and shop online anytime, anywhere. However, with this unprecedented level of connectivity comes the danger of being monitored. There is an increasing tension between the need to share data and the need to preserve the privacy of Internet users. The need for privacy appears in three main contexts: (1) the global privacy context, as in when private companies and public institutions release personal information about individuals to the public; (2) the local privacy context, as in when individuals disclose their personal information with potentially malicious service providers; (3) the multi-party privacy context, as in when different parties cooperate to interactively compute a function that is defined over all the parties' data. Differential privacy has recently surfaced as a strong measure of privacy in all three contexts. Under differential privacy, privacy is achieved by randomizing the data before releasing it. This leads to a fundamental tradeoff between privacy and utility. In this thesis, we take a concrete step towards understanding the fundamental structure of privacy mechanisms that achieve the best privacy-utility tradeoff. This tradeoff is formulated as a constrained optimization problem: maximize utility subject to differential privacy constraints. We show, perhaps surprisingly, that in all three privacy contexts, the optimal privacy mechanisms have the same combinatorial staircase structure. This deep result is a direct consequence of the geometry of the constraints imposed by differential privacy on the privatization mechanisms.","abstract_has_math":false,"creators":["Kairouz, Peter"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Viswanath, Pramod","Oh, Sewoong","Hajek, Bruce","Borisov, Nikita","Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-11-10T17:49:18Z","date_published":"2016-11-10T17:49:18Z","updated_at":"2026-07-22T22:26:35Z","subjects":["Privacy","Information Theory","Data Privacy","Statistics","Multi-Party Computation","Security","Local Differential Privacy","Privacy-Preserving Machine Learning Algorithms","Information Theoretic Utilities","f-Divergence","Mutual Information","Statistical Inference","Hypothesis Testing","Estimation"],"languages":["en"],"rights":["Copyright © 2016 by Peter Kairouz"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/92686","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Viswanath, Pramod","Oh, Sewoong","Hajek, Bruce","Borisov, Nikita","Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Kairouz, Peter"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-11-10T17:49:18Z","2016-04-20","2016-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Privacy","Information Theory","Data Privacy","Statistics","Multi-Party Computation","Security","Local Differential Privacy","Privacy-Preserving Machine Learning Algorithms","Information Theoretic Utilities","f-Divergence","Mutual Information","Statistical Inference","Hypothesis Testing","Estimation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright © 2016 by Peter Kairouz"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/92686"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The Internet is shaping our daily lives. On the one hand, social networks like Facebook and Twitter allow people to share their precious moments and opinions with virtually anyone around the world. On the other, services like Google, Netflix, and Amazon allow people to look up information, watch movies, and shop online anytime, anywhere. However, with this unprecedented level of connectivity comes the danger of being monitored. There is an increasing tension between the need to share data and the need to preserve the privacy of Internet users. The need for privacy appears in three main contexts: (1) the global privacy context, as in when private companies and public institutions release personal information about individuals to the public; (2) the local privacy context, as in when individuals disclose their personal information with potentially malicious service providers; (3) the multi-party privacy context, as in when different parties cooperate to interactively compute a function that is defined over all the parties' data. Differential privacy has recently surfaced as a strong measure of privacy in all three contexts. Under differential privacy, privacy is achieved by randomizing the data before releasing it. This leads to a fundamental tradeoff between privacy and utility. In this thesis, we take a concrete step towards understanding the fundamental structure of privacy mechanisms that achieve the best privacy-utility tradeoff. This tradeoff is formulated as a constrained optimization problem: maximize utility subject to differential privacy constraints. We show, perhaps surprisingly, that in all three privacy contexts, the optimal privacy mechanisms have the same combinatorial staircase structure. This deep result is a direct consequence of the geometry of the constraints imposed by differential privacy on the privatization mechanisms.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-11-09 without embargo terms","The student, Peter Kairouz, accepted the attached license on 2016-04-19 at 14:12.","The student, Peter Kairouz, submitted this Dissertation for approval on 2016-04-19 at 14:19.","This Dissertation was approved for publication on 2016-04-20 at 16:44.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9341 on 2016-11-09 at 10:19:05","Made available in DSpace on 2016-11-10T17:49:18Z (GMT). No. of bitstreams: 3 KAIROUZ-DISSERTATION-2016.pdf: 5502601 bytes, checksum: 4b6054e2287a29f74af5e94e2e72d614 (MD5) LICENSE.txt: 4210 bytes, checksum: f645d2e47d8e2f13bd8e4f537c41e1f6 (MD5) PROQUEST_LICENSE.txt: 4556 bytes, checksum: 6db5cb25fb30290d63830ecbc3faf01c (MD5) Previous issue date: 2016-04-20"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["The fundamental limits of statistical data privacy"]}]}],"canonical_facts":{"dc:contributor":["Viswanath, Pramod","Oh, Sewoong","Hajek, Bruce","Borisov, Nikita","Srikant, Rayadurgam"],"dc:creator":["Kairouz, Peter"],"dc:date":["2016-11-10T17:49:18Z","2016-04-20","2016-08"],"dc:description":["The Internet is shaping our daily lives. On the one hand, social networks like Facebook and Twitter allow people to share their precious moments and opinions with virtually anyone around the world. On the other, services like Google, Netflix, and Amazon allow people to look up information, watch movies, and shop online anytime, anywhere. However, with this unprecedented level of connectivity comes the danger of being monitored. There is an increasing tension between the need to share data and the need to preserve the privacy of Internet users. The need for privacy appears in three main contexts: (1) the global privacy context, as in when private companies and public institutions release personal information about individuals to the public; (2) the local privacy context, as in when individuals disclose their personal information with potentially malicious service providers; (3) the multi-party privacy context, as in when different parties cooperate to interactively compute a function that is defined over all the parties' data. Differential privacy has recently surfaced as a strong measure of privacy in all three contexts. Under differential privacy, privacy is achieved by randomizing the data before releasing it. This leads to a fundamental tradeoff between privacy and utility. In this thesis, we take a concrete step towards understanding the fundamental structure of privacy mechanisms that achieve the best privacy-utility tradeoff. This tradeoff is formulated as a constrained optimization problem: maximize utility subject to differential privacy constraints. We show, perhaps surprisingly, that in all three privacy contexts, the optimal privacy mechanisms have the same combinatorial staircase structure. This deep result is a direct consequence of the geometry of the constraints imposed by differential privacy on the privatization mechanisms.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-11-09 without embargo terms","The student, Peter Kairouz, accepted the attached license on 2016-04-19 at 14:12.","The student, Peter Kairouz, submitted this Dissertation for approval on 2016-04-19 at 14:19.","This Dissertation was approved for publication on 2016-04-20 at 16:44.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9341 on 2016-11-09 at 10:19:05","Made available in DSpace on 2016-11-10T17:49:18Z (GMT). No. of bitstreams: 3 KAIROUZ-DISSERTATION-2016.pdf: 5502601 bytes, checksum: 4b6054e2287a29f74af5e94e2e72d614 (MD5) LICENSE.txt: 4210 bytes, checksum: f645d2e47d8e2f13bd8e4f537c41e1f6 (MD5) PROQUEST_LICENSE.txt: 4556 bytes, checksum: 6db5cb25fb30290d63830ecbc3faf01c (MD5) Previous issue date: 2016-04-20"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/92686"],"dc:language":["en"],"dc:rights":["Copyright © 2016 by Peter Kairouz"],"dc:subject":["Privacy","Information Theory","Data Privacy","Statistics","Multi-Party Computation","Security","Local Differential Privacy","Privacy-Preserving Machine Learning Algorithms","Information Theoretic Utilities","f-Divergence","Mutual Information","Statistical Inference","Hypothesis Testing","Estimation"],"dc:title":["The fundamental limits of statistical data privacy"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:35Z"}