InstaHide: Instance-hiding Schemes for Private Distributed Learning

Introduction

In many applications, multiple parties or clients with sensitive data want to collaboratively train a neural network. For instance, hospitals may wish to train a model on their patient data. However, aggregating data to a central server may violate regulations such as Health Insurance Portability and Accountability Act (HIPAA) [Act96] and General Data Protection Regulation (GDPR) [VVdB18].

Federated learning [MMR+17, KMY+16] proposes letting participants train on their own data in a distributed fashion and share only model updates —i.e., gradients—with the central server. The server aggregates these updates (typically by averaging) to improve a global model and then sends updates to participants. This process runs iteratively until the global model converges. Merging information from individual data points into aggregated gradients intuitively preserves privacy to some degree. On top of that, it is possible to add noise to gradients in accordance with Differential Privacy (DP) [DKM+06, DR14], though careful calculations are needed to compute the amount of noise to be added [ACG+16, PCS+19]. However, the privacy guarantee of DP only applies to the trained model (i.e., approved use of data) and does not apply to side-channel computations performed by curious/malicious parties who are privy to the communicated gradients. Recent work [ZLH19] suggests that eavesdropping attackers can recover private inputs from shared model updates, even when DP was used. A more serious issue with DP is that meaningful guarantees involve adding so much noise that test accuracy reduces by over $20\%$ even on CIFAR-10 [PCS+19].

Cryptographic methods such as secure multiparty computation of [Yao82] and fully-homomorphic encryption [Gen09] can ensure privacy against arbitrary side-computations by adversary during training. Unfortunately it is a challenge to use them in modern deep learning settings, owing to their high computational overheads and their needs for special setups (e.g finite field arithmetic, public-key infrastructure).

Here we introduce a new method InstaHide, inspired by a weaker cryptographic idea of instance hiding schemes [AFK87]. We only apply it to image data in this paper and leave other data types (e.g., text) for future work. InstaHide gives a way to transform input $x$ to a hidden/encrypted input $\widetilde{x}$ in each epoch such that: (a) Training deep nets using the $\widetilde{x}$’s instead of $x$’s gives nets almost as good in terms of final accuracy; (b) Known methods for recovering information about $x$ out of $\widetilde{x}$ are computationally very expensive. In other words, $\widetilde{x}$ effectively hides information contained in $x$ except for its label.

InstaHide encryption has two key components. The first is inspired by Mixup data augmentation method [ZCDLP18], which trains deep nets on composite images created via linear combination of pairs of images (viewed as vectors of pixel values). In InstaHide the first step when encrypting image $x$ (see Figure 1) is to take its linear combination with $k-1$ randomly chosen images from either the participant’s private training set or from a large public dataset (e.g., ImageNet [DDS+09]). The second step of InstaHide involves applying a random pattern of sign flips on the pixel values of this composite image, yielding encrypted image $\widetilde{x}$, which can be used as-is in existing deep learning frameworks. Note that the set of random images for mixing and the random sign flipped mask are used only once —in other words, as a one-time key that is never re-used for another encryption.

Experiments on MNIST, CIFAR-10, CIFAR-100 and ImageNet datasets (see Section 5) suggest that InstaHide is an effective approach to hide training images from attackers. It is much more effective at hiding images than Mixup alone and provides better trade-off between privacy preservation and accuracy than DP. To enable further rigorous study of attacks, we release a challenge dataset of images encrypted using InstaHide.

As hinted above, InstaHide plugs seamlessly into existing distributed learning frameworks such as federated learning: clients encrypt their inputs on the fly with InstaHide and participate in training (without using DP). Depending upon the level of security needed in the application (see Section 4.1), InstaHide can also be used to present enhanced functionality that are unsafe in current distributed frameworks. For instance, in each epoch, computationally limited clients can encrypt each private input $x$ to $\widetilde{x}$ and ship it to the central server for all subsequent computation. The server may randomize in the pooled data to create its own batches to deal with special learning situations when distributed data are not independent and identically distributed.

Security goal of InstaHide.

The goal of InstaHide is to provide a light-weight encryption method to make it difficult for attackers to recover the training data in a large training dataset in a distributed learning setting, with minor reduction on data utility. It is not designed to provide the level of security strength as encryption methods such as RSA [RSA78]. It is an initial step towards exploring better privacy preservation while maintaining data utility.

Rest of the Paper:

Section 2 recaps Mixup and suggests it alone is not secure. Section 3 presents two InstaHide schemes, and Section 4 analyzes their securityA recent attack [CDG+20] (see Section 9 for details) suggests that the security analysis for InstaHide in the current version may need some revisions. We will release an update with more extensive explanations.. Section 5 shows experiments for InstaHide’s efficiency, efficacy, and security. Section 6 provides suggestions for practical use, and Section 7 describes the challenge dataset. We review related work in Section 8, discuss potential attacks in Section 9 and conclude in Section 10.

Mixup and Its Vulnerability

See Algorithm 1. Given an original dataset, in each epoch of the training the algorithm generates a Mixup dataset on the fly, by linearly combining $k$ random samples, as well as their labels (lines 9, 10). Mixup suggests that training with mixed samples and mixed labels serves the purpose of data augmentation, and achieves better test accuracy on normal images.

We describe the algorithm as an operation on $k$ images, but previous works mostly used $k=2$.

We propose an attack to the Mixup method when a private image is mixed up more than once during training. In fact, in Algorithm 1, each image is used $kT$ times during training, where $k$ is the number of samples to mix, and $T$ is the number of training epochs.

Assume that pairs of images in $\mathcal{X}$ are fairly independent at the pixel level, so that the inner product of a random pair of images (viewed as vectors) has expectation (expectation can be nonzero but small). We can think of each pixel is generated from some distribution with standard deviation $1/\sqrt{d}$ and describe attacks with this assumption. (Section 5 presents experiments showing that these attacks do work in practice.)

Suppose we have two Mixup images $\widetilde{x}_{1}$ and $\widetilde{x}_{2}$ which are derived from two subsets of private images, ${\mathcal{S}}_{1},{\mathcal{S}}_{2}\subset\mathcal{X}$ and $|{\mathcal{S}}_{1}|=|{\mathcal{S}}_{2}|=k$. If $\widetilde{x}_{1}$ and $\widetilde{x}_{2}$ contain different private images, namely ${\mathcal{S}}_{1}\cap{\mathcal{S}}_{2}=\emptyset$, then the expectation of $\widetilde{x}_{1}\cdot\widetilde{x}_{2}$ is 0. However, if ${\mathcal{S}}_{1}\cap{\mathcal{S}}_{2}\neq\emptyset$, and $\widetilde{x}_{1}$ and $\widetilde{x}_{2}$ have coefficients $\lambda_{1}$ and $\lambda_{2}$ for the common image in these two sets, then the expectation of $\langle\widetilde{x}_{1},\widetilde{x}_{2}\rangle$ is $\lambda_{1}\lambda_{2}/k$, which means by simply checking the inner products between two $\widetilde{x}$’s, the attacker can determine with high probability whether they are derived from the same image. Thus if the attacker finds multiple such pairs, they can average the $\widetilde{x}$’s to start getting a good estimate of $x$. (Note that the rest of images in the pairs are with high probability distinct and so average to .)

