Testing the Lipschitz property over product distributions with applications to data privacy

Kashyap Dixit, Madhav Jha, Sofya Raskhodnikova, Abhradeep Thakurta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Proceedings
Pages418-436
Number of pages19
DOIs
StatePublished - 2013
Event10th Theory of Cryptography Conference, TCC 2013 - Tokyo, Japan
Duration: Mar 3 2013Mar 6 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7785 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th Theory of Cryptography Conference, TCC 2013
Country/TerritoryJapan
CityTokyo
Period3/3/133/6/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Testing the Lipschitz property over product distributions with applications to data privacy'. Together they form a unique fingerprint.

Cite this