Private Computation of Systematically Encoded Data with Colluding\n Servers

Abstract

Private Computation (PC), recently introduced by Sun and Jafar, is a\ngeneralization of Private Information Retrieval (PIR) in which a user wishes to\nprivately compute an arbitrary function of data stored across several servers.\nWe construct a PC scheme which accounts for server collusion, coded data, and\nnon-linear functions. For data replicated over several possibly colluding\nservers, our scheme computes arbitrary functions of the data with rate equal to\nthe asymptotic capacity of PIR for this setup. For systematically encoded data\nstored over colluding servers, we privately compute arbitrary functions of the\ncolumns of the data matrix and calculate the rate explicitly for polynomial\nfunctions. The scheme is a generalization of previously studied star-product\nPIR schemes.\n