An$(n,m,t)$-homomorphic secret sharing (HSS) scheme for a function family$\mathcal F$allows$n$clients to share their data$x_{1}, \ldots,x_{n}$among$m$servers and then distribute the computation of any function$f\in {\mathcal F}$to the servers such that: (i) any$t$colluding servers learn no information about the data; (ii) each server is able to compute a partial result and$f(x_{1}, \ldots,x_{n})$can be reconstructed from the servers’ partial results. HSS schemes cannot guarantee correct reconstruction, if some servers are malicious and provide wrong partial results. Recently, verifiable HSS (VHSS) has been introduced to achieve an additional property: (iii) any$t$colluding servers cannot persuade the client(s) to accept their partial results and reconstruct a wrong value. The property (iii) is usually achieved by the client verifying the servers’ partial results. A VHSS scheme is compact if the verification is substantially faster than locally computing$f(x_{1},\ldots,x_{n})$. Of the existing VHSS schemes for polynomials, some are not compact; the others are compact but impose very heavy workload on the servers, even for low degree polynomials (e.g., they are at least 4000× slower than the existing HSS schemes in order to evaluate polynomials of degree$\leq 5$, which have many applications such as privacy-preserving machine learning). In this paper, we propose both a single-client VHSS (SVHSS) model and a multi-client VHSS (MVHSS) model. Our SVHSS allows a client to use a secret key to share its data among servers; our MVHSS allows multiple clients to share their data with a public key. For any integers$m,t>0$, we constructed both an$(m,t)$-SVHSS scheme and an$(m,t)$-MVHSS scheme that satisfy the properties of (i)-(iii). Our constructions are based on level-$k$homomorphic encryptions. The$(m,t)$-SVHSS and$(m,t)$-MVHSS are compact and allow the computations of degree-$d$polynomials for$d\leq ((k+1)m-1)/t$and$d\leq ((k+1)(m-t)-1)/t$, respectively. Experiments show that our schemes are much more efficient than the existing compact VHSS for low degree polynomials. For example, to compute polynomials of degree$\leq 5$, our MVHSS scheme is at least 420× faster. By applying SVHSS and MVHSS, we may add verifiability to privacy-preserving machine learning (PPML) algorithms. Experiments show that the resulting schemes are at least 52× and 20× faster than the existing verifiable PPML schemes.

There are two main security concerns in outsourcing computations. One is how to protect the privacy of the outsourced data, and the other is how to ensure the correctness of the outsourced computations. Homomorphic secret sharing (HSS) schemes allow a client to store a set of private data on two servers and then offload a computation on the data to servers. Such schemes ensure that each individual server learns no information about the data. While HSS schemes that allow the client to use a secret key to verify the correctness of the computation results exist and relieve both security concerns, the current literature lacks apublicly verifiableHSS scheme forpolynomial evaluations. In this paper, we consider a two-server publicly verifiable HSS (PVHSS) model, where any third party can use a public key to perform verifications. We propose both a basic construction and an improved construction of PVHSS for evaluating polynomials. Our PVHSS ensures that no single server is able to learn any information about the outsourced data or persuade the verifier to accept a wrong result. We also implement the proposed scheme. For polynomials of degree ≤20, our experiments show that: (1) the proposed PVHSS is 2×-144× faster than the existing non-verifiable or privately verifiable HSS on the server-side; (2) the proposed PVHSS is friendly to resource-restricted clients and takes less than 27ms to reconstruct and verify the results.

Catalano and Fiore propose a scheme to transform a linearly-homomorphic encryption into a homomorphic encryption scheme capable of evaluating quadratic computations on ciphertexts. Their scheme is based on the linearly-homomorphic encryption (such as Goldwasser-Micali, Paillier and ElGamal) and need to perform large integer operation on servers. Then, their scheme have numerous computations on the servers. At the same time, their scheme cannot verify the computations and cannot evaluate more than degree-4 computations. To solve these problems, we no longer use linearly-homomorphic encryption which based on number theory assumptions. We use label and pseudorandom function to encrypt message, which significantly reduce the computations on the servers and enable us to use homomorphic MACs technology to realize verifiable computations naturally. We also extend the method to construct$d$-server schemes, which allow the client to delegate degree-$d$computations on outsourced data.