2 Attack on Mixup Between a Private and a Public Dataset

To defend against the previous attack, it seems that a possible method is to modify the Mixup method to mix a private image $x$ with $k-1$ images only once to get a single $\widetilde{x}$, and use this $\widetilde{x}$ as surrogate for $x$ in all epochs. To ensure $x\in\mathcal{X}$ is used only once, it uses an additional public dataset $\mathcal{X^{\prime}}$ (e.g. ImageNet). In other words, for every $x\in\mathcal{X}$, it produces $\widetilde{x}$ by using Mixup between $x$ and $k-1$ random images from a large public dataset.

This extension of the Mixup method seems secure at first glance, as naively one can imagine that to violate privacy, the adversary must do exhaustive search over $(k-1)$-tuples of public images to determine which were mixed into $\widetilde{x}$, and try all possible $k$-tuples of coefficients, and then subtract the corresponding sum from $\widetilde{x}$ to extract $x$. If this is true, it would suggest that extracting $x$ or any approximation to it requires ${N\choose{k-1}}\approx N^{k-1}$ work, where $N$ is the number of images in the public dataset. This work becomes infeasible even for $k=4$. However, we sketch an attack below that runs in $O(Nk)$ time.

It again uses the above assumption about the pairwise independence property of a random image pair. Recall that standard deviation of pixels is $1/\sqrt{d}$. Namely, to determine the images that went into the mixed sample $\widetilde{x}=\lambda_{1}x_{1}+\sum_{i=2}^{k}\lambda_{i}x_{i}$, it suffices to go through each image $z$ in the dataset and examine the inner product $z\cdot\widetilde{x}$. If $z$ is not one of the $x_{i}$’s then this inner product is of the order at most $\sqrt{k/d}$ (see part 1 of Theorem B.3), whereas if it is one of the $x_{i}$’s then it is of the order at least $\frac{1}{k}(1-\sqrt{k/d})$ (see part 2 of Theorem B.3). Thus if $k^{3}\ll d$ (which is true if the number of pixels $d$ is a few thousand) then the inner product gives a strong signal whether $z$ is one of the $x_{i}$’s. Once the correct $x_{i}$’s and their coefficients have been guessed, we obtain $x$ up to a linear scaling. Thus the above attack works with good probability and in time proportional to the size of the dataset. We provide results for this attack in Section 5.

This attack of course requires that $x$ is being mixed in with images from a public dataset $\mathcal{X^{\prime}}$. In the case that $\mathcal{X^{\prime}}$ is private and diverse enough, it is conceivable that Mixup is safe. (MNIST for example may not be diverse enough but ImageNet probably is.) We leave it as an open question.

3 Discussions

Table 1 summarizes the security of Mixup . Only Mixup with single $\widetilde{x}$ for each private $x$ and within a private dataset(s) has not been identified vulnerable to potential attacks. But this does not necessarily mean it is secure. In addition, the test accuracy in this case is not comparable to vanilla training; it incurs about $20\%$ accuracy loss with CIFAR-10 tasks.

Both methods may be vulnerable to the attacks presented in this section: when $h$ is linear (one example in [LWZ+19]), we have $\widetilde{h}_{1}(x)=\widetilde{h}_{2}(x)$, which means the attacker can reconstruct the Mixup image $\widetilde{x}=\lambda_{1}x+\sum_{i=1}^{k}x_{i}$ from $\widetilde{h}_{1}(x)$ and run attacks on Mixup. For a nonlinear $h$, $\widetilde{h}_{1}(x)\approx\widetilde{h}_{2}(x)$ may also hold.

InstaHide

This section first presents two schemes: Inside-dataset InstaHide and Cross-dataset InstaHide, and then describes their inference.

The Inside-dataset InstaHide mixes each training image with random images within the same private training dataset. The cross-dataset InstaHide, arguably more secure (see Section 4), involves mixing with random images from a large public dataset like ImageNet.

Algorithm 2 shows Inside-dataset InstaHide. Its encryption step includes mixing the secret image $x$ with $k-1$ other training images followed by an extra random pixel-wise sign-flipping mask on the composite image. Note that random sign flipping changes the color of a pixel. The motivation for random sign flips was described around Footnote 2.

Let $\Lambda_{\pm}^{d}$ denote the $d$-dimensional random sign distribution such that $\forall\sigma\sim\Lambda_{\pm}^{d}$, for $i\in[d]$, $\sigma_{i}$ is independently chosen from $\{\pm 1\}$ with probability 1/2 each.

To encrypt a private input $x_{i}$, we first determine the random coefficient $\lambda$’s for image-wise combination, but with the constraint that they are at most $c_{1}$ to avoid dominant leakage of any single image (line 6 in Algorithm 2). Then we sample a random mask $\sigma_{i}\sim\Lambda_{\pm}^{d}$ and apply $\sigma\circ x$, where $\circ$ is coordinate-wise multiplication of vectors (line 10 in Algorithm 2). Note that the random mask $\sigma_{i}$ and the $k-1$ images used for mixing with $x_{i}$, will not be reused to encrypt other images. They constitute a “random one-time private key.”

It may seem that using a different mask for each training sample would completely destroy the accuracy of the trained net, but as we will see later it has only a small effect when $k$ is small. Mathematically, this seems reminiscent of the phase retrieval problem [CSV13, LN18] (see Appendix D).

2 Cross-Dataset InstaHide

Cross-dataset InstaHide extends the encryption step of Algorithm 2 by mixing $k$ images from the private training dataset $D_{\text{private}}$ and a public dataset $D_{\text{public}}$, and a random mask as a random one-time secret key.

Although the second dataset can be private, there are several motivations to use a public dataset: (a) Some privacy-sensitive datasets, (e.g. CT or MRI scans), feature images with certain structure patterns with uniform backgrounds. Mixing among such images as in Algorithm 2 would not hide information effectively. (b) Drawing mixing images from a larger dataset gives greater unpredictability, hence better security (see Section 4). (c) Public datasets are freely available and eliminate the need for special setups among participants in a distributed learning setting.

