InstaHide’s Sample Complexity When Mixing Two Private Images 
Authors: Baihe Huang
Zhao Song
Runzhou Tao
Ruizhe Zhang
Danyang Zhuo
Venue: ICLR 2022 Submitted (2022)

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(n_{\mathsf{priv}}^{k_{\mathsf{priv}} - 2/(k_{\mathsf{priv}} + 1)})$ samples to recover one private image in $n_{\mathsf{priv}}^{O(k_{\mathsf{priv}})} + \mathrm{poly}(n_{\mathsf{pub}})$ time for any integer $k_{\mathsf{priv}}$, where $n_{\mathsf{priv}}$ and $n_{\mathsf{pub}}$ 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 ($k_{\mathsf{priv}} = 2$), this means $n_{\mathsf{priv}}^{4/3}$ samples are sufficient to recover a private image. In this work, we show that $n_{\mathsf{priv}} \log ( n_{\mathsf{priv}} )$ samples are sufficient (information-theoretically) for recovering all the private images. 



Under review as a conference paper at ICLR 2022
INSTAHIDE'S SAMPLE COMPLEXITY WHEN MIXING TWO PRIVATE IMAGES
A Anonymous authors Paper under double-blind review
A ABSTRACT
Inspired by InstaHide challenge [Huang, Song, Li and Arora'20), [Chen, Song and Zhuo 200 recently provides one mathematical formulation of InstaHide attack problem under Gaussian images distribution. They show that it suffices to use (nxriv 2/0=2/(( samples to recover one private image in O(kgi))
" priv + poly (ppbb) time for any integer kpriv where ppriv and Ppub denole the number of images used in the private and the public dataset to generate a mixed image sample. Under the current sctup for the InstaHide challenge of 4/3 mixing two private images (kpriv = 2), this means prrv samples are sulficient to recover a private image. In this work, we show that Ppriv log(npriv samples are sufficient (infornation-thhooeetialll for recovering all the private images.
INTRODUCTION
Collaboratively training neural networks based on sensitive data is appealing in many AT applications, such healthcare, fraud detection, and virtual assistants. How train neural networks without compromising data confidentiality and prediction accuracy has become an important and common rescarch goal Shokri & Shmatikov
(2015 Ryffel al. (2018); Phong ct al. (018): McMahan et al. (2017) 1s Konečný et al. (2016) in both academia and industry.
Huang et al. (222b)) 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 mix of kpriv private images and kppb public images, and (2) each pixel is independently sign-flipped after the
mixing. Instahide shows promising prediction accuracy on MNIST Deng (2012). CIPAR-
10 Krizhevsky (2012). 11FAR-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 neriv = 100 private 5000 sample images (each image is
images, TmageNet dataset the public images, combination of lipriv private images and kipb = public images and the sign each pixel randomly flipped). The challenge is to recover a private image given the set of sample images.
Chen et al. 2021 theoretical work that formulates the InstaHide altack problem as recovery problem. It also provides an algorithm to recover a private image assuming each private and public image is random Gaussian image (i.e., each pixel is an i.idd. draw from (0, 1)). The algorithm shows that ( 2pm-2/((pmtt)) sample images are sufficient to priv
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-basok practical attack for the InstaHide challenge (Fipriv = 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

---

Under review as a conference paper at ICLR 2022
et al. (2020) Luo al. (2021) can still work when use InstaHide to protect large numbers of private images (large n) Arora 2020)).
This raises important question:
What's the minimal number of InstaHide images needed to recover private image?
This question worthwhile to consider because is a quantitative measure for how secure InstaHide is. With the same formulation in Chen et al. (2021), we achieve better upper bound on the number of samples needed to recover private images when Apriv = 2. Our new algorithu can recover all the private images using only QM log(Hipny) samples This significantly improves the stale-of-the-arl theoretical results Chen et al. (2021) that requires 4/3
n priv samples to recover a single private image. However, our running time is exponential in the number of private images (Mpriv and polynomial in the number of public images (Npbb); where the running time of the algorithm in Chen et al. (2021) is polynomial in ppriv and pub- In addition, we provide a four-step framework to compare our attacks with the attacks presented in Carlini al. (2020) and Chen et al. (2021). We hope our framework can inspire more efficient attacks on InstaHide- approaches and can guide the design of futurc-generation deep learning algorithms on scnsitive data.
1.1
OUR RESULT
Chen et al. 2021 formulates the InstaHide attack problem recovery problem that given sample access an oracle that can generate as much as InstaHide images you want, there are two goals: 1) sample complexity, minimize the nunber 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 [Spubl = npub: let Spriv denote the set of private images with |Sprivl 7priv. The model that produces InstaHide image be described as follows:
Pick kpub vectors from public data set and kpriv vectors from private data set.
Normalize kpub vectors by 1/ 4/vkpub and normalize kpriv vectors by 1/v 1/Vkpriv
Add kppbb + kipivv 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:
Thcorem 1.1 (Informal version Theorem 3.1 Let lipii = 2. If there are Dariv private vectors and uppb public vectors, each of which i. draw from (0, then long as
d = (u(pooyykkpu log(Npub (ppri));
there is some m ( log ppriv) such that, given sample of random synthetic vectors independently generaled as above, one can exaclly recover all the privale vectors in time
Odmm² 2 + dnuub + n m20t + +mnuub) + (m)
with high probobilily-
Notations. For any positive integer n, we use [m] to denote the set 21, ... ,.. For a set S, supp(S) to denote the support of S, i.c., the indices of its elements. We also use supp(w) to denote the support of vector w E R", , ie. the indices of its non-zero coordinates. For a vector I, we use ||æ||a to denotes entry-wise &g norm. For two vectors and b, we use a b to denote à vector where i-th entry is azb; For a vector we use |a] to denote a vector where the i-th entry is la,l- Given a vector v E R and a subset S C [n] we use [u]s E RIS] to denote the restriction of to the coordinates indexed by S.
For the worst case distribution, (((pr))) is trivial sample complexity lower bound.
2

---

Under review as a conference paper at ICLR 2022
Contributions. Our contributions can be summarized into the following folds.
We propose an algorithm that recover all the private images using only D(nri log (eri)) samples in the recent thcoretical framework of attacking InstaHide Huang el al. (2220b) when mixing two private image, improving the state-of-art resull of Chen el al. 2021).
We summarize cxisting methods of attacking InstaHide into a unifying framework. By examining the functionality of each steps we identify the connection of 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. Section 3 WC present our algorithm and main results. In Scction we conclude our paper and discuss future directions.
PRELIMINARIES
We use the same setup as Chen et al. 2021
Definition 2.1 (Tmage matrix notation, Definition 2.2 Chen et al. (021 ). Let image
matria X E Rdx= be a matriz whose columns consist of vectors 21,.... In E Re corresponding
to n images each with d pizels taking values in R. It will also be convemient to refer to the rows of X as p1....,Pd IK..
We define public set, private set and synthetic images following the setup Huang et al. 2020b)
Definition 2.2 [Public/private notation, Definition 2.3 in Chen al. (0021)). We will refer to Spub C [n] and Spriv = [m]).Spub as the set of public and privale images respectively, and given vector w E IR"", we will refer to supp(w) O Spub and supp(w) O 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 kppb S p Kpriv S |S image malriz X E Raxa and a selection vector w E RRn for which (w) and [w))s,c are kpub- and lipriv -parss respectively, the corresponding synthetic =|
image is the vector =x [xw] E Rd where |-1 denotes entrywise absolute value. We say that X Rdxn and sequence of selection veclors wi,..., Wm Ih" give rise to synthelic datasel Y E RRxx consisling of the images Ky,, X.um
We consider Gaussian image which is common setting in phase retrieval Candes et al. (201)): 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 random Gaussian image matrix if its entries are sampled itddd. from N0,,
Distribution over selection vectors follows from variants of Mixup Zhang et al. 2017 Here we & normalize all vectors for convenience of analysis. Since lipriv 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 al. (022)) h). Let D be the distribution ouer selection vectors defined as follows. To sample once from D, draw random subset Tj C Spub; T2 S Spriv of size kipbb and kepiv and output the unit vector whose i-th entry is 1/ L/Vkn kpub if E Ti, 1/v/ipriv if E T2, and zero otherwise
For convenience we will define pub and priv operators as follows, cuablc/privatee
Definition 2.6 (Public/ private operators). We define function pub(.) and priv(-) such that
for vector w E R", pub(w) E "ma will be the vector which only contains the coortinates of corresponding to the public subset Spub, and priv(w) ) Rr will be the vector which only contains the coordinates of corresponding to the private subset Spriv-
2 Note that any such vector does not specify 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.
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Recovering All Private Images when kipriv 2
1:
procedure RECOVERALL(()
Theorem 3.1 Theorem
2:
> InstaHide dataset Y (y (yx.
E R Raxa
3:
Step 1. Retrieve Gram matrix
4:
M
A GRAMEXTRACT
Algorithm 1 in Chen et al. 2001
2uu + ppris
5:
Step Subtract Public images
from Gram matrix
6:
i E [m] do
7:
S: + LEARNPUBLIC(((E)) MJ "x (e)))))))
P Algorithm Chen et al. 2021
8:
end for
9:
W Wpb + (S1)), pub(vec(Sp)))) ver )))
b Wpub E {0, 1 p
Mpri + lipri (M
W pub
W pub)
Aipub
P. Step Assign original images b Algoritim > Step 4. Solving system of equations.
12:
W priv + ASSINNIGGORGIIAAAAAAEES M Mpric Meprio)
13:
14:
Y pub
W Wps pub
Xpub E Rddanpe
Y pub E max Wppb pub E {0, 10 mpx
VApub
15: X + SONTIGSYSTPMOORQIITTON W pri, Riprio pub,, v Kiprio Y)
b Algorithm
16: return X
17:
end procedure
For subset 5 C S we will refer to vec(S) E Rn the vector that vec(S); 1 if i e S and vec( 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 IR" we will refer
W (....., Wm) T Rmxx
as the mixup matrin.
Specifically, we will refer to Wpbb {0, 13 po as the public component of mizup matria and W priv E {0, 1] maxnge as the private component of mizup matria, i.e.,
1ub(
priv (ii((W1,)) : (W m.+)
W pub
/
kipbb
mxx Wpriv / //ppiiv
E {0,1) m0 mxngi
pub W )m..)
We will refer to X pub E Bdd as public component of image matric which only contains the columns of X E Baxn corresponding to the public subset Spub, and X RRdx private component of image matriz which only contains the columns of X Rdxx corresponding to the privale subsel Spriv-
Furthermore we define Yuu mxd as public contribution InstaHide images and Y priv Rmxd as private contribution to InstaHide images:
Y pub
W
pub
XT
pub:
Y priv
W priv X priv-
/kpub
lipriv
Instead of considering only private image recovery as Chen et al. 2021 here consider a harder question which requires to recover all the private images.
Problem (Exact Private image recovery). Let X E Rdx= be Gaussian image matriz. Given access to the public images (sss)e and the synthetic dalaset Xy........ ..... X.umm. where Wi...., Wm D unknown selection vectors, output set of vectors (Te).sm for which there exists a one-to-one mapping & from (oa) to {xahoesu satisfying o(F.), (xe)i, Vj [d].
4

---

Under review as a conference paper at ICLR 2022
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 [ The details are elaborated in following subsections.
Theorem 3.1 (Main result). Let Spub C [n], and let rdpb = |Spubl and Opriv - S Let hipriv = 2. Let = kipiiv + kipub- If d 2 (ooooyyNepp kipriv) log("pub + ('piv)) and m 2 Ot ((KPoly(Bm))) mpriv log Pepru),, then with high probability over X and the sequence of randomll chosen selection vectors Wi...... Wm DD there is an algorithm which takes as input the synthetic dataset Y (yx."ii... .....9 ....,,"..... (x..i)) E RR and the columns of X indered by Spub; and oulputs "priiv images (EE))ESSW for which there erists one-lo-one mappingg & from { to (ES salisfying ((T,)} [xsss for all j E [d]. Furthermore, the algorillem runs in time
2w++1 O(m d + drpub + pub
+ mmprrvv + 2m mmp
20211 on two aspects. First, we reduce the kpo-2/(kpinn) to rlpriv log Opriv when Kpriv 2. Note that our sample complexity is oplimal up to logarithmicc factors since fonding unique solutions of linear system requires at least ppriv sample complerity. Second, we can recover all private images exactly rather than recovering single image, which is highly desirable for real-world practitioners. Furthermore notice that fizing all public images, multiplying any private image by -1 might not keep InstaHide images unchanged. Thus information theoretically, we are able recover all private images precisely (not only absolute values) as long os we have access to sufficient synthetic images. In fact, from the proof of Lemma 3.7 our somple complexity suffices to achieve eracl recovery.
Remark 3.2. Our result improves on Chen et al.
sample complerity from priv
3.1 RETRIEVING GRAM MATRIX
In this section, present the algorithm for retrieving the Gram matrix.
Lemma 3.3 (Retrieve Gram matrix, Chen al. (2021)). Let пpрb + Reriv- Suppose For random Gaussian image matria X Rdx and arbitrary wi..... Wm E S0-1 let E' be the output of GRAMEXTRACT when we set 17 1/2k. Then with probability 1- - 8 over the randomness of X, we have that E = k. WW E mxx" Furthermore, GRAMEXTRACT runs in time Omm²d).
d (log(mm0))/n))
We briefly describe how this 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 E mgd whose rows are x6,,, ...., x.m. Then, it can be written as
w
Kps, will
Y
KPr, wm)l
Kpa wm)l
Since X is a Gaussian matrix, we can see that each column of Y is the absolute value of an independent draw of (0, WW We define this distribution as Affid WWT), and it can be proved that the covariance matrix of fold WWT) can be directly related WWT. Then, the task becomes estimating the covariance matrix of Told WWT) from d independent samples (columns of Y), which can be done by computing the empirical estimates.
3.2 REMOVE PUBLIC IMAGES
In this section, we present the algorithm of subtracting public images from Gram matrix. Formally, given any synthetic image y X," we recover the entire support of [w]sms (essentially supp([w)s, )m))
5

---

Under review as a conference paper at ICLR 2022
Lemma 3.4 (Subtract public images from Gram matrix, Chen et al. (2021) Let
Opriv + Ppub. For any 2 O, if (ppoly(kpub)/ log(n/6)), then with probability at least 1- - over the randomness of X, we have that the coondinates output by LEARNPUBLIC exactly equal to supp([u)ss.... Porthermore, LEARNPUBLIC runs in time (dn
2w++))
pub + n pub
where w 2 2.373 is the exponent of matriz 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 Pt. We denote these partial vectors as (pplssaaiied) The first step is to construct a matrix M E R RRpbb; R"au"
M 1
E ((0 22) 1)) ((pi)spu [pi]s I). d
d
It can be proved that when pa's are i.id standard Gaussian vectors, the expectation of M is M = {p [ However, when d < n, M is not sufficiently good spectral approximation of M, which means we cannot directly use the top eigenvector of M. Instead, with high probability [w]s can be approximated by the top eigenvector of the solution of the following semi-definite programming (SDP):
max (M, Z) s.t. tr|2] = 1, Zz0
Σ 1-==1
Zin S
Kpub-
Hence, the time complexity of this step is Od + mub 22+t))) where the first term is the time cost for constructing M and the second term is the time cost for SDP Jiang et al. (020))
3.3 ASSIGNING ENCODED IMAGES TO ORIGINAL IMAGES
We are now at the position of recovering W priv E Rmxm from private Gram matrix priv R where W priv {0, 1 is the mixup matrix with column sparsity Kprive By recovering mixup matrix W from private Gram matrix M the attacker maps each synthetic image yx,", i E [m] to two original images Tig.... F (to be recovered in the next step) in the private data set, where kpriv = 2.
Mpriv E mm Recall that M W priv WT
On the other hand, in order to recover original image I; from private data set, the attacker needs to know preciscly the set of synthetic images x.u, [m] generated by z;- 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 = Q(M log N.rri).
As noted by Chen et al. (2021), the intricacy of this step lies in the fact that 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 S, C (n) [m] be n sels with cardinality k. Given access to the cardinality of pairwise intersections S Syj for all i.j E [m], output family of sets S; C [n]. [m]] for which there erists one-to-one mopping from St, [m]] to S,, [m] satisfying o(3,) Sy for all
j e [m].
In real world applications, attackers may not even have access to precise cardinality of pairwise intersections [S, n SyI for all i,j E [m] due to errors in retrieving Gram matrix and public coordinates. Instead, attackers often face harder version of the above problem, where they only know whether |S, n SyI is an empty set for i,j E [m]. However for mixing two private images, the two problems the same.
We now provide a solution to this problem. First we define a concept closely related to the above problem.

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Assigning Original Imagge
1:
procedure ASSICKIGORGINAAAAAAEESS
Teprio)
2:
Mariv Rm is Private Gram matrix, Rariv is the number of private images
3:
Mc t Mari
4: Nari < then
5:
for H E {0, 10,1) 13 do
6:
2 4- adjacency matrix of the line graph of 17
7:
if M Me then
8:
W - WU(WH)
> W is the incidence matrix of H
end if 10: end for
9:
return W
12:
end if
13:
Reconstruct G from Ma
D By Theorem C.2
14:
return W
b The incidence matrix of G
15:
end procedure
Definition 3.5 (Distinguishable). For matrix M R we say M is distinguishable if there exists unique solution W (ww Wm) (up to permutation of rows) to the equation WW M such that w; supp(Dprvv for all i [m].
Lemma 3.6 (Assign InstaHide images to the original images). When m = (i( log Neprio);
let W priv (Wi,..., Wm) where W4, E [m] are sampled from distribution Dpriv and Mpriv priv E Rmxm. Then with high probubilily Mprv is distinguishable and algorithm imputs private Gram matriz Mpriv E 1, 1, correctly outputs W priv E 10.1)m 1p.1) XPir with row sparsity lipiiv = 2 such that W Wpriv WT runs in time O(mmpriv).
W priv WT
AASIGGIIGORRGGINALLAAAGGG
priv Mpriv-
Furthermore ASSIGNINGORGGINIIAA.GG
The proof of Lemma 3.6 is deferred to Appendix C We consider graph G (V, EV,
periv and E = m where each v, E corresponds to an original image in private data set and each (v,, v2) E E correspond to encrypted image generated from two original images corresponding to e and Vy We define the Gram matrix of graph G = (V, E); denoted by MR E {0, 1, mm where m = LE,, to be Mç = WWT where W {0, 1 11mmmxxmmm mxx is the incidence matrix of G. That is
C1 6e
|ei O em
M
m0 mxm
Jem neil
lem n em
We can see that Mg 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 and G have the same Gram matrix (up to permutations of edges), namely Mg Ma (for some ordering of edges). To put it into another word, if we know Mc, we can recover G uniquely. Therefore, recovering W from M can be viewed as recovering graph G from its Gram matrix M2 Rm and graph is distinguishable if and only if its Gram matrix Ma is distinguishable.
This problem
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-knows facts in random graph theory Erdōs & Rényi (1960) that G is connected with high probability when m (nppriv log R.priv). This paradigm can potentially be extended to handle k case with more information of G. Intuitively, this is achievable for dense subgraph of G, such the local structure idiet by Chen et al. (2021). More discussion can found in Appendix
3.4 SOLVING A LARGE SYSTEM OF EQUATIONS
In this section, we solve the step 4, recovering all private images by solving an ly-regression problem. Formally, given mixup coefficients priv (for private images) and contributions to
With high probability, W will not have multi-edge. So, entries of M will be in (0. 1).
7

---

Under review as a conference paper at ICLR 2022
InstaHide images from public images Y pub we recover all private images X Xpriv (up to absolute value).
Lemma 3.7 (Solve f2-regression with hidden signs). Given W priv E Imxx= and Y pub; Y Rmxdd For each [d], let Y. R denote the i-th column of Y and similarily for Y pub.,
the following l2 regression
min SAV
W priv 2i + Y pubb..l Y,,i
for all i [d] can be solue by SONINGSSSTMMOFKUUUTUS
in time 0 mm d).
Proof. Suppose W priv = [wi
W2
Wm] T
Then, the Ez-regression we considered actu-
ally minimizes
E(w 2, + Y pub Y y,,)²
[ 2 pubbji oj Yss)?
where oj E [- is the sign of wyz for the minimizer 2/.
Therefore, in Algorithm 3 we enumerate all possible a E {=1]m. Once a is fixed, the optimization problem becomes the usual fg-regression, which can be solved in + time. Since we assumee m (2(prriv log(Aprv)) in the previous step, the total time complexity is 0(2 mn?
If sign W 2 + Y pubb.,) holds for min we W priv + Y pub.,; Y 112, then 2 = 0 and is the unique minimizer of the signed éz-regression Σnn (Iuj 2; Y Yub pub ,,,)² problem almost surely.
Y.,; 0 and W priv Y pub... Jo Y. a, hold, then from direct caleulations we come to W priv a a (W priv (X spiv) o, Y (ubb..) ) Y pub.... This indicates that ao (W priv priv((X priv) o.i + Y pubb,;) Y pub..; lies in Upri- dimenssinai subspace of R. Noting that (Xpriv), and Y pub,,, i.i.d sampled from Gaussian, the event above happens with probability zero since m >> Rpriv- Thus, we can repeat. this process for all i [d] and solve all z,'s.
Indeed, if we have for # o, W priv Priv((X priv)., + pub..;
(XTT))
We also show that ke-rggressoon with hidden signs is in fact very hard problem. Although empirical methods may bypass this issue by directly applying gradient descent, real world practitioners taking shorteuts would certainly suffer from a lack of apriori theoretical guarantees when facing a large privale dataset.
Theorem 3.8 (Lower bound of fe-regression with hidden signs, informal version of The- orem D.4 ). There erists a constant e >> O such that it is NP-hard to (1 +1 appppromimmte minlER* [W vll2, where W {0, mm is row 2-sparse and y E {0, 1)m
We will reduce the MAX-CUT problem to the fz-regression. MAX-CUT is a well-known NP-hard problem Berman & Karpinski [1999). A MAX-CUT instance graph G = EV with n vertices and m edges. The goal is to find a subset of vertices S C V such that the number of edges between S and V is maximized, i.e., maxscv [E(S, V\ We can further assume G' is 3-rogular, that is, each vertex has degree 3. The full proof is deferred to Appendix D
3.5 PUTTING EVERYTHING TOGETHER
Now we are in the position to prove Theorem
3.1
Proof. By Lemma 3.3 the matrix computed in Line 4 satisfics M WWT By Lemma 3.4 Line correctly computes the indices of all public coordinaes of w; i [m]. Therefore from
M WWT
W priv W Wrri/hippic + W pub W pub hipbb
8

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Solving large system of equations
1: procedure SOLNINGSYSTERMFFERUUATOS W prive Y pub: Y)
2:
W priv Ruxxnin Y pub E Rmxd Y Raxd
3:
for i = 1 do
4:
T; 5 for a E [-1,+11] do
5:
6:
2 6 mii W priv + Y pub,,, Y,,i112
7:
if sign (W priv + Y pub,,.) then
8:
I; f 22
9:
end if end for end for
10:
11:
12:
X + --
13:
return X
14:
end procedure
the Gram matrix computed in Line 10 satisfies Mpriv W priv W
priv
We can now apply Lemma 3.6 to find the private components of mixup weights. Indeed, the output of Line is exactly
priv(W1,t)
W priv kpriv
E {0, mp
priv(Wm...
Based on the correctncss 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
By Lemma
3.3
Line Lakes O(m2d) time. By Lemma 3.4 Line runs in time (dn pub + 2 pub
By Lemma 3.6
private weights can be computed in time mmpriv- Line 10 and Line can be
computed efficiently in time O(m²). Finally Line 15 is computes in time 0(2 mn d)
by Lemma 3.7
Combining all these steps have that the total running time of Algorithm 2w-11 mm + 2m mm m))
bounded by O(m2d + dn + pub
CONCLUSION AND FUTURE WORK
We show that (Tiipriv log ) samples suffice to recover all privale images under the current setup for InstaHide challenge of mixing two private images. We show that 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-of- .4/3
the-art approach Chen et al. (021) that requires "priv samples to recover a single privale image. In addition, we present a theoretical framework to reason about the similarities and
differences of existing attacks Carlini et al. (2220 Chen et al. (2021) and our attack
Instahide.
Based framework, there several interesting directions for future study:
How to generalize our result 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 binary issue. We hope that theoretical contributions shed light on the discussion of safety for distributed training algorithms and provide inspirations for the development of better practical
machine learning methods.

---

Under review as a conference paper at ICLR 2022
5 ETHICS STATEMENT
Our work can potentially create negative societal impacts because our theoretical results can inspire new efficient practical attack methods machine learning models protected by InstaHide.
REPRODUCIBILITY STATEMENT
This is theory paper. We explicitly stated our assumptions and we provided the complete proofs supplementary materials.
REFERENCES
Sanjeev Arora. Instahide. http://www..ffoooue.rrrr.o/ 22000/11111/mssahdd// 2020.
Piotr Berman and Marek Karpinski. On some lighter inapproximability results. In Inter- national Colloquium on Automata, Languages, and Programming, pp. 200-209. Springer, 1999.
Candes, Emmanuel, Thomas Strohmer, and Vladislav Voroninski. Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Communi- cotions on Pure and Applied Mathematics, 66(8):1241-1274, 2013.
J Candes, Emmanuel, Xiaodong Li, and Mahdi. Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. TEFE Transactions on Information Theory, 61 (4):1985--2000 2007, 2015.
Nicholas Carlini, Samuel Deng, Sanjam Garg, Somesh Tha, Saeed Mahloujifar, Moham- mad Mahmoody, Shuang Song, Abhradeep Thakurta, and Florian Tramer. An attack on instahide: Is private learning possible with instance encoding? ar preprint ar orxxi:2011. 1.05315, 2020.
InstaHide Challenge. Instahide challenge. https://github.co com 2020.
Sitan Chen, Xiaoxiao Li, Zhao Song, and Danyang Zhuo. On instahide, phase retrieval, and sparse matrix factorization. In ICLR, 2021.
Danicle Giorgio Degiorgi and Klaus Simon. A dynamic algorithm for line graph recognition. In International Workshop on Graph- Theoretic Concepts in Computer Science, pp. 37-48. Springer, 1995.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A largo-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition (CVPR), pp. 248 255, 2009.
L. Deng. The mnist database of handwritten digit images for machine learning research [best of the web). IEEE Signal Processing Magazine, 29(6):141 142, 2012. doi: 10.1109 MO.P.. 2012.2211477.
Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publ. Moth. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Dimitris Fotakis, Michael Lampis, and Vangelis Th Paschos. Sub-exponential approximation schemes for csps: From dense almost sparse. In 33rd Symposium Thcoretical Aspects of Computer Science (STACS 2016). Schloss Dagstuhl-Leibnizz Zentrum fuer Informatik, 2016.
Baihe Huang, Shunhua Jiang, Zhao Song, and Runzhou Tao. Solving tall dense sdps in the current matrix multiplication time. arXiv preprint arXiw:2101.0822 2021.
10

---

Under review as a conference paper at ICLR 2022
Yangsibo Huang, Zhao Song, Danqi Chen, Kai Li, and Sanjeev Arora. Texthide: Tackling data privacy in language understanding tasks. In The Conference on Empirical Methods in Natural Language Processing (Findings of EMNLP), 2020a.
Yangsibo Huang, Zhao Song, Kai Li, and Sanjeev Arora. Instahide: Instance- hiding schemes for private distributed learning. In International Conference on Machine Learning (ICML), 2020b.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):366-33) 375, 2001.
Michael Jacobson, André E Kézdy, and Jenö Lehel. Rocognizing intersection graphs of linear uniform hypergraphs. Gruphs and Combinalorics, 13(4):359 367, 1997.
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. faster interior point method for semidefinite programiiigg In 61st Annual IEEE Symposeum on Foundations of Computer Science (FOCS), 2020.
Jakub Koncčný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theortha Suresh, and Dave Bacon. Foderated learning: Strategics for improving communication efficiency. arxiv preprinl Xrxiv:1610. 101::1610005492, 2016.
Alex Krizhevsky, Learning multiple layers of features from tiny images. University of Toronto, 05 2012.
Philippe GH Lehot. An optimal algorithm to detect line graph and output its root graph. Journal of the ACM (JACM), 21(4):569-575, 1974.
AG Levin and Regina Iosifovna Tyshkevich. Edge hypergraphs. Diskretnaya Matematika, 5 (1):112-129, 1993.
Dajie Liu, Stojan Trajanovski, and Piet Van Mieghem. Nigra: an efficient inverse line graph algorithm. Journal of Mathematical Modelling and Algorithms in Operations Research, 14 (1):13 33, 2015.
L Lovász. Problem, beitrag graphentheorie und deren auwendungen, vorgstragen auf dem intern. koll, 1977.
Xinjian Luo, Xiaokui Xiao, Yuncheng Wu, Juncheng Liu, and Beng Chin Ooi. A fusion- denoising attack on instahide with data augmentation. arXiv preprint ar Xrx::2105500755, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efice learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pp. 1273-1282. PMLR, 2017.
Praneeth Netrapalli, Prateek Jain, and Sujay. Sanghavi. Phase retrieval using alternating minimization. Tn Advances in Newral Information Processing Systems (NewrIPS), pp- 1273 1282, 2017.
L. T. Phong, Y. Aono, T. Hayashi, L. Wang, and S. Moriai. Privacy-preserving deep learning via additively homomorphic encryption. IEEE Transactions on Information Forensics and Security, 13(5):1333-133 2018. doi: 10. 10.9/ (000//IISS22 TIFS.2017.2787790
Svatopluk Poljak, Vojtëch Rödl, and Daniel TURZiK. Complexity of representation of graphs by set systems. Discrete Applied Mathematics, 3(4):301-31) 31220111,,111 1981.
Nicholas D Roussopoulos. A max {m, n} algorithm for determining the graph h from its line graph g. Information Processing Letters, 2(4):108- -1210 1973.
Theo Ryffel, Andrew Trask, Morten Dahl, Bobby Wagner, Jason Mancuso, Daniel Rueckert, generic framework for privacy preserving deep
and Jonathan Passerat-Pallmaade learning. CoRR, abs/187 1111111110000 100017,7 2018. URL htttt://aariv.org/bbb///te 04017
11

---

Under review as a conference paper at ICLR 2022
Reza Shokri and Vitaly Shmatikov. Privacy-preservic deep learning. In Proceedings of the 22nd CM SIGSAC Conference on Computer and Communications Security, CCS '15, pp. 1310-1321, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450388 450338325. doi:
2810008.8111111666 3687. URL https://dol org/ 1145/
2810103 2813687
Maciej M Syslo. A labeling algorithm recognize line digraph and output its root graph. Information Processing Letters, 15(1):28-3)) 30, 1982.
Hassler Whitney, Congruent graphs and the connectivity of graphs. In Hassler Whitney Collected Papers, pp. 79. Springer, 1992.
Virginia Vassilovska Williams. Multiplying matrices faster than coppersmith-winograd In Proceedings of the forty- fourth annual ACM symposium on Theory of computing (STOC), pp. 887 898. ACM, 2012.
Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In ICLR.
2017.
IF 7verovich. An analogue of the whithey theorem for edge graphs of multigraphs, and edge multigraphs. Discrete Mathematics and Applications, 7(3):287-294) 1997.
12

---

Under review as a conference paper at ICLR 2022
A A UNIFIED FRAMEWORK TO COMPARE WITH EXISTING ATTACKS
Refs
Rec.
Kpriv
Samples
Step
Step 2
Step
Step 4 2
Chen
one
2 2
m 2 n Ahw 2/(h
dm²
dn pub + n
pub
2x+1
m² Trmpriiv
Ours
all
2
Repriv log Plrri
dmd
dr + pu
20+1
2 n priv
Table 1: A summary of running times in different steps between ours and Chen et al. (2021
This table only compares the theoretical result. Let lariv denote the number of private images we
select in InstaHide image. Let d denote the dimension of image. Let Ngub denote the number of images in public dataset. Let Mpri denote the number of images in private dataset. We provide computational lower bound for Step in Appendix D There is no algorithm that solves Step 4 in 20( time under Exponential Time Hypothesis (ETH) (Theorem D.4). Let Rec. denote the Recover.
Our attack algorithm (Algorithm 1 contains four steps for Apriv = 2. We can prove (mprrv (Mvv)) suffices for exact recovery. Our algorithm shares similarities as two recent. attack results one is a practical attack Carlini et al. (2020), the of her 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 al. (2000) and Chen al. (2021).
Recover the Gram matrix M WWT E Rmmm of mixup weights W from henti images Y. This Gram matrix contains all inner products of mixup weights (wi, wyy) Intuitively this measures the similarity of each pair of two synthetic images and is natural start of all existing attacking algorithms.
Step 1. Section 3.1
For this step, Carlini 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 folded Gaussian distribution. This achieved by using Algorithm 2 in Chen et al. (2021). It takes O(m²d) d) time.
Step 2. Section 3.2 Recover all public image coefficients and substract the contribution of public coefficients from Gram matrix M to obtain Mpri- This step is considered
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 '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 paradign 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 dr 2) solving a SDP with "bub x niuu size matrix
variable and ((n constraints, which takes 2 time Jiang et al. (020)
Huang et al. (2021). where w is the exponent of matrix multiplication.
Step 3. Section 3.3 Recover private coefficients W Wpriv E m. from private
Gram matrix M Mpriv
(M = W priv WTw)), this step takes O(m (mmmn? n 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 bet ween 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
Apn (1)m++) Then Chen et al. (202)) can recover private
structure when m 2 "priv coefficients within that local structure using nice combinatorial properties of the "floral matrix".
13

---

Under review as a conference paper at ICLR 2022
For this step, note the fact that in Kpriv = 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 2 3 cases correspond to hypergraphs). We can then leverage results in graph isomorphism theory to recover the all private coefficients. In particular, when m Q(Npriv log "priv) the private coefficients are uniquely identifiable from the Gram matrix.
Step 4. Section 3.4 Solve independent lg-regression problems to find private images Xpriv. Given W
Wpriv priv "Rph and Y E R For each i E [d], let Y, J E R denote the i-th column of Y, we need to solve the following & regression
min ZER
W| + Y pub., ,Y,,2
The classical & 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 2 possibilities. In fact we show that solving l regression with hidden signs is NP-hard.
-oor 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 & regressions. Chen et al. (2021)'s attack is doing the exact same thing as us. However, since their goal just recovering one private image (which means m = O(k))) they only need to guess 2 possibilities.
B SUMMARY OF THE ATTACK BY CARLINI ET AL. CARLINI ET AL. (0200)
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 Piriv private images, the InstaHide authors Huang al. (2020b) first choose parameter T, this can be viewed as the number of ilerations in the deep learning training process. For each E [T], Huang et al. (2020b) draws a random permutation Te : [Mpn + Mpriu.. Each InstaHide image is constructed from private image i, another private image (i) and also some public images. Therefore, there are T Πpriv InstaHide images in total. Here is trivial observation: cach private image shown up in exactly 27 InstaHide images (because kppiv = 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 27' does not hold. In the current version of InstaHide Challenge, the InstaHide authors create the InstaHide labels (a vector that lies in R' 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 major difference compared with Chen et al. (2021). h. 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 similarity matrix M (0,1,2) 20,
Train deep neural network based 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 matrix M construct Trpriv clusters of InstaHide images based on each InstaHide image such that the images inside one cluster shares a common original image.
The second substop runs K-mcans on these clusters, to group clusters into ppriv groups such that each group corresponds to one original image.
'In Carlini et al. 2020). they call it similarity matrix, in Chen et al. 2021 they call it Gram matrix. Here, we follow Carlini al. (202)) for convenience.
14

---

Under review as a conference paper at ICLR 2022
The third substep constructs 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 subset. S of InstaHide images (S C [m]), we define INSERT(S)) as
INSERT(S) = S arg max iE|m
Σ
Mi.
jES
For each i [m]], we compule set C [m]]
where S. INSERT(T/21
Select cluster representatives. Figure illustrates an example of this step.
Define distance between clusters
[S 55 U Sy]
dist(i,
Run k-means using metric dist [m] x [m]] + I. and k = Rpriv- Result is Ppriv
groups C1...., Cr S [m]. Randomly select a representative Ty E C2 for each
E [privl-
Computing assignments. Construct a min-cost flow graph as Figure 2 with weight matrix W E m defined as follows:
W.J
Σ M
[Sr
AESr;
for i E [m],] E [Mpriv]. After solving the min-cost. flow (Figure 3 construct the assignment matrix W E Tmxxnii such that W., = 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 E {0, 1) Before we recover the original image, we need to first recover the weight of mixing, which is represented by the weighled assignment matrix E mmxpp 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 [mpriv]. Let denote the number of classes in the classification task of InstaHide application. For [m], let Yj E R24 be the label j.
label(i)
supp(y;) E [T.].
Jelm].W,..
Then, for i E [m] and j E [Mpri]] such that W., 1, define U2, Vi.labell)) for supp(y;) and Us - Vt.aabel for |supp(y;) =
Here, W E {0, mx is the unweighted assignment matrix and U E m= the weighted assignment matrix. For W., = 0, let U =0
Second, for each pixel e [d], we run gradient descent to find the original images. Let Y Rx be the matrix of all InstaHide images, Y., denote the i-th column of Y
min ||| 1l.22
zER"ph
C MISSING PROOFS FOR THEOREM 3.6
For simplicity, let W denote Wpriv and M denote Mpriv in this section.
Thh description of the attack in Carlini et al. 2020 recovers original images by using gradient descent for min new |U|a|] .. which believe is typo.
15

---

Under review as a conference paper at ICLR 2022
C.1 A GRAPH PROBLEM (Rirri 2)
Theorem C.1 (Whitney (1992)). Suppose G and H are connected simple graphs and L(G) = L(H). G and H are not K3 and K1,3, then G = H. Furthermore, if [V(G) 2 5, then an isomorphism of L(G) uniquely delermines an isomorphism of G.
In other words, this theorem claims that given M WWT, if the underlying W is not the incident matrix of K3 or K1 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, scries of work Roussopoulos 1973 Lehot 1974 Syslo 1982); Degiorgi & Simon (1995); Liu et al. (0155 showed how to efficiently reconstruct the original graph Irom its line graph:
Theorem C.2 [Liu et al. 2015)); ). Given a graph with m vertices and t edges, there crists an algorithm that rans time O(m + t) to decide whether L is line graph and output the original graph G. Furthermore, if L is promised to be the line graph of G, then there erists an algorilhm that oulyuts 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 = Q priv (og a well-known fact in random graph theory by Erdós and Rényí Erdōs & Rényi 1960)) showed that the graph G with incidence matrix W will almost surely be connected. Then, we compute M = M - I, the adjacency matrix of the line graph L(G). Theorem implies that G can be uniquely
recovered from Mg as long as Mpriv is large enough. Finally, We can reconstruct G from M by Theorem
For the time complexity of Algorithm 2 the reconstruction step can be done in ((m) time. Since we need to output the matrix W, we will take (mmmprv))-innn 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 (kipriv > 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 = W with Kpriv = k > 2. Then, W can be recognized as the incidence matrix of k-uniform hypergraph G, i.e. each hyperedge contains k vertices. Mg M corresponds to adjacency matrix of the line graph of hypergraph G: (Ma), le; 0 Neyl for C, being two hyperedges. Now, we can see that each entry of MG is in (O....,k) 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 more basic problem:
Problem C.3 (Line graph recognition for hypergraph). Given a simple graph L = (V, F) and ls M, decide if L is the line graph of k-uniform hypergroph G.
Even for the recognition problem. it was proved to be WP-complete for fixed k > 3 Levin & Tyshkevich (1993): Poljak et al. (1981). However, Problem C.3 becomes tractable we add more constraints to the underlying hypergraph G. First, suppose G is a linear hypergraph, ie., the intersection of two hyperedges 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 polynomial-time algorithm for the decision problem. Similar result also holds for h > 3 Jacobson et al. (1997). Let the edge-degree of 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 21.2 3k + 1,, there exists polynomial-time algorithm
16

---

Under review as a conference paper at ICLR 2022
polvate leogle
Tipe leagle
Intral
clydeer
clotter
cltdee
chseee
clarter
claater
elseter 7
clotter
Gloer
chulier
claier grow on
chacke growr oe
claxer grove on
claske grow
checks gaoer
claseer zroer
claster ghow ora
grver
BLB
Ranaus K=4
C
Figure 1: An example about cluster step in Carlini et al. (202)) for T = 2 and Plpriv 4. First, starting from each InstaHide image (lop), the algorithm grows cluster S with size (middle). Then, we use K-means for K 4 to compute 4 groups C1, Ca (bottom), these groups each correspond to one original image.
to docide whether the line graph of a linear k-uniform hypergraph. Furthermore, the yes case, the algorithm 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.
17

---

Under review as a conference paper at ICLR 2022
Instafidee image
seiginal imsuee
T Mye
ST,
Figure 2:
The construction of the graph for min-cost max flow. с denotes the flow capacity of the edge, and w denote the weight of the edge. The graph contains T Tipiiv nodes for each InstaHide images, Mpriv nodes for each original images, source and terminal. There are three types of edges: (left) from the source each InstaHide image node, with flow capacity and weight 0; (middle) from each InstaHide image node to each original image node j, with flow capacity and weight Ways tit) (right) from each original image node to the terminal, with flow capacity 27 and weight 0.
Imagre
ortginal Imagre
W.
000000
teminal
Figure 3: The result of solving the min-cost flow in Figure 2 Each InstaHide image is assigned to two clusters, which ideally correspond to two original images. In reality, cluster may not contain all InstaHide images that share the same original image.
D COMPUTATIONAL LOWER BOUND
The goal of this section is to prove that the égrregression with hidden signs is actually a. very hard problem, even for approximation (Theorem D.4) which implics that Algorithm cannot be significantly improved. For simplicity we consider Spub
We first state NP-hardness of approximation result for 3-regular MAX-CUT.
Theorem D.1 (Imapproximability of 3-regular MAX-CUT, Berman & Karpinski 19999 For every é > 0, is NP-hard to approzimate 3-regular MAX-CUT within a factor of
where R 0.997.
18

---

Under review as a conference paper at ICLR 2022
If assume the Exponential Time Hypothesis (ETH), which 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 erists a constant > 0 such that the time complexiiy oJ n-variable 3SAT is al least 2
Theorem D.3 Fooaaii et al. (2016)). Assuming ETH, there erists a constant 0 < r' <
such that no 20(m) algorithm can -appronimate the MarCul of an n-verlex, 5-regular groph.
With Theorem D.1 and Theorem D.3 we can prove the following inapproximability result for the le-regression problem with hidden signs.
Theorem D.4 (Lower bound of fz-regression with hidden signs). There exisls a consland 0 such that it is NP-hard to + -)opprozzialee
min =E
||Wz| - B112,
(1)
where W E {0, 1m is row 2-sperse and y E 1)".
Furthermore, assuming ETH, there erists a constant such that no -time algorithm con é' e-approzzimaee Eq.
Proof. Given 3-regular MAX-CUT instance G, we construct an éz-regression instance (W, y) with W 1mm and y {0, 1 where m'
(1 3c/2)m and 10 as
follows.
For each i E [m], let the i-th edge of G be e; fu, e). We set W., to be all zeros except the u-th and v-th coordinates being one. That is, we add a constraint | + zpl- And we set y: O.
For each j E [n], we set W the j-th entry being one. That is, add constraints of the form lzyl. And Vm+o(f-1)+11 = yatto 11
Wm+eij to be all zero vectors except
Completencss. Let opt be the optimal value of max-cut of G and let Sopt be the optimal subset. Then, for each u E Sopt, we set 2n 1; and for u & Sopt, we set zn = -1. For the first. lype constraints Iz, + zul: if and v cut by Sopts then Iz, + zul O; otherwise Izu + = = 2. For the second type constraints Ezyl, all of them are satisfied by our assignment. Thus, [W= - vll2- = 4(m - opt).
Soundness. Let n be constant such that <) 1, where is the approximation lower bound in Theorem D.1 Let = I_2 We will show that, if there exits a such that Toe
|[W - vl12 < 8m', then we can recover a subset S with cut-size 1pn.
It is casy to that the optimal solution lics in []1, Since for & [-1, 1]" can
always transform it to new vector z' E [-,,1 such that ||>'' - y11 S [| z y/12.
Suppose E {-1,1)" is Boolean vector. Then, we can pick (i E [n] 2; 1}. We
have the cut-size of S is
EESS V\S) 2 m 8m'/4
= m 5(1 + 3c/2)m/4
(1 5/4 3cd m
2 mm,
where the last step follows from 8 < 8(1-n)
246c
For general 1]", we first round by its sign: let 2, sign(z)) for i E [n]. We will show that
48
I - - I -
19

---

Under review as a conference paper at ICLR 2022
which implies
[ - -12 = || - -y12 + [I -v12 I| - -113)
48
S 6m' + m.
Then, we have the cut-size of S is
[BSS, V\S) 2 (ōm' 48m/c)/4
= (1 - 6/4 - 3c0/8 12/c)
2 npm,
where the last step follows from 5 S 8(1-n-12/e)
2+0c
Let A | zz| = 1- |2a| [0, We have
IW v11 - I|= - -212 =
uu + =0,)² -Zzu + 20x)2 +
(|=b1 - -1)2 - -[z]] - 1)²
j=1
(Zu: + kuu)) - -Zz + Zuz -c
(|2g1 1)²
1=1
j=1
(Zus +z, -Zzu + Zzz )²
A
m
A + 1 -
A3
j=1
124,
ca
i=1
72
c
48
where the first step follows by the construction of W and y. The second step follows from |žy| = 1 for all j [n]]. The third step follows from the definition of A The forth step follows from |=,, + zuyl [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 12r cr2 in is 72 The last step follows from m m= 33/2.
Therefore, by the completeness and soundness of reduction, if we take E (0, 8), Theorem D.1 implies that it is NP-hard to (1 + --aaprroximate the fz-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 6), we can use Theorem D.3 to rule out -ime algorithm for O(I)-factor approximation. We omit the details since they are almost the same as the first part.
20


Reviews:
[{"review_id": "neG3uoea5RI", "reviewer": "Reviewer_3gkW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nMy 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.\n\nIn 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_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. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "e4rJM6JLNYV", "reviewer": "Reviewer_d4iK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nTechniques:\n\nThe 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.\n", "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.\n\nThe 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.", "summary_of_the_review": "The paper makes reasonable improvements to the sample complexity of InstaHide challenge. However, I have two main concerns:\n\n1) 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.\n\n2) 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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Wh9GMmm_hD7", "reviewer": "Reviewer_x8b2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThis 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.\n\nAlthough 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_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.", "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.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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