  Delegating large-scale computations to service providers is a common practice
which raises privacy concerns. This paper studies information-theoretic
privacy-preserving delegation of data to a service provider, who may further
delegate the computation to auxiliary worker nodes, in order to compute a
polynomial over that data at a later point in time. We study techniques which
are compatible with robust management of distributed computation systems, an
area known as coded computing. Privacy in coded computing, however, has
traditionally addressed the problem of colluding workers, and assumed that the
server that administrates the computation is trusted. This viewpoint of privacy
does not accurately reflect real-world privacy concerns, since normally, the
service provider as a whole (i.e., the administrator and the worker nodes) form
one cohesive entity which itself poses a privacy risk. This paper aims to shift
the focus of privacy in coded computing to safeguarding the privacy of the user
against the service provider as a whole, instead of merely against colluding
workers inside the service provider. To this end, we leverage the recently
defined notion of perfect subset privacy, which guarantees zero information
leakage from all subsets of the data up to a certain size. Using known
techniques from Reed-Muller decoding, we provide a scheme which enables
polynomial computation with perfect subset privacy in straggler-free systems.
Furthermore, by studying information super-sets in Reed-Muller codes, which may
be of independent interest, we extend the previous scheme to tolerate
straggling worker nodes inside the service provider.