To mix $k$ images in the encryption step, we randomly choose $2$ images from $D_{\text{private}}$ and the other $k-2$ from $D_{\text{public}}$, and apply InstaHide to all these images. The only difference in the cross-dataset scheme is that, the model is trained to learn only the (mixed) label of $D_{\text{private}}$ images. We assume $D_{\text{public}}$ images are unlabelled. For better accuracy, we lower bound the sum of coefficients of two private images by a constant $c_{2}\in$.

We advocate preprocessing a public dataset in two steps to obtain $D_{\text{public}}$ for better security. The first is to randomly crop a number of patches from each image in the public dataset to form $D_{\text{public}}$. This step will make $D_{\text{public}}$ much larger than the original public dataset. The second is to filter out the “flat” patches. In our implementation, we design a filter using SIFT [Low99], a feature extraction technique to retain patches with more than 40 key points.

3 Inference with InstaHide

Either scheme above by default applies InstaHide during inference, by averaging predictions of multiple encryptions (e.g. 10) of a test sample. This idea is akin to existing cryptographic frameworks for secure evaluation on a public server via homomorphic encryption (e.g. [MLS+20]). Since the encryption step of InstaHide is very efficient, the overhead of such inference is quite small.

One can also choose not to apply InstaHide during inference. We found in our experiments (Section 5) that it works for low-resolution image datasets such as CIFAR-10 but it does not work well with a high-resolution image dataset such as ImageNet.

Security Analysis

This section considers the security of InstaHide in distributed learning, specifically the cross-dataset version.

Attack scenario: In each epoch, all clients replace each (image, label)-pair $(x,y)$ in the training set with some $(\widetilde{x},\widetilde{y})$ using InstaHide. Attackers observe $h(\widetilde{x},\widetilde{y})$ for some function $h$: in federated learning $h$ could involve batch gradients or hidden-layer activations computed using input $\widetilde{x},\widetilde{y}$ as well as other inputs.

Argument for security consists of two halves: (1) To recover significant information about an image $x$ from communicated information, computationally limited eavesdroppers/attackers have to break InstaHide encryption (Section 4.1). (2) Breaking InstaHide is difficult (Section 4.2).

Suppose an attacker exists that compromises an image $x$ in the protocol. We do the thought experiment of even providing the attacker with encryptions of all images belonging to all parties, as well as model parameters in each iteration. Now everything the attacker sees during the protocol it can efficiently compute by itself, and we can convert the attacker to one that, given $\widetilde{x}$, extracts information about $x$. We conclude in this thought experiment that a successful attack on the protocol also yields a successful attack on the encryption. In other words, privacy loss during protocol is upper bounded by privacy loss due to the encryption itself. Of course, this proof allows the possibility that the protocol —due to aggregation of gradients, etc.—ensures even greater privacy than the encryption alone.

In our protocol each image $x$ is re-encrypted in each epoch. This seems to act as a data augmentation and improves accuracy. The above argument translated to this setting shows that privacy violation requires solving the following problem: private images $x_{1},x_{2},\ldots,x_{n}$ were each encrypted $T$ times ($n$ is size of the private training set, $T$ is number of epochs), each time using a new private key. Attacker is given these $nT$ encryptions. Weaker task: Attacker has to identify which of them came from $x_{1}$. Stronger task: Attacker has to identify $x_{1}$.

We conjecture both tasks are hard. Visualization (see Figure 2) as well as the Kolmogorov–Smirnov test [Kol33, Smi48] (see Appendix E) suggest that statistically, it is difficult to distinguish among distributions of encryptions of different images. Thus, effectively identifying multiple $\widetilde{x}$’s of same $x$ and using them to run attacks seems difficult.

2 Hardness of Attacking InstaHide Encryption

Now we consider the difficulty of recovering information about $x$ given a single encryption $\widetilde{x}$.

We start by considering the naive attack on cross-dataset InstaHide, which would involve the attacker to either figure out the set of all $k-2$ public images, or to compromise the mask $\sigma$ and run attacks on Mixup. This should take $\min\{|\mathcal{D}_{\rm public}|^{k-2},2^{d}\}$ time. For cross-dataset InstaHide schemes with a large public dataset (e.g. ImageNet), the computation cost of attack will be $10^{7(k-2)}$, and $k=4$ already makes the attack hard.

Now we suggest reasons why the naive attack may be best possible.

For worst-case pixel-vectors, finding the k𝑘k-image set is hard.

Of course, images are not worst-case vectors. Thus an attack must leverage this fact somehow. The obvious idea today is to use a deep net for the attack, and the experiments below will suggest the obvious ideas do not work.

Compromising the mask is also hard.

As previously discussed, the pixel-wise mask $\sigma\sim\Lambda_{\pm}^{d}$ ( Def. 3.1) in InstaHide is kept private by each client, which is analogous to a private key (assuming the client never shares its own $\sigma$ with others, and the generation of $\sigma$ is statistically random). Brute-force algorithm consumes $2^{d}$ time to figure out $\sigma$, where $d$ can be several thousands in vision tasks.

Experiments

We have conducted experiments to answer three questions:

How much accuracy loss does InstaHide suffer (Section 5.1)?

How is the accuracy loss of InstaHide compared to differential privacy approaches (Section 5.2)?

Can InstaHide defend against known attacks (Section 5.3)?

We are particularly interested in the cases where $k\geq 4$.

Our main experiments are image classification tasks on four datasets MNIST [LCB10], CIFAR-10, CIFAR-100 [Kri09], and ImageNet [DDS+09]. We use ResNet-18 [HZRS16] architecture for MNIST and CIFAR-10, NasNet [ZVSL18] for CIFAR-100, and ResNeXt-50 [XGD+17] for ImageNet. The implementation uses the Pytorch [PGM+19] framework. Note that we convert greyscale MNIST images to be 3-channel RGB images in our experiments. Hyper-parameters are provided in Appendix E.

1 Accuracy Results of InstaHide

We evaluate the following InstaHide variants (with $c_{1}=0.65,c_{2}=0.3$):

Inside-dataset InstaHide with different $k$’s, where $k$ is chosen from $\{1,2,3,4,5,6\}$.

Cross-dataset InstaHide with $k=4,6$. For MNIST, we use CIFAR-10 as the public dataset; for CIFAR-10 and CIFAR-100, we use the preprocessed ImageNet as the public dataset. We do not test Cross-dataset InstaHide on ImageNet since its sample size is already large enough for good security.

