Can instance encoding achieve privacy-preserving learning?
Is Private Learning Possible with Instance Encoding?
The authors formalize instance-encoding privacy and prove an impossibility result, and propose a reconstruction attack on InstaHide that recovers 100 challenge images.
The attacker obtains the encoded dataset S̃ (and the public data P used by the scheme) and cannot access the original data S; the goal is to distinguish or reconstruct the original training samples from S̃. The single-encoding attack on InstaHide additionally assumes the attacker knows the private data distribution and the public dataset P.
- Can training data first be encoded and then given to an ordinary learner, thereby obtaining privacy without sacrificing accuracy? The authors study the theoretical limits of such instance-encoding schemes and examine whether the representative scheme InstaHide is truly private.
- The authors formalize instance encoding and its privacy definition, prove an impossibility theorem against distinguishing attacks, and design a three-stage reconstruction attack on InstaHide: take absolute values to remove signs, cluster encodings from the same source with a neural network, and solve linear systems of equations to recover the original images.
- The attack reconstructs high-fidelity original images on CIFAR-10, CIFAR-100 and the InstaHide Challenge, including all 100 images in the challenge; the single-encoding attack recovers all 3 public mixed images in 69% of the 100 encodings; the authors state that increasing MixUp-k instead makes the attack better.
- The authors point out that the single-encoding attack requires assuming the attacker knows the private data distribution and the public dataset P, and cannot be used on the challenge because the challenge did not release public images; pixel-level exact recovery is mathematically impossible and can only be achieved by exploiting an implementation flaw (PRNG).
- Evaluated models
- InstaHide
- Benchmarks
- CIFAR-10CIFAR-100InstaHide ChallengeImageNet (32x32)STL-10
- Metrics
- distinguishing advantagereconstruction fidelitySSIM相似度网络分类准确率
The authors study whether instance encoding can give non-private learning algorithms privacy, and present a practical attack against InstaHide. The paper establishes two attack models for instance encoding and its privacy definition, first giving an impossibility result under the stronger model, then demonstrating a practical attack against InstaHide under the weaker model; InstaHide is a scheme proposed by Huang, Song, Li and Arora at ICML'20.
Related events and news
0 events · 1 news mentions
News that mentions this paper
- Nicholas Carlini Writingcites the paper's id or linkInstaHide 获贝尔实验室奖二等奖引发争议
We showed this in a recent paper (and if you're reading this within the next few days, we'll be giving a talk on this paper at the PPML workshop at NeurIPS).
Paper analysis
What problem does this paper attempt to solve?
Can instance encoding provide privacy without sacrificing accuracy? The authors give a negative theoretical result and break InstaHide.
Core question: can an instance encoding function be designed such that a non-private learning algorithm trains an accurate model on the encoded data while the original data stays hidden from attackers?
- Problem setting: neural networks are increasingly trained on sensitive user data (e.g., medical images, email text). Existing privacy schemes either require a trusted central party, rely on cryptographic techniques such as secure multi-party computation (high computation and communication overhead), or use differential privacy (high accuracy cost). The authors ask: is there another way to achieve private learning without sacrificing performance or accuracy?
- Shortcomings of existing methods: the authors state that recently proposed instance encoding schemes (such as InstaHide) lack rigorous privacy definitions and rely on heuristic security arguments.
- Core observation: if the encoded data can still train an accurate model, then the encoding itself leaks information sufficient to distinguish different datasets or different instances; distinguishing attacks are harder to defend against than reconstruction attacks.
- Paper contributions: formalize instance encoding and its privacy (two attack models); prove impossibility results against distinguishing attacks (Theorem 1, 2); propose a practical reconstruction attack on InstaHide, recovering all 100 private images in its challenge.
- Threat model:
- Attacker goal: learn sensitive information about the original dataset S from the encoded dataset S̃, the strongest form being full reconstruction of training samples (Definition 6).
- Attacker knowledge: can access the encoded dataset S̃; if the encoding scheme uses public data P, the attacker can also access P; cannot access the original data S.
- Attacker capability: polynomial time; the single-encoding attack on InstaHide additionally assumes knowledge of the private data distribution and the public dataset P.
- Victim system: a learning protocol that uses instance encoding (such as InstaHide) to protect training data privacy.
What related research exists?
Related work covers sample complexity lower bounds for private learning, membership inference and model inversion attacks, and cryptographic private training schemes.
Sample complexity lower bounds for private learning
- Duchi et al. (2014), Hardt and Talwar (2010), Bun and Zhandry (2016) — give tight bounds for parameter/probability estimation via packing arguments. Bun et al. (2018) prove sample complexity lower bounds for differentially private answering of a large number of counting queries. Bassily et al. (2014), Beimel et al. (2014) prove sample complexity lower bounds for differentially private PAC learning. The authors state that Theorem 1 can be viewed as a (dimension-independent) lower bound on the sample complexity of private PAC learning, and that its two datasets have consistent labels and are compatible with the concept function, which is closer to realistic scenarios.
Privacy attacks against machine learning models
- Shokri et al. (2017) et al. — membership inference attacks; Fredrikson et al. (2014, 2015), Wu et al. (2016) — model inversion attacks; Dinur and Nissim (2003), Dwork et al. (2015, 2017) et al. — reconstruction attacks. The authors state that this paper's attack on InstaHide is a type of reconstruction attack.
Training schemes with provable privacy
- Mohassel and Zhang (2017), Bonawitz et al. (2016) et al. — secure multi-party computation; Gentry (2009), Hesamifard et al. (2017) — fully homomorphic encryption; Dwork et al. (2006), Abadi et al. (2016) — differential privacy. The authors state that these schemes can provide provable privacy guarantees, but at high performance and accuracy cost.
Encoding-based privacy schemes
- Huang et al. (ICML 2020) — InstaHide, which linearly mixes multiple images and randomly flips pixel signs, and won second place in the 2020 Bell Labs Prize; Raynal et al. (2020) — image obfuscation; Liu et al. (ECCV 2020) — DataMix private inference. The authors state that these schemes rely on heuristic security arguments, and that this paper's attack can likely also defeat similar constructions.
Positioning: The authors state that this paper formalizes the natural (cryptographic) privacy notion of instance encoding and proves its impossibility, and then directly refutes InstaHide's heuristic privacy argument with a reconstruction attack.
How does the paper address this problem?
First formalize instance encoding and the privacy definition and prove the impossibility of distinguishing attacks, then design a three-stage reconstruction attack on InstaHide.
The overall approach has two parts: theoretically, it defines a cryptographic-style indistinguishability privacy notion for instance encoding and proves that any utility-preserving encoding cannot resist distinguishing attacks; practically, it exploits the distinguishability of InstaHide encodings to first cluster encodings of the same origin and then solve a linear system to reconstruct the original images.
Problem formalization and privacy definitions
- Dataset encoding mechanism (Definition 1): an encoding function E maps a dataset S to an encoded dataset S̃; if instances and labels are encoded separately it is called decomposable, and if each encoding depends on at most r samples it is called r-local. InstaHide is a decomposable and local special case.
- Utility definitions: original-data accuracy (Definition 2) requires the model's risk on the original distribution to be bounded; encoded accuracy (Definition 3) requires the model to predict, from an encoding x̃, the label c(x) of some original instance x in it.
- Privacy definitions: the dataset distinguishing attack (Definition 4) requires the attacker to distinguish the encodings of two datasets differing in one same-label sample, with advantage p − 1/2; the instance distinguishing attack (Definition 5) gives the attacker only a single encoding; the instance recovery attack (Definition 6) requires the attacker to output a point within distance γ of some training sample.
Theoretical impossibility results
- Theorem 1 (limits of dataset encoding): if the protocol has accuracy at least 51% on the original data, then for any non-trivial concept class, the attacker can choose a concept c and two datasets S1, S2 differing in one (same-label) sample and distinguish their encodings with probability 1/2 + Ω(1/n).
- Theorem 2 (limits of instance encoding): if the concept class is rich enough (contains m balanced and mutually independent concepts) and the protocol's encoded accuracy is 1/2 + δ, then the attacker can distinguish the encodings of two random instances with probability at least 0.99 − O((1−2δ)/(1−2/√m)).
- Theorem 5 (single-concept variant): if the encoding achieves balanced encoded accuracy on a single concept, then either an efficient distinguishing attack exists, or a classifier with accuracy arbitrarily close to 1 can be extracted from it; the authors state that this constitutes an obstacle to the privacy-utility tradeoff for learning tasks with an upper bound on accuracy.
Reconstruction attack on InstaHide
- Attack pipeline (Figure 2): 1) take the absolute value of all encodings to eliminate sign flips; 2) train a neural network to judge whether two encodings share an original image, build a similarity graph and cluster the set of encodings corresponding to each original image; 3) given the clustering results and mixing coefficients λ, solve the underdetermined nonlinear system of equations by gradient descent to reconstruct the original image.
- Similarity network: Wide ResNet-28, input is two encodings concatenated along the channel dimension (32×32×6), trained with Adam (learning rate 0.1, weight decay 5·10⁻⁴) for 10⁶ steps; training data uses 32×32 ImageNet as the public set and the CIFAR-10/100 and STL-10 training sets as private images; held-out validation accuracy 91%. The second stage trains a new network with 4 reference encodings, raising accuracy to 96%.
- Clustering and assignment: greedy expansion yields candidate sets, then k-means (k = |X|) clustering; then min cost max flow assigns each encoding to exactly 2 sets and each set exactly N encodings, recovering the mapping φ′.
- Image recovery: the mixing coefficients λ can be read directly from the encoding labels (when mixing same-class images, guess equal split); solve the least-squares problem M · abs(A′) + σ = abs(B) by gradient descent minimizing |σ|22; the authors state that because the system is underdetermined, pixel-level exact recovery is mathematically impossible, but high-similarity reconstructions can be obtained. Finally, a 73-parameter tiny network performs color saturation correction.
Single-encoding attack (N = 1)
- Assumes the attacker knows the private data distribution and the public dataset P; first train a GAN to learn the "recoloring" mapping abs(x) ↦ x to recover the sign mask σ, then perform SSIM similarity search over the public dataset, subtracting the most similar public images one by one (guessing mixing weight λ = 1/k) to recover the private images.
What experiments did the paper conduct?
Reconstructs all 100 original images on CIFAR-10, CIFAR-100 and the InstaHide Challenge, and evaluates the single-encoding and large-k settings.
Experimental setup
- Attacked scheme: InstaHide (Huang et al., ICML 2020), using the code open-sourced by its authors to construct encoded datasets; the challenge version is the strongest configuration k = 6.
- Datasets: CIFAR-10, CIFAR-100 (the first 100 images of each test set are taken as private images, encoded into 5,000 images); InstaHide Challenge (5,000 encodings corresponding to 100 private images of unknown distribution, N = 50); the similarity network is trained with 32×32 ImageNet as the public set and the CIFAR-10/100 and STL-10 training sets as private images.
- Attack models: Wide ResNet-28 similarity network (validation accuracy 91%); second-stage set similarity network (96%); GAN used for recoloring in the single-encoding attack; 73-parameter network used for color correction.
- Metrics: Reconstruction quality is presented as visual fidelity (Figure 1, 3, 4 and all images in Appendix C); the single-encoding attack reports the proportion of public mixed images recovered; the theoretical part reports distinguishing advantage.
- Computation: The CIFAR attack takes 2 GPU hours + 2 CPU hours in total; the challenge attack is completed within 1 hour; PRNG state extraction takes 120 CPU hours (about 1 hour with 100 cores in parallel).
- Number of repetitions and statistical tests: Not reported in the paper.
Main results
Swipe horizontally to read the table
Setting Number of private images Number of encodings Result Source CIFAR-10 (k = 6) 100 5,000 100 reconstructed, visually high fidelity Figure 3a, Figure 5 CIFAR-100 (k = 6) 100 5,000 100 reconstructed, visually high fidelity Figure 3b, Figure 6 InstaHide Challenge (k = 6, N = 50) 100 5,000 All 100 reconstructed Figure 1, Figure 7 Challenge (PRNG implementation flaw attack) 100 5,000 Pixel-level exact reconstruction Figure 8, Appendix B - The authors state that the attack is "extremely effective" and that the reconstructions are almost visually identical to the original images; the challenge ground truth was obtained through a cryptanalytic attack on the PRNG in the InstaHide implementation (Appendix B).
- The authors state that the attack has no hyperparameters (other than image size), and that the same configuration works on CIFAR-10, CIFAR-100 and the challenge.
- For Figure 1, the top row (ground truth obtained by the PRNG attack) and the bottom row (reconstructions by the generic attack), at the text level it can only be confirmed that the authors state the two are highly consistent; the specific image content cannot be judged from the text.
Single-encoding attack (N = 1)
- What was tested: Only one encoding is released per private image (k = 4); the private images are the first 100 images of the CIFAR-10 test set, and the public set is the remaining 9,900 images.
- Results: Of the 100 encodings, 69% recover all 3 public mixed images, and 85% recover at least 2/3; the authors state that GAN recoloring recovers most of the mask σ in most cases, and when successful the private image is extracted almost perfectly (Figure 4).
- Authors' interpretation: If InstaHide is still to provide security when only a single encoding is released, then its security must partly depend on the secrecy of the "public" mixed data P.
Analysis of larger MixUp-k
- What was tested: Analysis of the effect of increasing k on the main attack (theoretical analysis, no new experimental numbers).
- Results and authors' interpretation: The authors state that increasing k instead makes the attack better — because the assumption of approximating the public-image noise σ as Gaussian noise becomes more accurate as k increases, and as k → ∞ the noise after averaging the public images tends to zero; even for k > 100, InstaHide is still broken under the same attack.
Other ablations and analyses
- Number of reference encodings for the similarity network: diminishing returns beyond 4 (Section 4.3.4).
- The greedy clustering parameter M = N/4 is effective in practice (Section 4.3.3).
- If InstaHide randomly selects the set size rather than exactly N, preliminary experiments show that the attack success rate is unchanged (Section 4.4).
- PRNG attack: exhaustively search 2³² seeds, verifying each candidate takes about 0.1 ms; if InstaHide released only abs(e), this attack would not be feasible (Appendix B).
What are some points that can be further explored?
The authors discuss the assumptions of the single-encoding attack and the impossibility of pixel-level recovery, and call for schemes to provide falsifiable privacy claims.
Limitations and future directions noted by the authors
- Assumptions of the single-encoding attack: The attack assumes the attacker knows the private data distribution and the public dataset P; the authors state that this assumption is strong, and that because the challenge did not release public images, this attack cannot be used on the InstaHide Challenge (Section 4.8.1).
- Impossibility of pixel-level recovery: Because the system of equations is underdetermined, the authors state that pixel-level exact recovery of the original images is mathematically impossible, and reconstruction can only achieve high similarity to the original images (Section 4.2).
- Room for improvement in Theorem 1: The authors state that Theorem 1 might be improved by incorporating the data dimension, but that being dimension-independent is itself an advantage (Section 1.3).
- Extension to other schemes: The authors state that similar heuristic constructions also appear in other private training and inference schemes, and that these schemes can likely be defeated by similar attacks (Section 5).
- Advice for defenders: The authors state that proposed schemes should provide precise, falsifiable privacy claims rather than heuristic security arguments (Section 5).
Scope of experiments
- The only attacked scheme is InstaHide; the datasets are CIFAR-10, CIFAR-100 and the InstaHide Challenge, and all images are 32×32.
- Settings for the main attack evaluation: k = 6, N = 50 (challenge) or 5,000 encodings corresponding to 100 original images (CIFAR); settings for the single-encoding attack evaluation: k = 4, N = 1.
- Reconstruction quality is presented mainly through images; the paper does not report quantitative similarity metrics for reconstruction (such as SSIM values) or the reconstruction success rate for each dataset.
- The paper does not report the number of repetitions of the attack, statistical significance tests, or human evaluation.
- The theoretical results concern distinguishing attacks; the authors explicitly state that their results do not rule out the possibility of privacy against instance recovery attacks (Section 2.2.1).
Summarize the main content of the paper
Instance encoding cannot simultaneously preserve utility and indistinguishability privacy; the reconstruction attack on InstaHide recovered all 100 challenge images.
An attack paper combining theory and practice, studying whether "first encoding the training data, then training with an ordinary learner" can provide privacy without sacrificing accuracy.
- Problem: Existing private training schemes (MPC, differential privacy) are costly, and instance-encoding schemes (such as InstaHide) claim to protect privacy at low cost, but lack a rigorous privacy definition.
- Theoretical results: The authors formalize instance encoding and two distinguishing attack models, and prove that any encoding protocol with accuracy of at least 51% on the original data admits an attack that distinguishes two datasets differing by only one same-label sample with probability 1/2 + Ω(1/n) (Theorem 1); for rich concept classes, the distinguishing advantage of instance encoding can reach 0.99 − O((1−2δ)/(1−2/√m)) (Theorem 2).
- Attack on InstaHide: Three-stage reconstruction — take absolute values to eliminate sign flips, cluster encodings from the same source with a Wide ResNet-28 similarity network (91% validation accuracy), and solve a least-squares system to reconstruct the original images; all 100 images are reconstructed on CIFAR-10, CIFAR-100 and the InstaHide Challenge (k = 6, 5,000 encodings for 100 original images), and the authors state that the reconstructions are almost visually identical to the original images.
- Security parameter analysis: The single-encoding attack (assuming knowledge of the public dataset P) recovers all 3 public mixed images in 69% of the 100 encodings and at least 2/3 in 85%; the authors state that increasing MixUp-k instead makes the attack better, because the Gaussian noise approximation is more accurate.
- Implementation flaw: Appendix B reports that the InstaHide implementation uses the Mersenne Twister PRNG, and that exhaustively searching 2³² seeds (120 CPU hours) can extract the state and reconstruct pixel-exactly; the authors state that this flaw can be easily fixed and is not a fundamental problem of InstaHide.
- Authors' conclusion: Any encoding scheme that can train an accurate model cannot provide indistinguishability guarantees like MPC; the authors call for future privacy schemes to provide precise, falsifiable privacy claims.