InstaHide’s Sample Complexity When Mixing Two Private Images
Year: 2021

Abstract:
Inspired by InstaHide challenge [Huang, Song, Li and Arora’20], [Chen, Song and Zhuo’20] recently provides one mathematical formulation of InstaHide attack problem under Gaussian images distribution. They show that it suffices to use O(nprivpriv priv ) samples to recover one private image in n O(kpriv) priv + poly(npub) time for any integer kpriv, where npriv and npub denote the number of images used in the private and the public dataset to generate a mixed image sample. Under the current setup for the InstaHide challenge of mixing two private images (kpriv = 2), this means n 4/3 priv samples are sufficient to recover a private image. In this work, we show that npriv log(npriv) samples are sufficient (information-theoretically) for recovering all the private images.

text: n O(kpriv) priv + poly(npub) time for any integer kpriv, where npriv and npub denote the number of images used in the private and the public dataset to generate a mixed image sample. Under the current setup for the InstaHide challenge of mixing two private images (kpriv = 2), this means n 4/3 priv samples are sufficient to recover a private image. In this work, we show that npriv log(npriv) samples are sufficient (information-theoretically) for recovering all the private images.

heading: 1 Introduction
text: Collaboratively training neural networks based on sensitive data is appealing in many AI applications, such as healthcare, fraud detection, and virtual assistants. How to train neural networks without compromising data confidentiality and prediction accuracy has become an important and common research goal Shokri & Shmatikov (2015); Ryffel et al. (2018); Phong et al. (2018); McMahan et al. (2017); Konečnỳ et al. (2016) in both academia and industry.
Huang et al. (2020b) recently proposed an approach called InstaHide for image classification. The key idea is to train the model on a dataset where (1) each image is a mix of kpriv private images and kpub public images, and (2) each pixel is independently sign-flipped after the mixing. Instahide shows promising prediction accuracy on MNIST Deng (2012), CIFAR10 Krizhevsky (2012), CIFAR-100, and ImageNet datasets Deng et al. (2009). TextHide Huang et al. (2020a) applies InstaHide’s idea to text datasets and achieves promising results on natural language processing tasks.
To understand the security aspect of InstaHide in realistic deployment scenarios, InstaHide authors present an InstaHide challenge Challenge (2020) that involves npriv = 100 private images, ImageNet dataset as the public images, m = 5000 sample images (each image is a combination of kpriv = 2 private images and kpub = 4 public images and the sign of each pixel is randomly flipped). The challenge is to recover a private image given the set of sample images.
Chen et al. (2021) is a theoretical work that formulates the InstaHide attack problem as a recovery problem. It also provides an algorithm to recover a private image assuming each private and public image is a random Gaussian image (i.e., each pixel is an i.i.d. draw from N (0, 1)). The algorithm shows that O(nkpriv−2/(kpriv+1)priv ) sample images are sufficient to recover one private image. Carlini et al. (2020) provides the first heuristic-based practical attack for the InstaHide challenge (kpriv = 2), and it can generate images that are visually similar to the private images in the InstaHide challenge dataset. Luo et al. (2021) provides the first heuristic-based practical attack for the InstaHide challenge (kpriv = 2) when data augmentation is enabled.
Although the InstaHide challenge is considered broken by several researchers, the current InstaHide challenge is itself too simple, and it is unclear whether the existing attacks Carlini
et al. (2020); Luo et al. (2021) can still work when we use InstaHide to protect large numbers of private images (large n) Arora (2020).
This raises an important question:
What’s the minimal number of InstaHide images needed to recover a private image?
This question is worthwhile to consider because it is a quantitative measure for how secure InstaHide is. With the same formulation in Chen et al. (2021), we achieve a better upper bound on the number of samples needed to recover private images when kpriv = 2. Our new algorithm can recover all the private images using only Ω(npriv log(npriv)) samples.1 This significantly improves the state-of-the-art theoretical results Chen et al. (2021) that requires n 4/3 priv samples to recover a single private image. However, our running time is exponential in the number of private images (npriv) and polynomial in the number of public images (npub), where the running time of the algorithm in Chen et al. (2021) is polynomial in npriv and npub. In addition, we provide a four-step framework to compare our attacks with the attacks presented in Carlini et al. (2020) and Chen et al. (2021). We hope our framework can inspire more efficient attacks on InstaHide-like approaches and can guide the design of future-generation deep learning algorithms on sensitive data.