The computation overhead of InstaHide in terms of extra training time in our experiments is smaller than $5\%$.

Figure 3 shows the test accuracy of vanilla training, and inside-dataset InstaHide with different $k$’s on MNIST, CIFAR-10 and CIFAR-100 benchmarks. Compared with vanilla training, InstaHide with $k=4$ only suffers small accuracy loss of $1.3\%$, $3.4\%$, and $4.7\%$ respectively. Also, increasing $k$ from 1 (i.e., apply mask on original images, no Mixup) to 2 (i.e., apply mask on pairwise mixed images) improves the test accuracy for CIFAR datasets, suggesting that Mixup data augmentation also helps for encrypted InstaHide data points.

Inside-dataset v.s. Cross-dataset.

We also evaluate the performance of Cross-dataset InstaHide, which does encryption using random images from both the private dataset and a large public dataset. As shown in Table 2, Cross-dataset InstaHide incurs an additional small accuracy loss comparing with inside-dataset InstaHide. The total accuracy losses for MNIST, CIFAR-10 and CIFAR-100 are $1.7\%$, $4.1\%$, and $4.7\%$ respectively. As previously suggested, a large public dataset provides a stronger notion of security.

Inference with and without InstaHide.

As mentioned in Sec 3.3, by default, InstaHide is applied during inference. In our experiments, we average predictions of 10 encryptions of a test image. We found that for high-resolution images, applying InstaHide during inference is important: the results of using Inside-dataset InstaHide on ImageNet in Table 2 show that the accuracy of inference with InstaHide is $72.6\%$, whereas that without InstaHide is only $1.4\%$.

2 InstaHide vs. Differential Privacy approaches

Although InstaHide is qualitatively different from differential privacy in terms of privacy guarantee, we would like to provide hints for their relative accuracy (Question 2).

DPSGD [ACG+16] injects noise to gradients to control private leakage. Table 2 shows that DPSGD leads to an accuracy drop of about $20\%$ on CIFAR-10 dataset. By contrast, InstaHide gives models almost as good as vanilla training in terms of test accuracy.

Comparison with adding random noise to images.

As shown in Figure 4, by increasing $\alpha$ from 0.1 to 0.9, the test accuracy of adding random noise drops from $\sim 94\%$ to $\sim 10\%$, while the accuracy of InstaHide is above $90\%$.

3 Robustness Against Attacks

To answer the question how well InstaHide can defend known attacks, here we report our findings with a sequence of attacks on InstaHide encryption $\widetilde{x}$ to recover original image $x$, including gradient-matching attack [ZLH19], demasking using GAN (Generative Adversarial Network), averaging multiple encryptions, and uncovering public images with similarity search.

Here attacker observes gradients of the loss generated using a user’s private image $s$ while training a deep net (attacker knows the deep net, e.g., as a participant in Federated Learning) and tries to recover $s$ by computing an image $s^{*}$ that has similar gradients to those of $s$ (see algorithm in Appendix E). Figure 5 shows results of this attack on Mixup and InstaHide schemes on CIFAR-10. If Mixup with $k=4$ is used, the attacker can still extract fair bit of information about the original image. However, if InstaHide is used the attack isn’t successful.

Demask using GAN.

InstaHide does pixel-wise random sign-flip after applying Mixup (with public images, in the most secure version). This flips the signs of half the pixels in the mixed image. An alternative way to think about it is that the adversary sees the intensity information (i.e. absolute value) but not the sign of the pixel. Attackers could use computer vision ideas to recover the sign. One attack consists of training a GAN on this sign-recovery taskWe thank Florian Tramèr for suggesting this attack., using a large training set of $(z,\sigma\circ z)$ where $z$ is a mixed image and $\sigma$ is a random mask. If this GAN recovers the signs reliably, this effectively removes the mask, after which one could use the attacks against Mixup described in Section 2.

In experiments this only succeeded in recovering half the flipped signs, which means $\sim 1/4$ of the coordinates continued to have the wrong sign; see Figure 6. GAN trainingWe use this GAN architecture (designed for image colorization): https://github.com/zeruniverse/neural-colorization. used 50,000 cross-dataset InstaHide examples generated with CIFAR-10 and ImageNet ($k=6$). This level of sign recovery seems insufficient to allow the attack against Mixup (Section 2) to succeed, nor the other attacks discussed below. Nevertheless, researchers trying to break InstaHide may want to use such a demasking GAN as a starting point.

Average multiple encryptions of the same image.

We further test if different encryptions of the same image (after demasking) can be used to recover that hidden image by running the attack in Section 2.1.

Assuming a public history of $n\times T$ encryptions, where $n$ is the size of the private training set, and $T$ is the number of epochs. We consider a stronger and a weaker version of this attack.

Stronger attack: the attacker already knows the set of multiple encryptions of the same image $x$. He uses GAN to demask all encryptions in the set, and averages images in the demasked set to estimate $x$.

Weaker attack: the attacker does not know which subset of the encryption history correspond to the same original image. To identify that subset, he firstly demasks all $n\times T$ encrytions in the history using GAN. With an arbitrary demasked encryption (from the history) for some unknown original image $x$, he runs similarity search to find top-$m$ closest images in $n\times T-1$ other demasked encryptions (which may also contain $x$), and averages these $m+1$ images to estimate $x$.

The stronger attack is conceivable if $n$ is very small (say a hospital only has 100 images), so via brute force the attacker can effectively have a small set of encryptions of the same image. However, in practice, $n$ is usually at least a few thousand.

For simplicity, we test with $n=50$ and $T=50$ (a larger $n$ will make the attack harder). We use the structural similarity index measure (SSIM) [WBSS04] as the similarity metric, and set $m$ to 5 after tuning.

We also run this attack directly on Mixup for comparison. As shown in Figure 7, if the original image is not flat (e.g. the “deer”), the stronger attack may not work. For flat images (e.g. the “truck”) or images with strong contrast (e.g. the “automobile” and the “frog”), the stronger attack is able to vaguely recover the original image. However, as previously suggested, the stronger attack is feasible only for a very small $n$.

Note that results here is an upper bound on privacy leakage since we assume a perfect recovery of $\widetilde{x}$ from the gradients. In real-life scenarios this may not hold.

Uncover public images by similarity search.

We also run the attack in Section 2.2 after demasking InstaHide encryptions using GAN, which tries to uncover the public images for mixing by running similarity search in the public dataset using the demasked encryption as the query.

