# On InstaHide, Phase Retrieval, and Sparse Matrix Factorization

arXiv: https://arxiv.org/abs/2011.11181 · HTML: https://mlsanity.com/paper/2011.11181/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Nov 2020.

## Built on by (most cited first, 4 of 4)

- [Evaluating Gradient Inversion Attacks and Defenses in Federated Learning](https://mlsanity.com/paper/2112.00059/) (2021)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Symmetric Sparse Boolean Matrix Factorization and Applications](https://mlsanity.com/paper/2102.01570/) (2021)
- [Prototype Guided Backdoor Defense](https://mlsanity.com/paper/2503.20925/) (2025)

## Abstract (arXiv)

In this work, we examine the security of InstaHide, a scheme recently proposed by [Huang, Song, Li and Arora, ICML'20] for preserving the security of private datasets in the context of distributed learning. To generate a synthetic training example to be shared among the distributed learners, InstaHide takes a convex combination of private feature vectors and randomly flips the sign of each entry of the resulting vector with probability 1/2. A salient question is whether this scheme is secure in any provable sense, perhaps under a plausible hardness assumption and assuming the distributions generating the public and private data satisfy certain properties. We show that the answer to this appears to be quite subtle and closely related to the average-case complexity of a new multi-task, missing-data version of the classic problem of phase retrieval. Motivated by this connection, we design a provable algorithm that can recover private vectors using only the public vectors and synthetic vectors generated by InstaHide, under the assumption that the private and public vectors are isotropic Gaussian.