%0 Conference Paper %B Information-Theoretic Cryptography (To appear - ITC 2020) %D 2020 %T The Power of Synergy in Differential Privacy: Combining a Small Curator with Local Randomizers %A Amos Beimel %A Aleksandra Korolova %A Kobbi Nissim %A Or Sheffet %A Uri Stemmer %X

Motivated by the desire to bridge the utility gap between local and trusted curator modelsof differential privacy for practical applications, we initiate the theoretical study of a hybridmodel 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 mn 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 hypothesistesting, 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.

%B Information-Theoretic Cryptography (To appear - ITC 2020) %G eng %U https://arxiv.org/abs/1912.08951