We test with $k=6$: mix 2 private images from CIFAR-10 with 4 public images from a set of 10,000 ImageNet images (i.e. $N=10,000$). We consider the attack a ‘hit’ if at least one public image for mixing is among the top-$m$ answers of the similarity search. The attacker uses SSIM as the default similarity metric for search. However, a traditional alignment-based similarity metric (e.g SSIM) would fail in InstaHide schemes which use randomly cropped patches of public images for mixing (see Figure 8), so in that case, the attacker trains a deep model (VGG [SZ15] in our experiments) to predict the similarity score.

Note that to find the 4 correct public images for mixing, the attack has to try all ${m\choose 4}$ combinations of the top-$m$ answers with different coefficients, and subtract the combined image from the demasked InstaHide encryption to verify. Figure 8 reports the averaged hit rate of this attack on 50 different InstaHide images. As shown, even with a relatively small public dataset ($N=10,000$) and a large $m=\sqrt{N}$, the hit rate of this attack on InstaHide (enhanced with random cropping) is around 0.05 (i.e. the attacker still has to try ${m\choose 4}=O(N^{2})$ combinations to succeed with probability 0.05). Also, this attack appears to become much more expensive with the public dataset being the whole ImageNet dataset ($N=1.4\times 10^{7}$) or random images on the Internet.

InstaHide Deployment: Best practice

Based on our security analysis (sec 4 and sec 5.3), we suggest the following:

Consider Inside-dataset InstaHide only if the private dataset is very large and images have varied, complex patterns. If the images in the private dataset have simple signal patterns or the dataset size is relatively small, consider using Cross-dataset InstaHide.

For Cross-dataset InstaHide, use a very large public dataset. Follow the preprocessing steps advocated in Sec 3.2 to randomly crop patches from each image in the public dataset and filter out “flat” patches.

Re-encrypt images in each epoch. This allows the benefits of greater data augmentation for deep learning and hinders attacks (as suggested in Sec 5.3).

Since images are re-encrypted in each epoch, for best security (e.g, against gradient-matching attacks), each participant should perform a random re-batching so that batch gradients do not correspond to the same subset of underlying images.

Choose $k=4,5,6$ for a good trade-off between accuracy and security.

Set a conservative upper threshold for the coefficients in mixing (e.g. $0.65$ in our experiments).

A Challenge Dataset

To encourage readers to design stronger attacks, we release a challenge dataset https://github.com/Hazelsuko07/InstaHide_Challenge. of encrypted images generated by applying Cross-dataset InstaHide with $k=6$ on some private image dataset and a preprocessed ImageNet as the public dataset. An attack is considered to succeed if it substantially recovers a significant fraction of original images.

Related Work

See Section 2. Mixup can improve both generalization and adversarial robustness [VLB+19]. It has also been adapted to various learning tasks, including semi-supervised data augmentation [BCG+19], unsupervised image synthesis [BHV+19], and adversarial defense at the inference stage [PXZ19]. Recently, [FWX+19] combined Mixup with model aggregation to defend against inversion attack, and [LWZ+19] proposed a novel method using Mixup for on-cloud privacy-preserving inference.

Differential privacy.

Differential privacy for deep learning involves controlling privacy leakage by adding noise to the learning pipeline. If the noise is drawn from certain distributions, say Gaussian or Laplace, it is possible to provide guarantees of privacy [DKM+06, DR14]. Applying differential privacy techniques to distributed deep learning is non-trivial. Shokri and Shmatikov [SS15] proposed a distributed learning scheme by directly adding noise to the shared gradients. However, the amount of privacy guaranteed drops with the number of training epochs and the size of shared parameters. DPSGD [ACG+16] was proposed to dynamically keep track of privacy spending based on the composition theorem [Dwo09]. However, it still leads to an accuracy drop of about $20\%$ on CIFAR-10 dataset. Also, to control privacy leakage, DPSGD has to start with a model pre-trained using nonprivate labeled data, and then carefully fine-tunes a few layers using private data.

Privacy using cryptographic protocols.

In distributed learning setting with multiple data participants, it is possible for the participants to jointly train a model over their private inputs by employing techniques like homomorphic encryption [Gen09, GLN12, LLH+17] or secure multi-party computation (MPC) [Yao82, Bei11, MZ17, DGL+19]. Recent work proposed to use cryptographic methods to secure federated learning by designing a secure gradients aggregation protocol [BIK+16] or encrypting gradients [AHWM17]. These approaches slow down the computation by orders of magnitude, and may also require special security environment setups.

Instance Hiding.

Discussions of Potential Attacks

We have received proposals of attacks since the release of early versions of this manuscript. We would like to thank these comments, which helped enhance the security of InstaHide. We hereby summarize some of them and explain why InstaHide in its current design is not vulnerable to them.

Florian Tramèr [Tra20] suggested an attack pipeline which 1) firstly uses GANs to undo the random one-time sign flips of encrypted images, and 2) then runs standard image-similarity search between the recovered image and images in the public dataset.

We have evaluated this attack scenario in Section 5.3 (see ‘Demask using GAN’ for the first step, and ‘Uncover public images by similarity search’ for the second step). As shown, the GAN demasking step corrects about 1/4 of the flipped signs (see Figure 6), however this doesn’t appear enough to allow further attacks (see Figure 8).

Several designs of InstaHide could provide better practice of privacy under this attack: 1) setting a conservative upper threshold for the coefficients in mixing (e.g. 0.65 in our experiments) makes it harder to train the demasking GAN. 2) To alleviate the threat of image-similarity search for public image retrieval, we use randomly cropped patches from public images. This could enlarge the search space of pubic images by some large constant factor. We also suggest using a very large public dataset (e.g. ImageNet) if possible.

Braverman’s attack.

Braverman’s attack can be seen as similar in spirit to the attack on vanilla Mixup in Section 2.2, with the difference that it needs images to behave like Gaussian vectors for higher moments, and not just inner products. In the empirical study, we find 1) the gaussianity assumption is not so good for real images 2) the shrinkage of candidate search space by Braverman’s attack is small for $k=4$ and almost disappears for $k=6$.

To alleviate the risk of Bravermen’s attack, we reemphasize our suggestions in Section 6: 1) use a large public dataset and use random cropping as the preprocessing step. This will increase the original search space of public images; 2) use a larger $k$ (e.g. 6) if possible (3) maybe use a high quality GAN instead of the public dataset for mixing.

Carlini et al.’s attack.

Carlini et al. [CDG+20] gave an attack to recover private images in the most vulnerable application of InstaHide - when the InstaHide encryptions are revealed to the attacker. The first step is to train a neural network on a public dataset for similarity annotation to infer whether a pair of InstaHide encryptions contain the same private image. With the inferred similarities of all pairs of encryptions, the attacker then runs a combinatorial algorithm (cubic time in size of private dataset) to cluster all encryptions based on their original private images, and finally uses a regression algorithm to recover the private images.

