  In a typical formulation of the private information retrieval (PIR) problem,
a single user wishes to retrieve one out of K files from N servers without
revealing the demanded file index to any server. This paper formulates an
extended model of PIR, referred to as multi-message private computation
(MM-PC), where instead of retrieving a single file, the user wishes to retrieve
P > 1 linear combinations of files while preserving the privacy of the demand
information. The MM-PC problem is a generalization of the private computation
(PC) problem (where the user requests one linear combination of the files), and
the multi-message private information retrieval (MM-PIR) problem (where the
user requests P > 1 files). A baseline achievable scheme repeats the optimal PC
scheme by Sun and Jafar P times, or treats each possible demanded linear
combination as an independent file and then uses the near optimal MM-PIR scheme
by Banawan and Ulukus. In this paper, we propose an achievable MM-PC scheme
that significantly improves upon the baseline scheme. Doing so, we design the
queries inspiring from the structure in the cache-aided scalar linear function
retrieval scheme by Wan et al., where they leverage the dependency between
messages to reduce the amount of communication. To ensure the decodability of
our scheme, we propose a new method to benefit from the existing dependency,
referred to as the sign assignment step. In the end, we use Maximum Distance
Separable matrices to code the queries, which allows the reduction of download
from the servers, while preserving privacy.