heading: 1.1 Our result
text: Chen et al. (2021) formulates the InstaHide attack problem as a recovery problem that given sample access to an oracle that can generate as much as InstaHide images you want, there are two goals : 1) sample complexity, minimize the number InstaHide images being used, 2) running time, use those InstaHide images to recover the original images as fast as possible.
Similar to Chen et al. (2021), we consider the case where private and public data vectors are Gaussians. Let Spub denote the set of public images with |Spub| = npub, let Spriv denote the set of private images with |Spriv| = npriv. The model that produces InstaHide image can be described as follows:
• Pick kpub vectors from public data set and kpriv vectors from private data set. • Normalize kpub vectors by 1/ √ kpub and normalize kpriv vectors by 1/ √ kpriv.
• Add kpub + kpriv vectors together to obtain a new vector, then flip each coordinate of that new vector independently with probability 1/2.
We state our result as follows: Theorem 1.1 (Informal version of Theorem 3.1). Let kpriv = 2. If there are npriv private vectors and npub public vectors, each of which is an i.i.d. draw from N (0, Idd), then as long as
d = Ω(poly(kpub) log(npub + npriv)),
there is some m = O(npriv log npriv) such that, given a sample of m random synthetic vectors independently generated as above, one can exactly recover all the private vectors in time
O(dm2 + dn2pub + n 2ω+1 pub +mn 2 pub) + d2 O(m)
with high probability.
Notations. For any positive integer n, we use [n] to denote the set {1, 2, · · · , n}. For a set S, we use supp(S) to denote the support of S, i.e., the indices of its elements. We also use supp(w) to denote the support of vector w ∈ Rn, i.e. the indices of its non-zero coordinates. For a vector x, we use ‖x‖2 to denotes entry-wise `2 norm. For two vectors a and b, we use a ◦ b to denote a vector where i-th entry is aibi. For a vector a, we use |a| to denote a vector where the i-th entry is |ai|. Given a vector v ∈ Rn and a subset S ⊂ [n] we use [v]S ∈ R|S| to denote the restriction of v to the coordinates indexed by S.
1For the worst case distribution, Ω(npriv) is a trivial sample complexity lower bound.
Contributions. Our contributions can be summarized into the following folds.
• We propose an algorithm that recover all the private images using only Ω(npriv log(npriv)) samples in the recent theoretical framework of attacking InstaHide Huang et al. (2020b) when mixing two private image, improving the state-of-art result of Chen et al. (2021).
• We summarize existing methods of attacking InstaHide into a unifying framework. By examining the functionality of each steps we identify the connection of a key step with problems in graph isomorphism. We also reveal the vulnerability of existing method to recover all private images by showing hardness to recover all images.
Organizations. In Section 2 we formulate our attack problem. In Section 3 we present our algorithm and main results. In Section 4 we conclude our paper and discuss future directions.

heading: 2 Preliminaries
text: We use the same setup as Chen et al. (2021). Definition 2.1 (Image matrix notation, Definition 2.2 in Chen et al. (2021)). Let image matrix X ∈ Rd×n be a matrix whose columns consist of vectors x1, . . . , xn ∈ Rd corresponding to n images each with d pixels taking values in R. It will also be convenient to refer to the rows of X as p1, . . . , pd ∈ Rn.
We define public set, private set and synthetic images following the setup in Huang et al. (2020b). Definition 2.2 (Public/private notation, Definition 2.3 in Chen et al. (2021)). We will refer to Spub ⊂ [n] and Spriv = [n]\Spub as the set of public and private images respectively, and given a vector w ∈ Rn, we will refer to supp(w) ∩ Spub and supp(w) ∩ Spriv as the public and private coordinates of w respectively. Definition 2.3 (Synthetic images, Definition 2.4 in Chen et al. (2021)). Given sparsity levels kpub ≤ |Spub|, kpriv ≤ |Spriv|, image matrix X ∈ Rd×n and a selection vector w ∈ Rn for which [w]Spub and [w]Spriv are kpub- and kpriv-sparse respectively, the corresponding synthetic image is the vector yX,w = |Xw| ∈ Rd where | · | denotes entrywise absolute value. We say that X ∈ Rd×n and a sequence of selection vectors w1, . . . , wm ∈ Rn give rise to a synthetic dataset Y ∈ Rm×d consisting of the images (yX,w1 , . . . , yX,wm)>.
We consider Gaussian image which is a common setting in phase retrieval Candes et al. (2013); Netrapalli et al. (2017); Candes et al. (2015). Definition 2.4 (Gaussian images, Definition 2.5 in Chen et al. (2021)). We say that X is a random Gaussian image matrix if its entries are sampled i.i.d. from N (0, 1).
Distribution over selection vectors follows from variants of Mixup Zhang et al. (2017). Here we `2 normalize all vectors for convenience of analysis. Since kpriv is a small constant, our analysis can be easily generalized to other normalizations. Definition 2.5 (Distribution over selection vectors, Definition 2.6 in Chen et al. (2021)). Let D be the distribution over selection vectors defined as follows. To sample once from D, draw random subset T1 ⊂ Spub, T2 ⊆ Spriv of size kpub and kpriv and output the unit vector whose i-th entry is 1/ √ kpub if i ∈ T1, 1/ √ kpriv if i ∈ T2, and zero otherwise.2
For convenience we will define pub and priv operators as follows, Definition 2.6 (Public/private operators). We define function pub(·) and priv(·) such that for vector w ∈ Rn, pub(w) ∈ Rnpub will be the vector which only contains the coordinates of w corresponding to the public subset Spub, and priv(w) ∈ Rnpriv will be the vector which only contains the coordinates of w corresponding to the private subset Spriv.
2Note that any such vector does not specify a convex combination, but this choice of normalization is just to make some of the analysis later on somewhat cleaner, and our results would still hold if we chose the vectors in the support of D to have entries summing to 1.
Algorithm 1 Recovering All Private Images when kpriv = 2
1: procedure RecoverAll(Y) . Theorem 3.1, Theorem 1.1 2: . InstaHide dataset Y = (yX,w1 , . . . , yX,wm)> ∈ Rm×d 3: . Step 1. Retrieve Gram matrix 4: M← 1
kpriv+kpub ·GramExtract(Y, 1 2(kpub+kpriv) ) . Algorithm 1 in Chen et al. (2021)
5: . Step 2. Subtract Public images from Gram matrix 6: for i ∈ [m] do 7: Si ← LearnPublic({(pj)Spub , y X,wi j )}j∈[d]) . Algorithm 2 in Chen et al. (2021)
8: end for 9: Wpub ← (pub(vec(S1)), . . . , pub(vec(Sm)))> . Wpub ∈ {0, 1}m×npub 10: Mpriv ← kpriv · (M− 1kpubWpubW > pub) 11: . Step 3. Assign original images 12: Wpriv ← AssigningOriginalImages(Mpriv, npriv) . Algorithm 2 13: . Step 4. Solving system of equations. 14: Ypub = 1√
kpub WpubX
> pub . Xpub ∈ Rd×npub , Ypub ∈ Rm×d, Wpub ∈ {0, 1}m×npub 15: X̃ ← SolvingSystemofEquations(Wpriv, √ kprivYpub, √
kprivY) . Algorithm 3 16: return X̃ 17: end procedure
For subset S̃ ⊂ S we will refer to vec(S̃) ∈ Rn as the vector that vec(S̃)i = 1 if i ∈ S̃ and vec(S̃)i = 0 otherwise. We define the public and private components of W and Y for convenience. Definition 2.7 (Public and private components of image matrix and selection vectors). For a sequence of selection vectors w1, . . . , wm ∈ Rn we will refer to
W = (w1, . . . , wm) > ∈ Rm×n
as the mixup matrix.
Specifically, we will refer to Wpub ∈ {0, 1}m×npub as the public component of mixup matrix and Wpriv ∈ {0, 1}m×npriv as the private component of mixup matrix, i.e.,
Wpub = √ kpub ·   pub(W1,∗)
... pub(Wm,∗)
  ∈ {0, 1}m×npub ,Wpriv = √ kpriv ·   priv(W1,∗)
... priv(Wm,∗)
  ∈ {0, 1}m×npriv .