Carlini et al.’s attack is able to give high-fidelity recoveries on our challenge dataset of 100 private images, but several limitations may prevent the current attack from working in a more realistic setting:

The current attack runs in time cubic in the dataset size, and it can’t directly attack an individual encryption. Running time was not an issue for attacking our challenge set, which consisted of 5,000 encrypted images derived from 100 images. But feasibility on larger datasets becomes challenging.

The challenge dataset corresponded to an ambitious form of security, where the encrypted images themselves are released to the world. The more typical application is a Federated Learning scenario where the attacker observes gradients computed using the inputs. When InstaHide is adopted in Federated Learning, the attacker only observes gradients computed on encrypted images. The attacks in this paper do not currently apply to that scenario. A possible attack to recover the original images may require recovering encrypted images from the gradients [ZLH19, GBDM20] as the first step.

Conclusion

InstaHide is a practical instance-hiding method for image data for private distributed deep learning.

InstaHide uses the Mixup method with a one-time secret key consisting of a pixel-wise random sign-flipping mask and samples from the same training dataset (Inside-dataset InstaHide) or a large public dataset (Cross-dataset InstaHide). The proposed method can be easily plugged into any existing distributed learning pipeline. It is very efficient and incurs minor reduction in accuracy. Maybe modifications of this idea can further alleviate the loss in accuracy that we observe, especially as $k$ increases.

We hope our analysis of InstaHide’s security on worst-case vectors will motivate further theoretical study, including for average-case settings and for adversarial robustness. In Appendix D, we suggest that although InstaHide can be formulated as a phase retrieval problem, classical techniques have failed as attacks.

We have tried statistical and computational attacks against InstaHide without success. To encourage other researchers to try new attacks, we release a challenge dataset of encrypted images.

Acknowledgments

This project is supported in part by Princeton University fellowship, Ma Huateng Foundation, Schmidt Foundation, Simons Foundation, NSF, DARPA/SRC, Google and Amazon AWS. Arora and Song were at the Institute for Advanced Study during this research.

We would like to thank Amir Abboud, Josh Alman, Boaz Barak, and Hongyi Zhang for helpful discussions, and Mark Braverman, Matthew Jagielski, Florian Tramèr, Nicholas Carlini and his team for suggesting attacks.

References

Appendix

The appendix is organized as follows: Appendix A reviews Instance hiding. Appendix B provides more details for two attacks on Mixup schemes in Section 2. Appendix C discusses $k$-SUM, a well-known fine-grained complexity problem that is related to the worst-case security argument of InstaHide. Appendix D shows the connection between InstaHide and phase retrieval. Finally, Appendix E provides experimental details.

Appendix A Instance Hiding

In the classical setting of instance hiding [AFK87] in cryptography, a computationally-limited Alice is trying to get more powerful computing services Bob1 and Bob2 to help her compute a function $f$ on input $x$, without revealing $x$. The simplest case is that $f$ is a linear function over a finite field (e.g., integers modulo a prime number). Then Alice can pick a random number $r$ and “hide” the input $x$ by asking Bob1 for $f(x+r)$ and Bob2 for $f(r)$, and then infer $f(x)$ from the two answers. When all arithmetic is done modulo a prime, it can be shown that neither Bob1 nor Bob2 individually learns anything (information-theoretically speaking) about $x$. This scheme can also be applied to compute polynomials instead of linear functions.

InstaHide is inspired by the special case where there is a single computational agent Bob1. Alice has to use random values $r$ such that she knows $f(r)$, and simply ask Bob1 to supply $f(x+r)$. Note that such a random value $r$ would be use-once (also called nonce in cryptography); it would not be reused when trying to evaluate a different input.

Appendix B Attacks on Mixup

Here we provide more details for the attacks discussed in Section 2.

B.1 Don’t mix up the same image multiple times

Let us continue with the vision task. This attack argues that given a pair of Mixup images $\widetilde{x}_{1}$ and $\widetilde{x}_{2}$, by simply checking $\langle\widetilde{x}_{1},\widetilde{x}_{2}\rangle$, the attacker can determine with high probability whether $\widetilde{x}_{1}$ and $\widetilde{x}_{2}$ are derived from the same image. We show this by a simple case with $k=2$ in Theorem B.1, where $k$ is the number of images used to generate a Mixup sample.

Part 1. First, we can expand $\langle{x}_{3}+x_{1},{x}_{2}+x_{2}^{\prime}\rangle$,

For each fixed $u\in\{x_{3},x_{1}\}$ and each fixed $v\in\{x_{2},x_{2}^{\prime}\}$, using Lemma B.8, we have

where $c_{1}>1$ is some sufficiently large constant.

Since $x_{1},x_{2},x_{2},x_{3}$ are independent random Gaussian vectors, taking a union bound over all pairs of $u$ and $v$, we have Lemma B.8, we have

We can lower bound $|\langle{x}_{3}+x_{1},{x}_{3}+x_{2}\rangle|$ in the following sense,

For a fixed $x_{3}$, we can lower bound $\|x_{3}\|_{2}^{2}$ with Lemma B.5,

Since $x_{1},x_{2},x_{3}$ are independent random Gaussian vectors, using Lemma B.8, we have

where $c_{1}>1$ is some sufficiently large constant.

holds with probability $1-\delta/n^{2}-3\delta/n^{2}=1-4\delta/n^{2}$. ∎

With Theorem B.1, we have with probability $1-\delta$, we have :

where the forth step follows from choice $c_{1}$ and $c_{2}$, the fifth step follows from assumption in Lemma statement, and the last step follows from $\beta>1$.

B.2 Attacks that run in |𝒳|𝒳|\mathcal{X}| time

This attack says that, if a cross-dataset Mixup sample $\widetilde{x}$ is generated by mixing 1 sample from a privacy-sensitive original dataset and $k-1$ samples from a public dataset (say ImageNet [DDS+09]), then the attacker can crack the $k-1$ samples from the public dataset by simply checking the inner product between $\widetilde{x}$ and all images in the public dataset. We show this formally in Theorem B.3.

We remark that the proof of Theorem B.3 is similar to the proof of Theorem B.1.

Part 1. We can rewrite $\langle\widetilde{x},x_{t^{\prime}}\rangle$ as follows:

For each fixed $i\in[k]$ and each fixed $t^{\prime}\notin[k]$, using Lemma B.8, we have

where $c_{1}>1$ is some sufficiently large constant.

