Efficient Private Federated Submodel Learning

We investigate the problem of private federated submodel learning, where a machine learning model is divided into M submodels and stored in N databases, from which a given user privately reads, updates and writes back an arbitrary submodel. We consider information-theoretic privacy of the updated submodel index as well as the values of the updates. We provide an efficient private read update write (PRUW) scheme which achieves a lower total communication cost compared to the state-of-the-art. Our scheme significantly reduces the writing cost by combining all updates into a single bit in a way that it can be privately decomposed and placed at the relevant positions at the databases. This is achieved by over-designing the system with additional random noise terms in storage, which in turn provides additional security to the submodels. The scheme is designed for arbitrary privacy and security requirements.