Pollen: Single-server Sparse Secure Aggregation with Minimal Leakage

Secure aggregation protects the values of client updates in federated learning but assumes dense model updates. This assumption misaligned with modern language models and recommendation system models, whose index embedding and parameter-efficient fine-tuning layers produce highly sparse updates. While recent works such as Meridian (S&P 2026) and Clover (CCS 2025) have proposed sparse secure aggregation protocols, they focus on non-colluding multiple-server setting only, and the privacy effects of sparse updates comparing to dense are still not well understood. In this paper, we identify a new leakage channel, termed client index structure leakage, arising from the co-occurrence structure of sparse updates. We show that under a positive distributional-gap assumption, any sparse aggregation protocol whose server view preserves per-client index co-occurrence information admits cross-round client re-identification attacks. Conversely, we show that revealing only the union of active input indices is sufficient, as this information is already derivable from the ideal functionality of dense secure aggregation. Together, these results characterize a minimal leakage profile for sparse secure aggregation. Guided by this characterization, we introduce a new primitive, labeled multiparty private set union (LMPSU) and present a lightweight single-server construction, Pollen, based on arithmetic invertible Bloom lookup tables and secure aggregation. Building on this primitive, we design a sparse secure aggregation protocol for sparse embedding updates. Experiments show that our approach eliminates re-identification attacks while achieving a $1.9-2803\times$ communication savings compared to dense secure aggregation.