TY - GEN
T1 - The power of synergy in differential privacy
T2 - 1st Conference on Information-Theoretic Cryptography, ITC 2020
AU - Beimel, Amos
AU - Korolova, Aleksandra
AU - Nissim, Kobbi
AU - Sheffet, Or
AU - Stemmer, Uri
N1 - Publisher Copyright:
© Amos Beimel, Aleksandra Korolova, Kobbi Nissim, Or Sheffet, and Uri Stemmer; licensed under Creative Commons License CC-BY
PY - 2020/6/1
Y1 - 2020/6/1
N2 - Motivated by the desire to bridge the utility gap between local and trusted curator models of differential privacy for practical applications, we initiate the theoretical study of a hybrid model introduced by “Blender” [Avent et al., USENIX Security’17], in which differentially private protocols of n agents that work in the local-model are assisted by a differentially private curator that has access to the data of m additional users. We focus on the regime where m n and study the new capabilities of this (m,n)-hybrid model. We show that, despite the fact that the hybrid model adds no significant new capabilities for the basic task of simple hypothesis-testing, there are many other tasks (under a wide range of parameters) that can be solved in the hybrid model yet cannot be solved either by the curator or by the local-users separately. Moreover, we exhibit additional tasks where at least one round of interaction between the curator and the local-users is necessary – namely, no hybrid model protocol without such interaction can solve these tasks. Taken together, our results show that the combination of the local model with a small curator can become part of a promising toolkit for designing and implementing differential privacy.
AB - Motivated by the desire to bridge the utility gap between local and trusted curator models of differential privacy for practical applications, we initiate the theoretical study of a hybrid model introduced by “Blender” [Avent et al., USENIX Security’17], in which differentially private protocols of n agents that work in the local-model are assisted by a differentially private curator that has access to the data of m additional users. We focus on the regime where m n and study the new capabilities of this (m,n)-hybrid model. We show that, despite the fact that the hybrid model adds no significant new capabilities for the basic task of simple hypothesis-testing, there are many other tasks (under a wide range of parameters) that can be solved in the hybrid model yet cannot be solved either by the curator or by the local-users separately. Moreover, we exhibit additional tasks where at least one round of interaction between the curator and the local-users is necessary – namely, no hybrid model protocol without such interaction can solve these tasks. Taken together, our results show that the combination of the local model with a small curator can become part of a promising toolkit for designing and implementing differential privacy.
KW - Differential privacy
KW - Hybrid model
KW - Local model
KW - Private learning
UR - http://www.scopus.com/inward/record.url?scp=85092758203&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85092758203&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITC.2020.14
DO - 10.4230/LIPIcs.ITC.2020.14
M3 - Conference contribution
AN - SCOPUS:85092758203
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 1st Conference on Information-Theoretic Cryptography, ITC 2020
A2 - Kalai, Yael Tauman
A2 - Smith, Adam D.
A2 - Wichs, Daniel
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 17 June 2020 through 19 June 2020
ER -