We will refer to Xpub ∈ Rd×npub as public component of image matrix which only contains the columns of X ∈ Rd×n corresponding to the public subset Spub, and Xpriv ∈ Rd×npriv as private component of image matrix which only contains the columns of X ∈ Rd×n corresponding to the private subset Spriv.
Furthermore we define Ypub ∈ Rm×d as public contribution to InstaHide images and Ypriv ∈ Rm×d as private contribution to InstaHide images:
Ypub = 1√ kpub WpubX > pub, Ypriv = 1√ kpriv WprivX > priv.
Instead of considering only one private image recovery as Chen et al. (2021), here we consider a harder question which requires to recover all the private images.
Problem 1 (Exact Private image recovery). Let X ∈ Rd×n be a Gaussian image matrix. Given access to the public images {xs}s∈Spub and the synthetic dataset (yX,w1 , . . . , yX,wm), where w1, . . . , wm ∼ D are unknown selection vectors, output a set of vectors {x̃s}s∈Spriv for which there exists a one-to-one mapping φ from {x̃s}s∈Spriv to {xs}s∈Spriv satisfying φ(x̃s)j = (xs)j, ∀j ∈ [d].
3 Recovering All Private Images when kpriv = 2
In this section, we prove our main algorithmic result. Our algorithm follows the high-level procedure introduced in section A. The details are elaborated in following subsections.
Theorem 3.1 (Main result). Let Spub ⊂ [n], and let npub = |Spub| and npriv = |Spriv|. Let kpriv = 2. Let k = kpriv + kpub. If d ≥ Ω ( poly(kpub, kpriv) log(npub + npriv) ) and m ≥ Ω ( kpoly(kpriv)npriv log npriv ) , then with high probability over X and the sequence of randomly chosen selection vectors w1, . . . , wm ∼ D, there is an algorithm which takes as input the synthetic dataset Y> = (yX,w1 , . . . , yX,wm) ∈ Rd×m and the columns of X indexed by Spub, and outputs npriv images {x̃s}s∈Spriv for which there exists one-to-one mapping φ from {x̃s}s∈Spriv to {xs}s∈Spriv satisfying φ(x̃s)j = (xs)j for all j ∈ [d]. Furthermore, the algorithm runs in time
O(m2d+ dn2pub + n 2ω+1 pub +mn 2 priv + 2 m ·mn2privd).
Remark 3.2. Our result improves on Chen et al. (2021) on two aspects. First, we reduce the sample complexity from nkpriv−2/(kpriv+1)priv to npriv log npriv when kpriv = 2. Note that our sample complexity is optimal up to logarithmic factors since finding unique solutions of linear system requires at least npriv sample complexity. Second, we can recover all private images exactly rather than recovering a single image, which is highly desirable for real-world practitioners. Furthermore notice that fixing all public images, multiplying any private image by −1 might not keep InstaHide images unchanged. Thus information theoretically, we are able to recover all private images precisely (not only absolute values) as long as we have access to sufficient synthetic images. In fact, from the proof of Lemma 3.7 our sample complexity suffices to achieve exact recovery.

heading: 3.1 Retrieving Gram matrix
text: In this section, we present the algorithm for retrieving the Gram matrix.
Lemma 3.3 (Retrieve Gram matrix, Chen et al. (2021)). Let n = npub + npriv. Suppose d = Ω(log(m/δ)/η4). For a random Gaussian image matrix X ∈ Rd×n and arbitrary w1, . . . , wm ∈ Sd−1≥0 , let Σ∗ be the output of GramExtract when we set η = 1/2k. Then with probability 1 − δ over the randomness of X, we have that Σ∗ = k ·WW> ∈ Rm×m. Furthermore, GramExtract runs in time O(m2d).
We briefly describe how this is achieved. Without loss of generality, we may assume Spriv = [n], since once we determine the support of public images Spub, we can easily subtract the contribution of them. Consider a matrix Y ∈ Rm×d whose rows are yX,w1 , . . . , yX,wm . Then, it can be written as
Y =   |〈p1, w1〉| · · · |〈pd, w1〉| ... . . .
... |〈p1, wm〉| · · · |〈pd, wm〉|.
 
Since X is a Gaussian matrix, we can see that each column of Y is the absolute value of an independent draw of N (0,WW>). We define this distribution as N fold(0,WW>), and it can be proved that the covariance matrix of N fold(0,WW>) can be directly related WW>. Then, the task becomes estimating the covariance matrix of N fold(0,WW>) from d independent samples (columns of Y), which can be done by computing the empirical estimates.

heading: 3.2 Remove public images
text: In this section, we present the algorithm of subtracting public images from Gram matrix. Formally, given any synthetic image yX,w we recover the entire support of [w]Spub (essentially supp([w]Spub)).
Lemma 3.4 (Subtract public images from Gram matrix, Chen et al. (2021)). Let n = npriv + npub. For any δ ≥ 0, if d = Ω(poly(kpub)/ log(n/δ)), then with probability at least 1− δ over the randomness of X, we have that the coordinates output by LearnPublic are exactly equal to supp([w]Spub). Furthermore, LearnPublic runs in time O(dn2pub + n 2ω+1 pub ), where ω ≈ 2.373 is the exponent of matrix multiplication Williams (2012).
Note that this problem is closely related to the Gaussian phase retrieval problem. However, we can only access the public subset of coordinates for any image vector pi. We denote these partial vectors as {[pi]Spub}i∈[d]. The first step is to construct a matrix M̃ ∈ Rnpub×npub :
M̃ = 1
d
d∑
i=1
((yX,wi ) 2 − 1) · ([pi]Spub [pi]>Spub − I).
It can be proved that when pi’s are i.i.d standard Gaussian vectors, the expectation of M̃ is M = 12 [w]Spub [w] > Spub
. However, when d n, M̃ is not a sufficiently good spectral approximation of M, which means we cannot directly use the top eigenvector of M̃. Instead, with high probability [w]Spub can be approximated by the top eigenvector of the solution of the following semi-definite programming (SDP):
max Z 0
〈M̃, Z〉 s.t. tr[Z] = 1, npub∑
i,j=1
|Zi,j | ≤ kpub.
Hence, the time complexity of this step is O(dn2pub + n 2ω+1 pub ), where the first term is the time
cost for constructing M̃ and the second term is the time cost for SDP Jiang et al. (2020).

