Multi-Server Private Linear Computation with Joint and Individual Privacy Guarantees

This paper considers the problem of multi-server Private Linear Computation,\nunder the joint and individual privacy guarantees. In this problem, identical\ncopies of a dataset comprised of $K$ messages are stored on $N$ non-colluding\nservers, and a user wishes to obtain one linear combination of a $D$-subset of\nmessages belonging to the dataset. The goal is to design a scheme for\nperforming the computation such that the total amount of information downloaded\nfrom the servers is minimized, while the privacy of the $D$ messages required\nfor the computation is protected. When joint privacy is required, the\nidentities of all of these $D$ messages must be kept private jointly, and when\nindividual privacy is required, the identity of every one of these $D$ messages\nmust be kept private individually. In this work, we characterize the capacity,\nwhich is defined as the maximum achievable download rate, under both joint and\nindividual privacy requirements. In particular, we show that when joint privacy\nis required the capacity is given by ${(1+1/N+\\dots+1/N^{K-D})^{-1}}$, and when\nindividual privacy is required the capacity is given by\n${(1+1/N+\\dots+1/N^{\\lceil K/D\\rceil-1})^{-1}}$ assuming that $D$ divides $K$,\nor $K\\pmod D$ divides $D$. Our converse proofs are based on reduction from two\nvariants of the multi-server Private Information Retrieval problem in the\npresence of side information. Our achievability schemes build up on our\nrecently proposed schemes for single-server Private Linear Transformation and\nthe multi-server private computation scheme proposed by Sun and Jafar. Using\nsimilar proof techniques, we also establish upper and lower bounds on the\ncapacity for the cases in which the user wants to compute $L$ (potentially more\nthan one) linear combinations.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC