  This work investigates the design of sparse secret sharing schemes that
encode a sparse private matrix into sparse shares. This investigation is
motivated by distributed computing, where the multiplication of sparse and
private matrices is moved from a computationally weak main node to untrusted
worker machines. Classical secret-sharing schemes produce dense shares.
However, sparsity can help speed up the computation. We show that, for matrices
with i.i.d. entries, sparsity in the shares comes at a fundamental cost of
weaker privacy. We derive a fundamental tradeoff between sparsity and privacy
and construct optimal sparse secret sharing schemes that produce shares that
leak the minimum amount of information for a desired sparsity of the shares. We
apply our schemes to distributed sparse and private matrix multiplication
schemes with no colluding workers while tolerating stragglers. For the setting
of two non-communicating clusters of workers, we design a sparse one-time pad
so that no private information is leaked to a cluster of untrusted and
colluding workers, and the shares with bounded but non-zero leakage are
assigned to a cluster of partially trusted workers. We conclude by discussing
the necessity of using permutations for matrices with correlated entries.
