Private Histograms in the Shuffle Model

A Google TechTalk, presented by Albert Cheu, 2021/10/27 Privacy in ML Seminars - ABSTRACT: In this talk, I describe two of the (many) differentially private histogram protocols in the shuffle model literature. The shuffle model can be thought of as a relaxation of the local model where a service anonymizes communication between users and an analyzer. The first histogram protocol we consider has asymptotic error close to what is possible in the central model. The second demands only a constant number of messages from each user, so long as the number of users is above a small threshold. The second protocol’s estimates are also robust to malicious users. Speaker: Dr. Albert Cheu (Georgetown University)