heading: 3.3 Assigning encoded images to original images
text: We are now at the position of recovering Wpriv ∈ Rm×npriv from private Gram matrix Mpriv ∈ Rm×m. Recall that Mpriv = WprivW>priv ∈ Rm×m where Wpriv ∈ {0, 1}m×npriv is the mixup matrix with column sparsity kpriv. By recovering mixup matrix W from private Gram matrix M the attacker maps each synthetic image yX,wi , i ∈ [m] to two original images xi1 , . . . , xikpriv (to be recovered in the next step) in the private data set, where kpriv = 2.
On the other hand, in order to recover original image xi from private data set, the attacker needs to know precisely the set of synthetic images yX,wi , i ∈ [m] generated by xi. Therefore this step is crucial to recover the original private images from InstaHide images. We provide an algorithm and certify that it outputs the private component of mixup matrix with sample complexity m = Ω(npriv log npriv).
As noted by Chen et al. (2021), the intricacy of this step lies in the fact that a family of sets may not be uniquely identifiable from the cardinality of all pairwise intersections. This problem is formally stated in the following.
Problem 2 (Recover sets from cardinality of pairwise intersections). Let Si ⊂ [n], i ∈ [m] be n sets with cardinality k. Given access to the cardinality of pairwise intersections |Si ∩ Sj | for all i, j ∈ [m], output a family of sets S̃i ⊂ [n], i ∈ [m] for which there exists a one-to-one mapping φ from S̃i, i ∈ [m] to Si, i ∈ [m] satisfying φ(S̃j) = Sj for all j ∈ [m].
In real world applications, attackers may not even have access to precise cardinality of pairwise intersections |Si ∩ Sj | for all i, j ∈ [m] due to errors in retrieving Gram matrix and public coordinates. Instead, attackers often face a harder version of the above problem, where they only know whether |Si ∩ Sj | is an empty set for i, j ∈ [m]. However for mixing two private images, the two problems are the same.
We now provide a solution to this problem. First we define a concept closely related to the above problem.
Algorithm 2 Assigning Original Images 1: procedure AssigningOriginalImages(Mpriv, npriv) 2: . Mpriv ∈ Rm×m is Private Gram matrix, npriv is the number of private images 3: MG ←Mpriv − I 4: if npriv < 5 then 5: for H ∈ {0, 1}npriv×npriv do 6: MH ← adjacency matrix of the line graph of H 7: if MH = MG then 8: W̃← W̃ ∪ {WH} . WH is the incidence matrix of H 9: end if 10: end for 11: return W̃ 12: end if 13: Reconstruct G from MG . By Theorem C.2 14: return W . The incidence matrix of G 15: end procedure
Definition 3.5 (Distinguishable). For matrix M ∈ Rm×m, we say M is distinguishable if there exists unique solution W = (w1, . . . , wm)> (up to permutation of rows) to the equation WW> = M such that wi ∈ supp(Dpriv) for all i ∈ [m]. Lemma 3.6 (Assign InstaHide images to the original images). When m = Ω(npriv log npriv), let Wpriv = (w1, . . . , wm)> where wi, i ∈ [m] are sampled from distribution Dpriv and Mpriv = WprivW > priv ∈ Rm×m. Then with high probability Mpriv is distinguishable and algorithm AssigningOriginalImages inputs private Gram matrix Mpriv ∈ {0, 1, 2}m×m correctly outputs Wpriv ∈ {0, 1}m×npriv with row sparsity kpriv = 2 such that WprivW>priv = Mpriv. Furthermore AssigningOriginalImages runs in time O(mnpriv).
The proof of Lemma 3.6 is deferred to Appendix C. We consider graph G = (V,E), |V | = npriv and |E| = m where each vi ∈ V corresponds to an original image in private data set and each e = (vi, vj) ∈ E correspond to an encrypted image generated from two original images corresponding to vi and vj . We define the Gram matrix of graph G = (V,E), denoted by MG ∈ {0, 1, 2}m×m where m = |E|, to be MG = WW> − I where W ∈ {0, 1}m×npriv is the incidence matrix of G. That is 3
MG =   |e1 ∩ e1| · · · |e1 ∩ em| ... . . .
... |em ∩ e1| · · · |em ∩ em|
  ∈ {0, 1, 2}m×m.
We can see thatMG actually correspond the line graph L(G) of the graph G. We similarly call a graph G distinguishable if there exists no other graph G′ such that G and G′ have the same Gram matrix (up to permutations of edges), namely MG = MG′ (for some ordering of edges). To put it into another word, if we know MG, we can recover G uniquely. Therefore, recovering W from M can be viewed as recovering graph G from its Gram matrix MG ∈ Rm×m, and a graph is distinguishable if and only if its Gram matrix MG is distinguishable.
This problem was studied since the 1970s and fully resolved by Whitney Whitney (1992). In fact, from a line graph L(G) one can first identify a tree of the original graph G and then proceed to recover the whole graph. The proof is then completed from well-known facts in random graph theory Erdős & Rényi (1960) that G is connected with high probability when m = Ω(npriv log npriv). This paradigm can potentially be extended to handle k ≥ 3 case with more information of G. Intuitively, this is achievable for a dense subgraph of G, such as the local structure identified by Chen et al. (2021). More discussion can be found in Appendix C.

