The limits of pan privacy and shuffle privacy for learning and estimation

There has been a recent wave of interest in intermediate trust models for di erential privacy that eliminate the need for a fully trusted central data collector, but overcome the limitations of local di erential privacy. This interest has led to the introduction of the shu e model (Cheu et al., EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private model (Dwork et al., ITCS 2010). The message of this line of work is that, for a variety of low-dimensional problemssuch as counts, means, and histograms-these intermediate models o er nearly as much power as central di erential privacy. However, there has been considerably less success using these models for high-dimensional learning and estimation problems. In this work we prove the rst non-trivial lower bounds for high-dimensional learning and estimation in both the pan-private model and the general multi-message shu e model. Our lower bounds apply to a variety of problems-for example, we show that, private agnostic learning of parity functions over 𝑑 bits requires Ω(2 𝑑/2 ) samples in these models, and privately selecting the most common attribute from a set of 𝑑 choices requires Ω(𝑑 1/2 ) samples, both of which are exponential separations from the central model. Our work gives the rst non-trivial lower bounds for learning and optimization in both the pan-private and the general multi-message shu e model.