BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model


Brendan Avent and Aleksandra Korolova, University of Southern California; David Zeber and Torgeir Hovden, Mozilla; Benjamin Livshits, Imperial College London


We propose a hybrid model of differential privacy that considers a combination of regular and opt-in users who desire the differential privacy guarantees of the local privacy model and the trusted curator model, respectively. We demonstrate that within this model, it is possible to design a new type of blended algorithm for the task of privately computing the most popular records of a web search log. This blended approach provides significant improvements in the utility of obtained data compared to related work while providing users with their desired privacy guarantees. Specifically, on two large search click data sets comprising 4.8 million and 13.2 million unique queries respectively, our approach attains NDCG values exceeding 95% across a range of commonly used privacy budget values.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {203630,
author = {Brendan Avent and Aleksandra Korolova and David Zeber and Torgeir Hovden and Benjamin Livshits},
title = {{BLENDER}: Enabling Local Search with a Hybrid Differential Privacy Model},
booktitle = {26th {USENIX} Security Symposium ({USENIX} Security 17)},
year = {2017},
isbn = {978-1-931971-40-9},
address = {Vancouver, BC},
pages = {747--764},
url = {},
publisher = {{USENIX} Association},