heading: 3.4 Solving a large system of equations
text: In this section, we solve the step 4, recovering all private images by solving an `2-regression problem. Formally, given mixup coefficients Wpriv (for private images) and contributions to
3With high probability, W will not have multi-edge. So, most entries of M will be in {0, 1}.
InstaHide images from public images Ypub we recover all private images Xpriv (up to absolute value). Lemma 3.7 (Solve `2-regression with hidden signs). Given Wpriv ∈ Rm×npriv and Ypub,Y ∈ Rm×d. For each i ∈ [d], let Y∗,i ∈ Rm denote the i-th column of Y and similarily for Ypub∗,i, the following `2 regression
min zi∈Rnpriv
‖|Wprivzi + Ypub∗,i| −Y∗,i‖2.
for all i ∈ [d] can be solve by SolvingSystemOfEquations in time O(2m ·mn2priv · d).
Proof. Suppose Wpriv = [w1 w2 · · · wm]>. Then, the `2-regression we considered actually minimizes
m∑
j=1
(|w>j zi + Ypubj,i| −Yj,i)2 = m∑
j=1
(w>j zi + Ypubj,i − σj ·Yj,i)2,
where σj ∈ {−1, 1} is the sign of wjz∗i for the minimizer z∗i . Therefore, in Algorithm 3, we enumerate all possible σ ∈ {±1}m. Once σ is fixed, the optimization problem becomes the usual `2-regression, which can be solved in O(nωpriv+mn 2 priv) time. Since we assume m = Ω(npriv log(npriv)) in the previous step, the total time complexity is O(2m ·mn2priv). If sign(Wprivz + Ypub∗,i) = σ holds for z = minz∈Rnpriv ‖Wprivz + Ypub∗,i − σ ◦Y∗,i‖2, then∑m j=1(|w>j zi +Ypubj,i| −Yj,i)2 = 0 and z is the unique minimizer of the signed `2-regression problem almost surely.
Indeed, if we have for σ 6= σ̃, Wpriv(X>priv)∗,i + Ypub∗,i − σ ◦Y∗,i = 0 and Wprivz̃ + Ypub∗,i − σ̃ ◦Y∗,i = 0 hold, then from direct calculations we come to Wprivz̃ = σ ◦ σ̃ ◦ (Wpriv(X>priv)∗,i + Ypub∗,i)−Ypub∗,i. This indicates that σ ◦ σ̃ ◦ (Wpriv(X>priv)∗,i + Ypub∗,i)−Ypub∗,i lies in a npriv-dimensional subspace of Rm. Noting that (X>priv)j,i and Ypubj,i are i.i.d sampled from Gaussian, the event above happens with probability zero since m npriv. Thus, we can repeat this process for all i ∈ [d] and solve all zi’s.
We also show that `2-regression with hidden signs is in fact a very hard problem. Although empirical methods may bypass this issue by directly applying gradient descent, real world practitioners taking shortcuts would certainly suffer from a lack of apriori theoretical guarantees when facing a large private dataset. Theorem 3.8 (Lower bound of `2-regression with hidden signs, informal version of Theorem D.4.). There exists a constant > 0 such that it is NP-hard to (1 + )-approximate minz∈Rn ‖|Wz| − y‖2, where W ∈ {0, 1}m×n is row 2-sparse and y ∈ {0, 1}m.
We will reduce the MAX-CUT problem to the `2-regression. MAX-CUT is a well-known NP-hard problem Berman & Karpinski (1999). A MAX-CUT instance is a graph G = (V,E) with n vertices and m edges. The goal is to find a subset of vertices S ⊆ V such that the number of edges between S and V \S is maximized, i.e., maxS⊆V |E(S, V \S)|. We can further assume G is 3-regular, that is, each vertex has degree 3. The full proof is deferred to Appendix D.

heading: 3.5 Putting everything together
text: Now we are in the position to prove Theorem 3.1.
Proof. By Lemma 3.3 the matrix computed in Line 4 satisfies M = WW>. By Lemma 3.4, Line 7 correctly computes the indices of all public coordinaes of wi, i ∈ [m]. Therefore from
M = WW> = WprivW > priv/kpriv + WpubW > pub/kpub,
Algorithm 3 Solving a large system of equations
1: procedure SolvingSystemOfEquations(Wpriv,Ypub,Y) 2: . Wpriv ∈ Rm×npriv ,Ypub ∈ Rm×d,Y ∈ Rm×d 3: for i = 1→ d do 4: x̃i ← ∅ 5: for σ ∈ {−1,+1}m do 6: z ← minz∈Rnpriv ‖Wprivz + Ypub∗,i − σ ◦Y∗,i‖2 7: if sign(Wprivz + Ypub∗,i) = σ then 8: x̃i ← x̃i ∪ z 9: end if 10: end for 11: end for 12: X̃ ← {x̃1, · · · , x̃d} 13: return X̃ 14: end procedure
the Gram matrix computed in Line 10 satisfies Mpriv = WprivW>priv.
We can now apply Lemma 3.6 to find the private components of mixup weights. Indeed, the output of Line 12 is exactly
Wpriv = kpriv ·   priv(W1,∗)
... priv(Wm,∗)
  ∈ {0, 1}m×npriv .
Based on the correctness of private weights, the output in Line 15 is exactly all private images by Lemma 3.7. This completes the proof of correctness of Algorithm 1.
By Lemma 3.3, Line 4 takesO(m2d) time. By Lemma 3.4 Line 7 runs in timeO(dn2pub+n 2ω+1 pub ). By Lemma 3.6 private weights can be computed in time mnpriv. Line 10 and Line 14 can be computed efficiently in time O(mω). Finally Line 15 is computes in time O(2m ·mn2priv · d) by Lemma 3.7. Combining all these steps we have that the total running time of Algorithm 1 is bounded by O(m2d+ dn2pub + n 2ω+1 pub +mn 2 priv + 2 m ·mn2privd).

heading: 4 Conclusion and Future Work
text: We show that Ω(npriv log npriv) samples suffice to recover all private images under the current setup for InstaHide challenge of mixing two private images. We show that a key step in attacking procedure can be formulated as a problem of graph isomorphism and prove the uniqueness and hardness of recovery. Our approach has significantly advanced the state-ofthe-art approach Chen et al. (2021) that requires n4/3priv samples to recover a single private image. In addition, we present a theoretical framework to reason about the similarities and differences of existing attacks Carlini et al. (2020); Chen et al. (2021) and our attack on Instahide.
Based on our framework, there are several interesting directions for future study:
• How to generalize our result to recover all private images when mixing more than two private images?
• How to extend this framework to analyze multi-task phase retrieval problem with real-world data?
Real-world security is not a binary issue. We hope that our theoretical contributions shed light on the discussion of safety for distributed training algorithms and provide inspirations for the development of better practical privacy-preserving machine learning methods.

heading: 5 Ethics Statement
text: Our work can potentially create negative societal impacts because our theoretical results can inspire new efficient practical attack methods to machine learning models protected by InstaHide.

heading: 6 Reproducibility Statement
text: This is a theory paper. We explicitly stated our assumptions and we provided the complete proofs in supplementary materials.

heading: A A Unified Framework to Compare with Existing Attacks
text: Our attack algorithm (Algorithm 1) contains four steps for kpriv = 2. We can prove m = O(npriv log(npriv)) suffices for exact recovery. Our algorithm shares similarities as two recent attack results : one is a practical attack Carlini et al. (2020), the other is a theoretical attack Chen et al. (2021). In the next few paragraphs, we describe our attack algorithm in four major steps. For each step, we also give a comparison with the corresponding step in Carlini et al. (2020) and Chen et al. (2021).
• Step 1. Section 3.1. Recover the Gram matrix M = WW> ∈ Rm×m of mixup weights W from synthetic images Y. This Gram matrix contains all inner products of mixup weights 〈wi, wj〉. Intuitively this measures the similarity of each pair of two synthetic images and is a natural start of all existing attacking algorithms.
– For this step, Carlini et al. (2020)’s attack uses a pre-trained neural network on public dataset to construct the Gram matrix.
– For this step, note that Y follows folded Gaussian distribution whose covariance matrix is directly related to M. We can thus solve this step by estimating the covariance of a folded Gaussian distribution. This is achieved by using Algorithm 2 in Chen et al. (2021). It takes O(m2d) time.
• Step 2. Section 3.2. Recover all public image coefficients and substract the contribution of public coefficients from Gram matrix M to obtain Mpriv. This step is considered as one of the main computational obstacle for private image recovery.
– For this step, Carlini et al. (2020)’s attack: 1) they treat public images as noise, 2) they don’t need to take care of the public images’ labels, since current InstaHide Challenge doesn’t provide label for public images.
– For this step, we invoke a paradigm in sparse phase retrieval via using general SDP solver to approximate the principle components of the Gram matrix of public coefficients. Chen et al. (2021) proved that this method exactly outputs all public coefficients. The time of this step has two parts : 1) formulating the matrix, which takes dn2pub, 2) solving a SDP with n 2 pub × n2pub size matrix
variable and O(n2pub) constraints, which takes n 2ω+1 pub time Jiang et al. (2020); Huang et al. (2021), where ω is the exponent of matrix multiplication.
• Step 3. Section 3.3. Recover private coefficients Wpriv ∈ Rm×npriv from private Gram matrix Mpriv (Mpriv = WprivW>priv), this step takes O(m · n2priv) time. – For this step, Carlini et al. (2020)’s attack uses K-means to figure out cliques
and then solves a min-cost max flow problem to find the correspondence between InstaHide image and original image (see Appendix B for detailed discussions).
– For this step Chen et al. (2021) starts by finding a local structure called “floral matrix” in the Gram matrix. They prove the existence of this local structure whenm ≥ nkpriv−2/(kpriv+1)priv . Then Chen et al. (2021) can recover private coefficients within that local structure using nice combinatorial properties of the “floral matrix”.
– For this step, we note the fact that in kpriv = 2 case the mixup matrix corresponds to the incident matrix of a graph G and the Gram matrix corresponds to its line graph L(G) (while kpriv ≥ 3 cases correspond to hypergraphs). We can then leverage results in graph isomorphism theory to recover the all private coefficients. In particular, when m ≥ Ω(npriv log npriv) the private coefficients are uniquely identifiable from the Gram matrix.
• Step 4. Section 3.4. Solve d independent `2-regression problems to find private images Xpriv. Given Wpriv ∈ Rm×npriv and Y ∈ Rm×d. For each i ∈ [d], let Y∗,i ∈ Rm denote the i-th column of Y, we need to solve the following `2 regression
min z∈Rnpriv
‖|Wprivz + Ypub∗,i| − |Y∗,i|‖2.
The classical `2 regression can be solved in an efficient way in both theory and practice. However, here we don’t know the random signs and we have to consider all 2m possibilities. In fact we show that solving `2 regression with hidden signs is NP-hard. – For this step, Carlini et al. (2020)’s attack is a heuristic algorithm that uses
gradient descent. – For this step, we enumerate all possibilities of random signs to reduce it to
standard `2 regressions. Chen et al. (2021)’s attack is doing the exact same thing as us. However, since their goal is just recovering one private image (which means m = O(k2)) they only need to guess 2k 2 possibilities.

