  In this work we examine the security of InstaHide, a recently proposed scheme
for distributed learning (Huang et al.). A number of recent works have given
reconstruction attacks for InstaHide in various regimes by leveraging an
intriguing connection to the following matrix factorization problem: given the
Gram matrix of a collection of m random k-sparse Boolean vectors in {0,1}^r,
recover the vectors (up to the trivial symmetries). Equivalently, this can be
thought of as a sparse, symmetric variant of the well-studied problem of
Boolean factor analysis, or as an average-case version of the classic problem
of recovering a k-uniform hypergraph from its line graph.
  As previous algorithms either required m to be exponentially large in k or
only applied to k = 2, they left open the question of whether InstaHide
possesses some form of "fine-grained security" against reconstruction attacks
for moderately large k. In this work, we answer this in the negative by giving
a simple O(m^{\omega + 1}) time algorithm for the above matrix factorization
problem. Our algorithm, based on tensor decomposition, only requires m to be at
least quasi-linear in r. We complement this result with a quasipolynomial-time
algorithm for a worst-case setting of the problem where the collection of
k-sparse vectors is chosen arbitrarily.
