  This paper considers the problem of outsourcing the multiplication of two
private and sparse matrices to untrusted workers. Secret sharing schemes can be
used to tolerate stragglers and guarantee information-theoretic privacy of the
matrices. However, traditional secret sharing schemes destroy all sparsity in
the offloaded computational tasks. Since exploiting the sparse nature of
matrices was shown to speed up the multiplication process, preserving the
sparsity of the input matrices in the computational tasks sent to the workers
is desirable. It was recently shown that sparsity can be guaranteed at the
expense of a weaker privacy guarantee. Sparse secret sharing schemes with only
two output shares were constructed. In this work, we construct sparse secret
sharing schemes that generalize Shamir's secret sharing schemes for a fixed
threshold $t=2$ and an arbitrarily large number of shares. We design our
schemes to provide the strongest privacy guarantee given a desired sparsity of
the shares under some mild assumptions. We show that increasing the number of
shares, i.e., increasing straggler tolerance, incurs a degradation of the
privacy guarantee. However, this degradation is negligible when the number of
shares is comparably small to the cardinality of the input alphabet.
