Timezone: »

 
On the Renyi Differential Privacy of the Shuffle Model
Antonious Girgis · Deepesh Data · Suhas Diggavi · Ananda Theertha Suresh · Peter Kairouz

@
in Theory and Practice of Differential Privacy »

We study the Renyi Differential Privacy (RDP) for general discrete local mechanisms in the {\em shuffle} privacy model, where clients randomize their responses using a local differentially private (LDP) mechanism and the untrusted server only receives a random permutation (shuffle) of the client responses without association to each client. The principal result in this paper is the \emph{first} non-trivial RDP guarantee for general discrete local randomization mechanisms in the shuffled privacy model, and we develop new analysis techniques for deriving our results which could be of independent interest. In applications, such an RDP guarantee is most useful when we use it for composing several private interactions. We numerically demonstrate that, for important regimes, with composition our bound yields a significant improvement in privacy guarantee over the state-of-the-art approximate Differential Privacy (DP) guarantee (with standard composition) for shuffled models.

Author Information

Antonious Girgis (University of California, Los Angeles)
Deepesh Data (UCLA)
Suhas Diggavi (University of California, Los Angeles)
Ananda Theertha Suresh (Google Research)
Peter Kairouz (Google)

More from the Same Authors