  Homomorphic secret sharing (HSS) allows multiple input clients to
secret-share their data among multiple servers such that each server is able to
locally compute a function on its shares to obtain a partial result and all
partial results enable the reconstruction of the function's value on the
outsourced data by an output client. The existing HSS schemes for {\em
high-degree} polynomials either {\em require a large number of servers} or {\em
lack verifiability}, which is essential for ensuring the correctness of the
outsourced computations. In this paper, we propose a two-server verifiable HSS
(VHSS) model and construct a scheme that supports the computation of
high-degree polynomials. The degree of the outsourced polynomials can be as
high as a polynomial in the system's security parameter. Despite of using only
2 servers, our VHSS ensures that each single server learns no information about
the outsourced data and no single server is able to persuade the client to
output a wrong function value. Our VHSS is significantly more efficient. When
computing degree-7 polynomials, our scheme could be 3-10 times faster than the
previously best construction.
