TY - GEN
T1 - Testing the Lipschitz property over product distributions with applications to data privacy
AU - Dixit, Kashyap
AU - Jha, Madhav
AU - Raskhodnikova, Sofya
AU - Thakurta, Abhradeep
PY - 2013
Y1 - 2013
N2 - In the past few years, the focus of research in the area of statistical data privacy has been in designing algorithms for various problems which satisfy some rigorous notions of privacy. However, not much effort has gone into designing techniques to computationally verify if a given algorithm satisfies some predefined notion of privacy. In this work, we address the following question: Can we design algorithms which tests if a given algorithm satisfies some specific rigorous notion of privacy (e.g., differential privacy)? We design algorithms to test privacy guarantees of a given algorithm when run on a dataset x containing potentially sensitive information about the individuals. More formally, we design a computationally efficient algorithm that verifies whether satisfies differential privacy on typical datasets (DPTD) guarantee in time sublinear in the size of the domain of the datasets. DPTD, a similar notion to generalized differential privacy first proposed by [3], is a distributional relaxation of the popular notion of differential privacy [14]. To design algorithm , we show a formal connection between the testing of privacy guarantee for an algorithm and the testing of the Lipschitz property of a related function. More specifically, we show that an efficient algorithm for testing of Lipschitz property can be used as a subroutine in that tests if an algorithm satisfies differential privacy on typical datasets. Apart from formalizing the connection between the testing of privacy guarantee and testing of the Lipschitz property, we generalize the work of [21] to the setting of property testing under product distribution. More precisely, we design an efficient Lipschitz tester for the case where the domain points are drawn from hypercube according to some fixed but unknown product distribution instead of the uniform distribution.
AB - In the past few years, the focus of research in the area of statistical data privacy has been in designing algorithms for various problems which satisfy some rigorous notions of privacy. However, not much effort has gone into designing techniques to computationally verify if a given algorithm satisfies some predefined notion of privacy. In this work, we address the following question: Can we design algorithms which tests if a given algorithm satisfies some specific rigorous notion of privacy (e.g., differential privacy)? We design algorithms to test privacy guarantees of a given algorithm when run on a dataset x containing potentially sensitive information about the individuals. More formally, we design a computationally efficient algorithm that verifies whether satisfies differential privacy on typical datasets (DPTD) guarantee in time sublinear in the size of the domain of the datasets. DPTD, a similar notion to generalized differential privacy first proposed by [3], is a distributional relaxation of the popular notion of differential privacy [14]. To design algorithm , we show a formal connection between the testing of privacy guarantee for an algorithm and the testing of the Lipschitz property of a related function. More specifically, we show that an efficient algorithm for testing of Lipschitz property can be used as a subroutine in that tests if an algorithm satisfies differential privacy on typical datasets. Apart from formalizing the connection between the testing of privacy guarantee and testing of the Lipschitz property, we generalize the work of [21] to the setting of property testing under product distribution. More precisely, we design an efficient Lipschitz tester for the case where the domain points are drawn from hypercube according to some fixed but unknown product distribution instead of the uniform distribution.
UR - http://www.scopus.com/inward/record.url?scp=84873953800&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84873953800&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-36594-2_24
DO - 10.1007/978-3-642-36594-2_24
M3 - Conference contribution
AN - SCOPUS:84873953800
SN - 9783642365935
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 418
EP - 436
BT - Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Proceedings
T2 - 10th Theory of Cryptography Conference, TCC 2013
Y2 - 3 March 2013 through 6 March 2013
ER -