Private Set Union Based Approach to Enable Private Federated Submodel Learning

We consider the federated submodel learning (FSL) problem and propose an approach where clients are able to update the central model information theoretically privately. Our approach is based on private set union (PSU), which is further based on multi-message symmetric private information retrieval (MM-SPIR). With our scheme, the server does not learn anything further than the subset of submodels updated by the clients: the server does not know which client updated which submodel(s), or anything about the local client data. In comparison to the state-of-the-art private FSL schemes of Jia-Jafar and Vithana-Ulukus, our scheme does not require noisy storage of the model at the databases; and in comparison to the secure aggregation scheme of Zhao-Sun, our scheme incorporates the creation of the required client-side common randomness via random symmetric private information retrieval (RSPIR) and one-time pads. Our system is initialized with a replicated storage of submodels and a sufficient amount of common randomness in two databases at the server-side. The protocol starts with a common randomness generation (CRG) where the two databases establish common randomness at the client-side (FSL-CRG phase). Next, the clients utilize the established client-side common randomness to have the server determine privately the union of indices of submodels to be updated collectively by the clients (FSL-PSU phase). Then, the two databases broadcast the current versions of the submodels in the set union to clients. The clients update the submodels based on their local data. Finally, the clients use a variation of FSL-PSU to write the updates back to the databases privately (FSL-write phase). Our proposed private FSL scheme achieves low communication cost, and is also robust against client dropouts, client late-arrivals, and database drop-outs.