  Outsourcing computation has gained significant popularity in recent years due
to the prevalence of cloud computing. There are two main security concerns in
outsourcing computation: how to guarantee the cloud server performs the
computation correctly and how to keep the client's data secret. The {\em
single-server verifiable computation} (SSVC) of Gennaro, Gentry and Parno
(Crypto'10) enables a client to delegate the computation of a function $f$ on
any input $x$ with both concerns highly relieved, but only results in {\em
computationally secure} schemes that
  {\em lack practical efficiency}.
  While the SSVC schemes use a single server, in this paper we develop a {\em
multi-server verifiable computation} (MSVC) model where the client shares both
$f$ and $x$ among multiple servers, each server performs a set of computations
on its shares, and finally the client reconstructs $f(x)$ from all servers'
results. In this MSVC model we propose a generic construction for outsourcing
computations of the form $F{\bf x}$, where $F$ is a matrix and $\bf x$ is a
vector. Our generic construction achieves {\em information-theoretic security,
input privacy} and {\em function privacy}. By optimizing the parameters, we
obtain both a 3-server scheme,which uses the least number of servers, and a
4-server scheme, which incurs the least workload. By decomposing many
polynomial computations as a two-stage computation, where the first-stage has
the form $F{\bf x}$ and the second-stage is fast, and delegating the
first-stage computation, we obtain MSVC schemes for these polynomials. We
implement our MSVC schemes and show that they are among the most {\em
practical} ones to date.
