Using Noisy Binary Search for Differentially Private Anomaly Detection

Daniel M. Bittner; Anand D. Sarwate; Rebecca N. Wright

doi:10.1007/978-3-319-94147-9_3

Using Noisy Binary Search for Differentially Private Anomaly Detection

Daniel M. Bittner, Anand D. Sarwate, Rebecca N. Wright

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

In this paper, we study differential privacy in noisy search. This problem is connected to noisy group testing: the goal is to find a defective or anomalous item within a group using only aggregate group queries, not individual queries. Differentially private noisy group testing has the potential to be used for anomaly detection in a way that provides differential privacy to the non-anomalous individuals while still helping to allow the anomalous individuals to be located. To do this, we introduce the notion of anomaly-restricted differential privacy. We then show that noisy group testing can be used to satisfy anomaly-restricted differential privacy while still narrowing down the location of the anomalous samples, and evaluate our approach experimentally.

Original language	English (US)
Title of host publication	Cyber Security Cryptography and Machine Learning - Second International Symposium, CSCML 2018, Proceedings
Editors	Itai Dinur, Shlomi Dolev, Sachin Lodha
Publisher	Springer Verlag
Pages	20-37
Number of pages	18
ISBN (Print)	9783319941462
DOIs	https://doi.org/10.1007/978-3-319-94147-9_3
State	Published - 2018
Event	2nd International Symposium on Cyber Security Cryptography and Machine Learning, CSCML 2018 - Beer-Sheva, Israel Duration: Jun 21 2018 → Jun 22 2018

Publication series

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

Other

Other	2nd International Symposium on Cyber Security Cryptography and Machine Learning, CSCML 2018
Country/Territory	Israel
City	Beer-Sheva
Period	6/21/18 → 6/22/18

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-94147-9_3

Cite this

