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.

Outsourcing computations allows the resource-constrained clients (such as, IoT devices) to offload heavy computations to powerful cloud servers. At the same time, it brings many challenges such as data privacy, result verification and fair payment. In this paper, we propose a privacy-preserving multi-function verifiable computation (MFVC) model and construct an MFVC scheme for outsourcing matrix multiplication computations (MMC), which have many real-life applications, such as machine learning. Our scheme keeps one of the matrices in MMCsemantically secureand allows apublic verificationof the server's work. In particular, the client's work isfasterthan the native MMC for square matrices of order$\geq 7000$, while the best existing scheme requires matrices of order$\geq 270000$. We also propose a smart contract-based framework that equips the proposed scheme withfair paymentproperty. By offloading the verification to the blockchain, the client's work is faster than the native MMC for square matrices of order$\geq 6000$.

We present Matproofs, a matrix commitment scheme that allows one to commit to any matrix and then open any subset of the matrix entries. If we encode any vector as a matrix, by committing to the matrix Matproofs may function well as a vector commitment (VC) scheme. We show that Matproofs are simultaneously concise, aggregatable, easily updatable and maintainable. With these promising features, Matproofs give solutions to payment-only stateless cryptocurrencies with lower bandwidth and computational complexity. Compared with Hyperproofs, the only existing VC scheme that is simultaneously aggregatable, easily updatable and maintainable, Matproofs achieve the additional property of conciseness. Furthermore, in the worst case, the proof aggregation and verification in Matproofs are 700x and 10x faster than Hyperproofs, respectively.