  The shuffle model of differential privacy (DP) offers compelling
privacy-utility trade-offs in decentralized settings (e.g., internet of things,
mobile edge networks). Particularly, the multi-message shuffle model, where
each user may contribute multiple messages, has shown that accuracy can
approach that of the central model of DP. However, existing studies typically
assume a uniform privacy protection level for all users, which may deter
conservative users from participating and prevent liberal users from
contributing more information, thereby reducing the overall data utility, such
as the accuracy of aggregated statistics. In this work, we pioneer the study of
segmented private data aggregation within the multi-message shuffle model of
DP, introducing flexible privacy protection for users and enhanced utility for
the aggregation server. Our framework not only protects users' data but also
anonymizes their privacy level choices to prevent potential data leakage from
these choices. To optimize the privacy-utility-communication trade-offs, we
explore approximately optimal configurations for the number of blanket messages
and conduct almost tight privacy amplification analyses within the shuffle
model. Through extensive experiments, we demonstrate that our segmented
multi-message shuffle framework achieves a reduction of about 50\% in
estimation error compared to existing approaches, significantly enhancing both
privacy and utility.