heading: B Summary of the Attack by Carlini et al. Carlini et al. (2020)
text: This section summarizes the result of Carlini et al, which is an attack of InstaHide when kpriv = 2. Carlini et al. (2020). We first briefly describe the current version of InstaHide Challenge. Suppose there are npriv private images, the InstaHide authors Huang et al. (2020b) first choose a parameter T , this can be viewed as the number of iterations in the deep learning training process. For each t ∈ [T ], Huang et al. (2020b) draws a random permutation πt : [npriv] → [npriv]. Each InstaHide image is constructed from a private image i, another private image πt(i) and also some public images. Therefore, there are T · npriv InstaHide images in total. Here is a trivial observation: each private image shown up in exactly 2T InstaHide images (because kpriv = 2). The model in Chen et al. (2021) is a different one: each InstaHide image is constructed from two random private images and some random public images. Thus, the observation that each private image appears exactly 2T does not hold. In the current version of InstaHide Challenge, the InstaHide authors create the InstaHide labels (a vector that lies in RL where the L is the number of classes in image classification task) in a way that the label of an InstaHide image is a linear combination of labels (i.e., one-hot vectors) of the private images and not the public images. This is also a major difference compared with Chen et al. (2021). Note that Carlini et al. (2020) won’t be confused about, for the label of an InstaHide image, which coordinates of the label vector are from the private images and which are from the public images.
• Step 1. Recover a similarity4 matrix M ∈ {0, 1, 2}m×m. – Train a deep neural network based on all the public images, and use that neural network to construct the similarity matrix M. • Step 2. Treat public image as noise. • Step 3. Clustering. This step is divided into 3 substeps. The first substep uses the similarity matrixM to construct Tnpriv clusters of InstaHide images based on each InstaHide image such that the images inside one cluster shares a common original image. The second substep runs K-means on these clusters, to group clusters into npriv groups such that each group corresponds to one original image.
4In Carlini et al. (2020), they call it similarity matrix, in Chen et al. (2021) they call it Gram matrix. Here, we follow Carlini et al. (2020) for convenience.
The third substep constructs a min-cost flow graph to compute the two original images that each InstaHide image is mixed from.
– Grow clusters. Figure 1 illustrates an example of this step. For a subset S of InstaHide images (S ⊂ [m]), we define insert(S) as
Insert(S) = S ∪ arg max i∈[m]
∑ j∈S Mi,j
For each i ∈ [m], we compute set Si ⊂ [m] where Si = insert(T/2)({i}). – Select cluster representatives. Figure 1 illustrates an example of this step.
Define distance between clusters as
dist(i, j) = |Si ∩ Sj | |Si ∪ Sj | .
Run k-means using metric dist : [m] × [m] → R and k = npriv. Result is npriv groups C1, . . . , Cnpriv ⊆ [m]. Randomly select a representative ri ∈ Ci, for each i ∈ [npriv].
– Computing assignments. Construct a min-cost flow graph as Figure 2, with weight matrix W̃ ∈ Rm×npriv defined as follows:
W̃i,j = 1 |Srj | ∑
k∈Srj
Mi,k.
for i ∈ [m], j ∈ [npriv]. After solving the min-cost flow (Figure 3), construct the assignment matrix W ∈ Rm×npriv such that Wi,j = 1 if the edge from i to j has flow, and 0 otherwise.
• Step 4. Recover original image. From Step 3, we have the unweighted assignment matrix W ∈ {0, 1}m×npriv . Before we recover the original image, we need to first recover the weight of mixing, which is represented by the weighted assignment matrix U ∈ Rm×npriv . To recover weight, we first recover the label for each cluster group, and use the recovered label and the mixed label to recover the weight.
– First, we recover the label for each cluster, for all i ∈ [npriv]. Let L denote the number of classes in the classification task of InstaHide application. For j ∈ [m], let yj ∈ RL be the label of j.
label(i) = ⋂
j∈[m],Wj,i=1
supp(yj) ∈ [L].
Then, for i ∈ [m] and j ∈ [npriv] such that Wi,j = 1, define Ui,j = yi,label(j) for | supp(yi)| = 2 and Ui,j = yi,label(j)/2 for | supp(yi)| = 1. Here, W ∈ {0, 1}m×npriv is the unweighted assignment matrix and U ∈ Rm×npriv is the weighted assignment matrix. For Wi,j = 0, let Ui,j = 0. – Second, for each pixel i ∈ [d], we run gradient descent to find the original images. Let Y ∈ Rm×d be the matrix of all InstaHide images, Y∗,i denote the i-th column of Y.5
min z∈Rnpriv
‖|Uz| − |Y∗,i|‖2.

