Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the sample complexity of InstaHide challenge in an idealized setting, where it is assumed that each public and private image is generated using a standard Gaussian distribution. Further, similar to previous attacks, the paper assumes that each image is a combination of 2 private images.

The main contribution of the paper is to show that using O(n polylog ) images one can recover all private images in the InstaHide challenge. This is an improvement over previous works in two ways: 1) The paper shows how to recover all images rather than few (or 1) images. 2) The previous best sample complexity for this case was n^4/3. However, on the downside, the running time of the algorithm is exponential in the number of private images.
main_review: 
Techniques:

The overall framework used in the paper is very similar to previous attacks on InstaHide by Carilini  et al [CDG+20] and Chen et al [CSZ20]. From my understanding, the main innovation seems to be in finding W such that WW^T = M, where M is the gram matrix. Here the paper deviates from the previous approaches, treats the problem as a question in Graph theory, and uses a result due to Whitney. This connection is simple but neat. Rest of the attack is similar to CSZ20 as I understand.

summary_of_the_review: The paper makes reasonable improvements to the sample complexity of InstaHide challenge. However, I have two main concerns:

1) Is the attack in the paper gives any significant improvement in real world application? I feel that it is not, and paper has no experiments. Given that InstaHide is rather new suggestion for privacy in ML and has not really been widely used, so I am not sure if this is a significant improvement in practice. I would like to know authors take on this.

2) My understand that finding W such that WW^T = M by applying Whitney's theorem seems to be the only difference compared to CSZ20 paper. Is this correct? It would be worthwhile to summarize technical improvements over CSZ20.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors examines the sample complexity for recovery private images in the InstaHide setting. Comparing with existing works, the authors provided a tighter sample complexity bound when k_{priv} =2, which is nearly-optimal up to logarithmic factors at the cost of an increased time-complexity. 
main_review: As a theoretical paper, I consider the results solid and complete (I did not checked all the details of the proof). Although it brings the bound to nearly optimal for a particular settings (k_priv = 2), but it seems to be a common settings and great starting point. 

My main concern of this submission is its limited scope: the conclusion provides limited value for people outside of this area. It is unlikely to benefit practitioners or readers who works on other theoretical problems other than InstaHide. However, due to the significance of the privacy related topics, I would err on the side of accepting.

In order to provide more value to a larger audience: It will be great if the authors can provide more discussion for cases where k_priv > 2, it will help readers who are not familiar with the InstaHide setting (like myself) to gain more insight on the problem and it will have better utilities for the field as a whole. Additional assumptions or empirical demonstration would also help. 
summary_of_the_review: The authors provides a solid solution for a problem with limited scope. In the current form, I believe the value for the general readers are limited, therefore I would recommend for weak reject. It will be great if the authors can generalize the results for a larger impact.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the weaknesses of InstaHide and provides an algorithm for retrieving all private images using near-linear size samples from the distribution of the private images.
main_review: Inspired by previous works (e.g., Chen, Song, and Zhuo’20), the paper assumes that the images were sampled from a Gaussian distribution and the number of images needed to be mixed via InstaHide is 2 (i.e., $k=2$). Assumptions of this sort in this context are somewhat acceptable and used in practice.

This paper is a generalization of the paper by Chen et al. (2021), where the sample size has been exponentially improved, while the time needed to find such a sample worsened. The time in the paper was shown to be exponential in the number of the hidden images, due to a reduction to solving an instance of a regression problem where the signs of the entries are unknown or hidden. Although the time needed to design the attack is exponential in the number of private images, the theoretical guarantees are favorable.

Although the theory seems sound, however, the weakness of this paper lies in its practicability. Is it possible to apply some data reduction techniques (e.g., coresets) of the data with respect to your variant of the $\ell_2$-regression? This would help in reducing the time needed to solve the problem. However, note that using such technology would result in an approximated solution to the regression problem.
summary_of_the_review: First, the paper is well written and the theoretical results are sound.  Secondly, the paper indeed sheds light on the weaknesses of InstaHide. The authors have in addition shown the hardness of the involved regression problem with hidden signs, which is responsible for a large amount of time (theoretically speaking) needed for the suggested attack on InstaHide.
review_title: null

Meta-review: All reviewers agree that this is a reasonable contribution but that it is also extremely limited in scope. The authors suggest in one of their response that their technique could apply to "any data mixing method with “batched k-sum” structure". Such a larger level of generality might make the paper more interesting, but at the moment it is an extremely niche result.
Decision: Reject