Abstract
The shuffle model of differential privacy was proposed as a viable model forperforming distributed differentially private computations. Informally, themodel consists of an untrusted analyzer that receives messages sent byparticipating parties via a shuffle functionality, the latter potentiallydisassociates messages from their senders. Prior work focused on one-rounddifferentially private shuffle model protocols, demonstrating thatfunctionalities such as addition and histograms can be performed in this modelwith accuracy levels similar to that of the curator model of differentialprivacy, where the computation is performed by a fully trusted party. Focusing on the round complexity of the shuffle model, we ask in this workwhat can be computed in the shuffle model of differential privacy with tworounds. Ishai et al. [FOCS 2006] showed how to use one round of the shuffle toestablish secret keys between every two parties. Using this primitive tosimulate a general secure multi-party protocol increases its round complexityby one. We show how two parties can use one round of the shuffle to send secretmessages without having to first establish a secret key, hence retaining roundcomplexity. Combining this primitive with the two-round semi-honest protocol ofApplebaun et al. [TCC 2018], we obtain that every randomized functionality canbe computed in the shuffle model with an honest majority, in merely two rounds.This includes any differentially private computation. We then move to examinedifferentially private computations in the shuffle model that (i) do notrequire the assumption of an honest majority, or (ii) do not admit one-roundprotocols, even with an honest majority. For that, we introduce twocomputational tasks: the common-element problem and the nested-common-elementproblem, for which we show separations between one-round and two-roundprotocols.