Since $x_{1},x_{2},\cdots,x_{k},x_{t^{\prime}}$ are independent random Gaussian vectors, taking a union over all $i\in[k]$, we have

Taking a union bound over all $t^{\prime}\in[n]\backslash[k]$, we have

We can lower bound $|\langle\widetilde{x},x_{t}\rangle|$ as follows:

First, we can bound $\|x_{t}\|_{2}^{2}$ with Lemma B.5,

For each $i\in[k]\backslash\{t\}$, using Lemma B.8, we have

where $c_{1}>1$ is some sufficiently large constant.

Taking a union bound over all $i\in[k]\backslash\{t\}$, we have

holds with probability $1-\delta/n^{2}-\delta(k-1)/n^{2}=1-\delta k/n^{2}$.

Taking a union bound over all $t\in[k]$, we complete the proof. ∎

With Theorem B.3, we have with probability $1-\delta$, we have : for all $t\in[k]$ and $t^{\prime}\notin[k]$,

where the forth step follows from the choice of $c_{1}$ and $c_{2}$, the fifth step follows from the assumption in the Lemma statement, and the last step follows from $\beta>1$.

B.3 Chi-square concentration and Bernstein inequality

We state two well-known probability tools in this section.The major of idea of the provable results in this section is $p$-th moment concentration inequality (see Lemma 3.1 in [CLS20] as an example). The inner product “attack” for Mixup is based on $p=2$. The inner product “attack” for InstaHide is based on $p=4$ (suggested by [Bra20]). One is the concentration inequality for Chi-square and the other is Bernstein inequality.

First, we state a concentration inequality for Chi-square:

Let $X\sim{\cal X}_{k}^{2}$ be a chi-squared distributed random variable with $k$ degrees of freedom. Each one has zero mean and $\sigma^{2}$ variance. Then

We state the Bernstein inequality as follows:

Let $X_{1},\cdots,X_{n}$ be independent zero-mean random variables. Suppose that $|X_{i}|\leq M$ almost surely, for all $i\in[n]$. Then, for all $t>0$,

B.4 Inner product between a random Gaussian vector a fixed vector

The goal of this section is to prove Lemma B.7. It provides a high probability bound for the absolute value of inner product between one random Gaussian vector with a fixed vector.

Let $u_{1},\cdots,u_{d}$ denote i.i.d. random Gaussian variables where $u_{i}\sim{\cal N}(0,\sigma_{1}^{2})$.

Next, we can upper bound $|u_{i}|$ and $|u_{i}e_{i}|$.

Take $t_{1}=\sqrt{2\log(d/\delta)}\sigma_{1}$, then for each fixed $i\in[d]$, we have, $|u_{i}|\leq\sqrt{2\log(d/\delta)}\sigma_{1}$ holds with probability $1-\delta/d$.

Taking a union bound over $d$ coordinates, with probability $1-\delta$, we have : for all $i\in[d]$, $|u_{i}|\leq\sqrt{2\log(d/\delta)}\sigma_{1}$.

Let $E_{1}$ denote the event that, $\max_{i\in[d]}|u_{i}e_{i}|$ is upper bounded by $\sqrt{2\log(d/\delta)}\sigma_{1}\|e\|_{\infty}$. $\Pr[E_{1}]\geq 1-\delta$.

Using Bernstein inequality (Lemma B.6), we have

Taking a union bound with event $E_{1}$, we have $\Pr[|\langle u,e\rangle|\geq t]\leq 2\delta$. Finally, rescaling $\delta$ finishes the proof. ∎

B.5 Inner product between two random Gaussian vectors

The goal of this section is to prove Lemma B.8. It provides a high probability bound for the absolute value of inner product between two random (independent) Gaussian vectors.

Let $u_{1},\cdots,u_{d}$ denote i.i.d. random Gaussian variables where $u_{i}\sim{\cal N}(0,\sigma_{1}^{2})$ and $e_{1},\cdots,e_{d}$ denote i.i.d. random Gaussian variables where $e_{i}\sim{\cal N}(0,\sigma_{2}^{2})$.

Then, for any failure probability $\delta\in(0,1/10)$, we have

First, using Lemma B.5, we compute the upper bound for $\|e\|_{2}^{2}$

Take $t=\log(1/\delta)$, then with probability $1-\delta$,

Second, we compute the upper bound for $\|e\|_{\infty}$ (the proof is similar to Lemma B.7)

We define $t$ and $t^{\prime}$ as follows

Therefore, rescaling $\delta$ completes the proof. ∎

Appendix C Computational hardness results of d𝑑d-dimensional k𝑘k-SUM

The basic components in InstaHide schemes are inspired by computationally hard problems derived from the classic SUBSET-SUM problem: given a set of integers, decide if there is a non-empty subset of integers whose integers sum to . It is a version of knapsack, one of the Karp’s 21 NP-complete problems [Kar72]. The $k$-SUM [Eri95] is the parametrized version of the SUBSET-SUM. Given a set of integers, one wants to ask if there is a subset of $k$ integers sum to . The $k$-SUM problem can be solved in $O(n^{\lceil k/2\rceil})$ time. For any integer $k\geq 3$ and constant $\epsilon>0$, whether $k$-SUM can be solved in $O(n^{\lfloor k/2\rfloor-\epsilon})$ time has been a long-standing open problem. Patrascu [Pat10], Abboud and Lewi [AL13] conjectured that such algorithm doesn’t exist.

It is natural to extend definition from one-dimensional scalar/number case to the high-dimensional vector case. For $d$-dimensional $k$-sum over finite field, Bhattacharyya, Indyk, Woodruff and Xie [BIWX11] have shown that any algorithm that solves this problem has to take $\min\{2^{\Omega(d)},n^{\Omega(k)}\}$ time unless Exponential Time Hypothesis is false. Here, Exponential Time Hypothesis is believed to be true, it states that there is no $2^{o(n)}$ time to solve 3SAT with $n$ variables.

In this work, we observe that privacy of InstaHide can be interpreted as $d$-dimensional $k$-SUM problem and thus could be intractable and safe. For real field, $d$-dimensional is equivalent to $1$-dimensional due to [ALW14]. Therefore, Patrascu [Pat10], Abboud and Lewi [AL13]’s conjecture also suitable for $d$-dimensional $k$-SUM problem, and several hardness results in $d=1$ also can be applied to general $d>1$ directly.

We hereby provide a detailed explanation for the $d$-dimensional $k$-SUM problem. Let us start with the special case of $d=1$ and all values are integers.

Given a set of integers, if there is a subset of integers whose integers sum to .

SUBSET-SUM is a well-known NP-complete problem.

The $k$-SUM is the parameterized version of the SUBSET-SUM,