heading: C Missing proofs for Theorem 3.6
text: For simplicity, let W denote Wpriv and M denote Mpriv in this section.
5The description of the attack in Carlini et al. (2020) recovers original images by using gradient descent for minz∈Rnpriv ‖U|z| − |Y∗,i|‖2, which we believe is a typo.
C.1 A graph problem (kpriv = 2)
Theorem C.1 (Whitney (1992)). Suppose G and H are connected simple graphs and L(G) ∼= L(H). If G and H are not K3 and K1,3, then G ∼= H. Furthermore, if |V (G)| ≥ 5, then an isomorphism of L(G) uniquely determines an isomorphism of G.
In other words, this theorem claims that given M = WW>, if the underlying W is not the incident matrix of K3 or K1,3, W can be uniquely identified up to permutation. Theorem C.1 can also be generalized to the case when G has multi-edges Zverovich (1997).
On the other hand, a series of work Roussopoulos (1973); Lehot (1974); Syslo (1982); Degiorgi & Simon (1995); Liu et al. (2015) showed how to efficiently reconstruct the original graph from its line graph: Theorem C.2 (Liu et al. (2015)). Given a graph L with m vertices and t edges, there exists an algorithm that runs in time O(m+ t) to decide whether L is a line graph and output the original graph G. Furthermore, if L is promised to be the line graph of G, then there exists an algorithm that outputs G in time O(m).
With Theorem C.1 and Theorem C.2, Theorem 3.6 follows immediately:
Proof of Theorem 3.6. First, since m = Ω(npriv log(npriv)), a well-known fact in random graph theory by Erdős and Rényi Erdős & Rényi (1960) showed that the graph G with incidence matrix W will almost surely be connected. Then, we compute MG = M− I, the adjacency matrix of the line graph L(G). Theorem C.1 implies that G can be uniquely recovered from MG as long as npriv is large enough. Finally, We can reconstruct G from MG by Theorem C.2.
For the time complexity of Algorithm 2, the reconstruction step can be done in O(m) time. Since we need to output the matrix W, we will take O(mnpriv)-time to construct the adjacency matrix of G. Here, we do not count the time for reading the whole matrix M into memory.
C.2 General case (kpriv > 2)
The characterization of M and W as the line graph and incidence graph can be generalized to kpriv > 2 case, which corresponds to hypergraphs.
Suppose M = WW> with kpriv = k > 2. Then, W can be recognized as the incidence matrix of a k-uniform hypergraph G, i.e., each hyperedge contains k vertices. MG = M− I corresponds to adjacency matrix of the line graph of hypergraph G: (MG)i,j = |ei ∩ ej | for ei, ej being two hyperedges. Now, we can see that each entry of MG is in {0, . . . , k}. Unfortunately, the identification problem becomes very complicated for hypergraphs. Lovász Lovász (1977) stated the problem of characterizing the line graphs of 3-uniform hypergraphs and noted that Whitney’s isomorphism theorem (Theorem C.1) cannot be generalized to hypergraphs. Hence, we may not be able to uniquely determine the underlying hypergraph and we should just consider a more basic problem: Problem C.3 (Line graph recognition for hypergraph). Given a simple graph L = (V,E) and k ∈ N, decide if L is the line graph of a k-uniform hypergraph G.
Even for the recognition problem, it was proved to be NP-complete for fixed k ≥ 3 Levin & Tyshkevich (1993); Poljak et al. (1981). However, Problem C.3 becomes tractable if we add more constraints to the underlying hypergraph G. First, suppose G is a linear hypergraph, i.e., the intersection of two hyperedges is at most one. If we further assume the minimum degree of G is at least 10, i.e., each vertex are in at least 10 hyperedges, there exists a polynomial-time algorithm for the decision problem. Similar result also holds for k > 3 Jacobson et al. (1997). Let the edge-degree of a hyperedge be the number of triangles in the hypergraph containing that hyperedge. Jacobson et al. (1997) showed that assuming the minimum edge-degree of G is at least 2k2 − 3k + 1, there exists a polynomial-time algorithm
to decide whether L is the line graph of a linear k-uniform hypergraph. Furthermore, in the yes case, the algorithm can also reconstruct the underlying hypergraph. We also note that without any constraint on minimum degree or edge-degree, the complexity of recognizing line graphs of k-uniform linear hypergraphs is still unknown.

