We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.
%0 Conference Paper
%1 DBLP:conf/stoc/BlumLR08
%A Blum, Avrim
%A Ligett, Katrina
%A Roth, Aaron
%B STOC
%D 2008
%E Ladner, Richard E.
%E Dwork, Cynthia
%I ACM
%K database differential_privacy privacy
%P 609-618
%R 10.1145/1374376.1374464
%T A Learning Theory Approach to Non-Interactive Database Privacy
%X We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.
%@ 978-1-60558-047-0
@inproceedings{DBLP:conf/stoc/BlumLR08,
abstract = {We demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial VC-dimension. We show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. Despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. Inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.},
added-at = {2010-03-09T03:25:24.000+0100},
author = {Blum, Avrim and Ligett, Katrina and Roth, Aaron},
bibsource = {DBLP, http://dblp.uni-trier.de},
biburl = {https://www.bibsonomy.org/bibtex/2c7a08f242dfd926edaaeee82cc04686b/ytyoun},
booktitle = {STOC},
crossref = {DBLP:conf/stoc/2008},
doi = {10.1145/1374376.1374464},
editor = {Ladner, Richard E. and Dwork, Cynthia},
interhash = {a554d12fc8b4de5e6f17fb20cd523e35},
intrahash = {c7a08f242dfd926edaaeee82cc04686b},
isbn = {978-1-60558-047-0},
keywords = {database differential_privacy privacy},
pages = {609-618},
publisher = {ACM},
timestamp = {2017-12-08T03:15:51.000+0100},
title = {A Learning Theory Approach to Non-Interactive Database Privacy},
year = 2008
}