differential privacy, federated learning, decision trees, privacy amplification, privacy composition, Technology, Engineering (General). Civil engineering (General), TA1-2040, Biology (General), QH301-705.5, Physics, QC1-999, Chemistry, QD1-999

In decentralized scenarios without fully trustable parties (e.g., in mobile edge computing or IoT environments), the shuffle model has recently emerged as a promising paradigm for differentially private federated learning. Despite many efforts of privacy accounting for federated learning with many sequential rounds in the shuffle model, they suffer from generality and tightness. For example, existing accounting methods are targeted to single-message shuffle protocols (which have intrinsic utility barriers compared to multi-message ones), and are untight for the commonly used vector randomized response randomizer. As countermeasures, we first present a tight total variation characterization of vector randomized response randomizers in the shuffle model, which demonstrates over 20% budget conservation. We then unify the representation of single-message and multi-message shuffle protocols and derive their privacy loss distribution (PLD). The PLDs are finally composed by Fourier analysis to obtain the overall privacy loss of many sequential rounds in the shuffle model. Through simulations in federated decision tree building and federated deep learning, we show that our approach saves up to 80% budget when compared to existing methods.