heading: D Computational Lower Bound
text: The goal of this section is to prove that the `2-regression with hidden signs is actually a very hard problem, even for approximation (Theorem D.4), which implies that Algorithm 3 cannot be significantly improved. For simplicity we consider Spub = ∅. We first state an NP-hardness of approximation result for 3-regular MAX-CUT. Theorem D.1 (Imapproximability of 3-regular MAX-CUT, Berman & Karpinski (1999)). For every > 0, it is NP-hard to approximate 3-regular MAX-CUT within a factor of r + , where r ≈ 0.997.
If we assume the Exponential Time Hypothesis (ETH), which a plausible assumption in theoretical computer science, we can get stronger lower bound for MAX-CUT. Definition D.2 (Exponential Time Hypothesis (ETH), Impagliazzo & Paturi (2001)). There exists a constant > 0 such that the time complexity of n-variable 3SAT is at least 2 n. Theorem D.3 (Fotakis et al. (2016)). Assuming ETH, there exists a constant 0 < r′ < 1 such that no 2o(n)-time algorithm can r′-approximate the MaxCut of an n-vertex, 5-regular graph.
With Theorem D.1 and Theorem D.3, we can prove the following inapproximability result for the `2-regression problem with hidden signs. Theorem D.4 (Lower bound of `2-regression with hidden signs). There exists a constant > 0 such that it is NP-hard to (1 + )-approximate
min z∈Rn
‖|Wz| − y‖2, (1)
where W ∈ {0, 1}m×n is row 2-sparse and y ∈ {0, 1}m. Furthermore, assuming ETH, there exists a constant ′ such that no 2o(n)-time algorithm can ′-approximate Eq. (1).
Proof. Given a 3-regular MAX-CUT instance G, we construct an `2-regression instance (W, y) with W ∈ {0, 1}m′×n and y ∈ {0, 1}m′ where m′ = m + cn = (1 + 3c/2)m and c = 106 as follows.
• For each i ∈ [m], let the i-th edge of G be ei = {u, v}. We set Wi,∗ to be all zeros except the u-th and v-th coordinates being one. That is, we add a constraint |zu+zv|. And we set yi = 0.
• For each j ∈ [n], we set Wm+c(j−1)+1,∗, . . . ,Wm+cj,∗ to be all zero vectors except the j-th entry being one. That is, we add c constraints of the form |zj |. And ym+c(j−1)+1 = · · · = ym+cj = 1.
Completeness. Let opt be the optimal value of max-cut of G and let Sopt be the optimal subset. Then, for each u ∈ Sopt, we set zu = 1; and for u /∈ Sopt, we set zu = −1. For the first type constraints |zu + zv|, if u and v are cut by Sopt, then |zu + zv| = 0; otherwise |zu+ zv| = 2. For the second type constraints |zj |, all of them are satisfied by our assignment. Thus, ‖Wz − y‖22 = 4(m− opt).
Soundness. Let η be a constant such that r < η < 1, where r is the approximation lower bound in Theorem D.1. Let δ = 1−η10c . We will show that, if there exits a z such that ‖Wz − y‖22 ≤ δm′, then we can recover a subset S with cut-size ηm. It is easy to see that the optimal solution lies in [−1, 1]n. Since for z /∈ [−1, 1]n, we can always transform it to a new vector z′ ∈ [−1, 1]n such that ‖Wz′ − y‖2 ≤ ‖Wz − y‖2. Suppose z ∈ {−1, 1}n is a Boolean vector. Then, we can pick S = {i ∈ [n] : zi = 1}. We have the cut-size of S is
|E(S, V \S)| ≥ m− δm′/4 = m− δ(1 + 3c/2)m/4 = (1− δ/4− 3cδ/8)m ≥ ηm,
where the last step follows from δ ≤ 8(1−η)2+6c . For general z ∈ [−1, 1]n, we first round z by its sign: let zi = sign(zi) for i ∈ [n]. We will show that
‖Wz − y‖22 − ‖Wz − y‖22 ≤ 48
c m
which implies
‖Wz − y‖22 = ‖Wz − y‖22 + (‖Wz − y‖22 − ‖Wz − y‖22)
≤ δm′ + 48 c m.
Then, we have the cut-size of S is
|E(S, V \S)| ≥ m− (δm′ − 48m/c)/4 = (1− δ/4− 3cδ/8− 12/c)m ≥ ηm,
where the last step follows from δ ≤ 8(1−η−12/c)2+6c . Let ∆i := |zi − zi| = 1− |zi| ∈ [0, 1]. We have
‖Wz − y‖22 − ‖Wz − y‖22 = m∑
i=1
(zui + zvi) 2 − (zui + zvi)2 + c ·
n∑
j=1
(|zj | − 1)2 − (|zj | − 1)2
=
m∑
i=1
(zui + zvi) 2 − (zui + zvi)2 − c ·
n∑
j=1
(|zj | − 1)2
=
m∑
i=1
(zui + zvi) 2 − (zui + zvi)2 − c ·
n∑
j=1
∆2j
≤ m∑
i=1
4|∆ui + ∆uj | − c · n∑
j=1
∆2j
=
n∑
i=1
12∆i − c∆2i
≤ 72 c n
= 48
c m,
where the first step follows by the construction of W and y. The second step follows from |zj | = 1 for all j ∈ [n]. The third step follows from the definition of ∆j . The forth step follows from |zui + zuj | ∈ [0, 2]. The fifth step follows from the degree of the graph is 3. The fifth step follows from the minimum of the quadratic function 12x− cx2 in [0, 1] is 72c . The last step follows from m = 3n/2.
Therefore, by the completeness and soundness of reduction, if we take ∈ (0, δ), Theorem D.1 implies that it is NP-hard to (1 + )-approximate the `2-regression, which completes the proof of the first part of the theorem.
For the furthermore part, we can use the same reduction for a 5-regular graph. By choosing proper parameters (c and δ), we can use Theorem D.3 to rule out 2o(n)-time algorithm for O(1)-factor approximation. We omit the details since they are almost the same as the first part.

Review summaries:
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.