Given a set of integers, if there is a subset of $k$ integers whose integers sum to .

The $k$-SUM problem can be solved in $O(n^{\lceil k/2\rceil})$ time. For $k=3$, Baran, Demaine and Patrascu [BDP08] introduced algorithm that takes $O(n^{2}/\log^{2}n)$ time. It has been a longstanding open problem to solve $k$-SUM for some $k$ in time $O(n^{\lceil k/2\rceil-\epsilon})$. Therefore, complexity communities made the following conjecture,

There does not exist a $k\geq 2$, an $\epsilon>0$, and a randomized algorithm that succeeds (with high probability) in solving $k$-SUM in time $O(n^{\lceil k/2\rceil-\epsilon})$.

Although the $n^{\lceil(k/2)\rceil}$ hardness for $k$-SUM is not based on anything else at the moment, an $n^{\Omega(k)}$ lower bound under ETH is already known due to Abboud and Lewi [AL13]. Recently, Abboud [Abb19] also shows a weaker $n^{\Omega(k/\log k)}$ lower bound under the Set Cover Conjecture, but it has the advantage that it holds for any fixed $k>2$.

C.2 k𝑘k Vector Sum over Finite Field

Now we move onto the $d$-dimensional $k$ vector sum problem.

A more general definition that fits the InstaHide setting is called $k$-VEC-T-SUM (where $T$ denotes the “target”),

$d$-dimensional $k$-VEC-T-SUM and $d$-dimensional $k$-VEC-SUM are considered to have the same hardness. Bhattacharyya, Indyk, Woodruff and Xie [BIWX11] proved hardness result for the problem defined in Definition C.4 and Definition C.5. Before stating the hardness result, we need to define several basic concepts in complexity. We introduce the definition of 3SAT and Exponential Time Hypothesis(ETH). For the details and background of 3SAT problem, we refer the readers to [AB09].

Given $n$ variables and $m$ clauses conjunctive normal form CNF formula with size of each clause at most $3$, the goal is to decide whether there exits an assignment for the $n$ boolean variables to make the CNF formula be satisfied.

We state the definition of Exponential Time Hypotheis, which can be thought of as a stronger assumption than P$\neq$NP.

There is a $\delta>0$ such that 3SAT problem defined in Definition C.6 cannot be solved in $O(2^{\delta n})$ running time.

Now, we are ready to state the hardness result.

Assuming Exponential Time Hypothesis (ETH), any algorithm solves $k$-VEC-SUM or $k$-T-VEC-SUM requires $\min\{2^{\Omega(d)},n^{\Omega(k)}\}$ time.

C.3 k𝑘k Vector Sum over Bounded Integers

For the bounded integer case, we can also define the $k$-VEC-SUM problem,

For integers $k$, $n$, $M$, $d>0$, the $k$-VEC-SUM problem is to determine, given vectors $x_{1},\cdots,x_{n},x\in[0,kM]^{d}$, if there is a size-$k$ subset $S\subseteq[n]$ such that $\sum_{i\in S}x_{i}=z$.

Abboud, Lewi, and Williams proved that the 1-dimensional $k$-VEC-SUM and $d$-dimensional $k$-VEC-SUM are equivalent in bounded integer setting,

Due to the above result, as long as we know a hardness result for classical $k$-SUM, then it automatically implies a hardness result for $d$-dimensional $k$-VEC-SUM.

Appendix D Phase Retrieval

We primarily want to minimize $m$ (which is the number of measurements), the running time of ${\cal A}$(which is the decoding time) and column sparsity of $\Phi$.

D.2 Phase Retrieval

We primarily want to minimize $m$ (which is the number of measurements), the running time of ${\cal A}$ (which is the decoding time) and column sparsity of $\Phi$.

The state-of-the-art result is due to [LN18].

The problem formulation of compressive sensing and phase retrieval have many variations, for more details we refer the readers to several surveys [Pri13, Has16, Nak19, Son19].

D.3 Comments on Phase Retrieval

We would like to point out that although InstaHide can be formulated as a phase retrieval problem, classical techniques will fail as an attack.

To show the phase retrieval formulation of InstaHide, we first argue applying the random pixel-wise sign is equivalent to taking the absolute value, namely (A): ${x}=\sigma\circ f_{\text{mix}}(x)$ is equivalent to (B): ${x}=|f_{\text{mix}}(x)|$, where $f_{\text{mix}}(\cdot)$ denote the mixing function. This is because, to reduce from B to A, we can just take absolute value in each coordinate; and to reduce from A to B, we can just select a random mask (i.e., $\sigma$) and apply it.

Appendix E Experiments

Table 3 provides Implementation details of the deep models. All experiments are conducted on 24 NVIDIA RTX 2080 Ti GPUs.

E.2 Details of attacks

We hereby provide more details for the attacks in Section 5.3.

Algorithm 3 describes the gradients matching attack [ZLH19]. This attack aims to recover the original image from model gradients computed on it. In the InstaHide setting, the goal becomes to recover $\widetilde{x}$, the image after InstaHside. As we have shown in Section 4, the upper bound on the privacy loss in gradients matching attack is the loss when attacker is given $\widetilde{x}$.

E.3 Results of the Kolmogorov–Smirnov Test

In order to further understand whether there is significant difference among distributions of InstaHide encryptions of different $x$’, we run the Kolmogorov-Smirnov (KS) test [Kol33, Smi48].

Specifically, we randomly pick 10 different private $x_{i}$’s, $i\in$, and generate 400 encryptions for each $x_{i}$ (4,000 in total). We sample $\widetilde{x}_{ij},j\in$, the encryption of a given $x_{i}$, and run KS-test under two different settings:

$\widetilde{x}_{ij}$ v.s. all encryptions (All): KS-test(statistics of $\widetilde{x}_{ij}$, statistics of all $\widetilde{x}_{uj}$’s for $u\in$)

$\widetilde{x}_{ij}$ v.s. encryptions of other $x_{u}$’s, $u\neq i$ (Other): KS-test(statistics of $\widetilde{x}_{ij}$, statistics of all $\widetilde{x}_{uj}$’s for $u\in,u\neq i$)

For each $x_{i}$, we run the Kolmogorov–Smirnov test for 50 independent $\widetilde{x}_{ij}$’s, and report the averaged p-value as below (a higher p-value indicates a higher probability that $\widetilde{x}_{ij}$ comes from the tested distribution). We test 7 different statistics: pixel-wise mean, pixel-wise standard deviation, total variation, and the pixel values of 4 random locations. KS-test results suggest that, there is no significant differences among distribution of encryptions of different images.