Shared Spotlight Meridian: Distributed Sparse Pseudorandom Functions for Scalable Federated Learning

Secure federated learning enables multiple clients to train a shared model while keeping raw data private. Minimizing communication is natural in secure multiparty computation, yet cryptographic mechanisms create tension. Consequently, existing secure aggregation protocols are illsuited to high-dimensional sparse updates and forfeit sparsification gains, inflating communication by orders of magnitude relative to plaintext aggregation.

Seeking efficiency under privacy, we introduce distributed sparse pseudorandom functions. Hidden alignment comes from a secretly shared spotlight index that illuminates the chosen coordinate and serves as a meridian that anchors aggregations of nonzero entries. Enabled by our cryptographic advances, we present a secure aggregation protocol with near-optimal client communication. Relative to a plaintext baseline, each client sends at most one extra bit per nonzero gradient element. Multi-server security holds unless all servers collude. At the client side, computational overhead is small, and server communication is optimal. Near-baseline accuracy is seen across computer vision, natural language processing, and recommendation experiments, with plaintext-level bandwidth savings.

1. Here, we assume i matches the coordinate that the client will use. 2. Advanced encryption standard, or any pseudorandom permutation