Bittner, D. M., Sarwate, A. D., & Wright, R. N. (2018). Using Noisy Binary Search for Differentially Private Anomaly Detection. In I. Dinur, S. Dolev, & S. Lodha (Eds.), Cyber Security Cryptography and Machine Learning - Second International Symposium, CSCML 2018, Proceedings (pp. 20-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10879 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-94147-9_3

Bittner, Daniel M. ; Sarwate, Anand D. ; Wright, Rebecca N. / Using Noisy Binary Search for Differentially Private Anomaly Detection. Cyber Security Cryptography and Machine Learning - Second International Symposium, CSCML 2018, Proceedings. editor / Itai Dinur ; Shlomi Dolev ; Sachin Lodha. Springer Verlag, 2018. pp. 20-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{43d2845416a947e18739b5e19537bf31,

title = "Using Noisy Binary Search for Differentially Private Anomaly Detection",

abstract = "In this paper, we study differential privacy in noisy search. This problem is connected to noisy group testing: the goal is to find a defective or anomalous item within a group using only aggregate group queries, not individual queries. Differentially private noisy group testing has the potential to be used for anomaly detection in a way that provides differential privacy to the non-anomalous individuals while still helping to allow the anomalous individuals to be located. To do this, we introduce the notion of anomaly-restricted differential privacy. We then show that noisy group testing can be used to satisfy anomaly-restricted differential privacy while still narrowing down the location of the anomalous samples, and evaluate our approach experimentally.",

author = "Bittner, {Daniel M.} and Sarwate, {Anand D.} and Wright, {Rebecca N.}",

note = "Funding Information: Acknowledgements. This work was partially supported by NSF under award CCF-1453432, DARPA and SSC Pacific under contract N66001-15-C-4070, and DHS under award 2009-ST-061-CCI002 and contract HSHQDC-16-A-B0005/HSHQDC-16-J-00371. Publisher Copyright: {\textcopyright} 2018, Springer International Publishing AG, part of Springer Nature.; 2nd International Symposium on Cyber Security Cryptography and Machine Learning, CSCML 2018 ; Conference date: 21-06-2018 Through 22-06-2018",

year = "2018",

doi = "10.1007/978-3-319-94147-9_3",

language = "English (US)",

isbn = "9783319941462",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "20--37",

editor = "Itai Dinur and Shlomi Dolev and Sachin Lodha",

booktitle = "Cyber Security Cryptography and Machine Learning - Second International Symposium, CSCML 2018, Proceedings",

address = "Germany",

}

Bittner, DM, Sarwate, AD & Wright, RN 2018, Using Noisy Binary Search for Differentially Private Anomaly Detection. in I Dinur, S Dolev & S Lodha (eds), Cyber Security Cryptography and Machine Learning - Second International Symposium, CSCML 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10879 LNCS, Springer Verlag, pp. 20-37, 2nd International Symposium on Cyber Security Cryptography and Machine Learning, CSCML 2018, Beer-Sheva, Israel, 6/21/18. https://doi.org/10.1007/978-3-319-94147-9_3

Using Noisy Binary Search for Differentially Private Anomaly Detection. / Bittner, Daniel M.; Sarwate, Anand D.; Wright, Rebecca N.
Cyber Security Cryptography and Machine Learning - Second International Symposium, CSCML 2018, Proceedings. ed. / Itai Dinur; Shlomi Dolev; Sachin Lodha. Springer Verlag, 2018. p. 20-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10879 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Using Noisy Binary Search for Differentially Private Anomaly Detection

AU - Bittner, Daniel M.

AU - Sarwate, Anand D.

AU - Wright, Rebecca N.

N1 - Funding Information: Acknowledgements. This work was partially supported by NSF under award CCF-1453432, DARPA and SSC Pacific under contract N66001-15-C-4070, and DHS under award 2009-ST-061-CCI002 and contract HSHQDC-16-A-B0005/HSHQDC-16-J-00371. Publisher Copyright: © 2018, Springer International Publishing AG, part of Springer Nature.

PY - 2018

Y1 - 2018

N2 - In this paper, we study differential privacy in noisy search. This problem is connected to noisy group testing: the goal is to find a defective or anomalous item within a group using only aggregate group queries, not individual queries. Differentially private noisy group testing has the potential to be used for anomaly detection in a way that provides differential privacy to the non-anomalous individuals while still helping to allow the anomalous individuals to be located. To do this, we introduce the notion of anomaly-restricted differential privacy. We then show that noisy group testing can be used to satisfy anomaly-restricted differential privacy while still narrowing down the location of the anomalous samples, and evaluate our approach experimentally.

AB - In this paper, we study differential privacy in noisy search. This problem is connected to noisy group testing: the goal is to find a defective or anomalous item within a group using only aggregate group queries, not individual queries. Differentially private noisy group testing has the potential to be used for anomaly detection in a way that provides differential privacy to the non-anomalous individuals while still helping to allow the anomalous individuals to be located. To do this, we introduce the notion of anomaly-restricted differential privacy. We then show that noisy group testing can be used to satisfy anomaly-restricted differential privacy while still narrowing down the location of the anomalous samples, and evaluate our approach experimentally.

UR - http://www.scopus.com/inward/record.url?scp=85049030049&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049030049&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-94147-9_3

DO - 10.1007/978-3-319-94147-9_3

M3 - Conference contribution

AN - SCOPUS:85049030049

SN - 9783319941462

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 20

EP - 37

BT - Cyber Security Cryptography and Machine Learning - Second International Symposium, CSCML 2018, Proceedings

A2 - Dinur, Itai

A2 - Dolev, Shlomi

A2 - Lodha, Sachin

PB - Springer Verlag

T2 - 2nd International Symposium on Cyber Security Cryptography and Machine Learning, CSCML 2018

Y2 - 21 June 2018 through 22 June 2018

ER -

Bittner DM, Sarwate AD, Wright RN. Using Noisy Binary Search for Differentially Private Anomaly Detection. In Dinur I, Dolev S, Lodha S, editors, Cyber Security Cryptography and Machine Learning - Second International Symposium, CSCML 2018, Proceedings. Springer Verlag. 2018. p. 20-37. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-94147-9_3

Using Noisy Binary Search for Differentially Private Anomaly Detection

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this