Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity

Understand

Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time.

• For example, trends in users' private preferences or software usage may be monitored via such reports.
• We study the collection of such statistics in the local differential privacy (LDP) model, and describe an algorithm whose privacy cost is polylogarithmic in the number of changes to a user's value.
• More fundamentally---by building on anonymity of the users' reports---we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy.