The Role of Interactivity in Local Differential Privacy

Understand

We study the power of interactivity in local differential privacy.

• First, we focus on the difference between fully interactive and sequentially interactive protocols.
• Sequentially interactive protocols may query users adaptively in sequence, but they cannot return to previously queried users.
• The vast majority of existing lower bounds for local differential privacy apply only to sequentially interactive protocols, and before this paper it was not known whether fully interactive protocols were more powerful.