Is Private Learning Possible with Instance Encoding?

Nicholas Carlini; Samuel Deng; Sanjam Garg; Somesh Jha; Saeed Mahloujifar; Mohammad Mahmoody; Shuang Song; Abhradeep Thakurta; Florian Tramer

Source-linked AI summary

Is Private Learning Possible with Instance Encoding?

Nicholas Carlini, Samuel Deng, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, Shuang Song, Abhradeep Thakurta, Florian Tramer

arXiv:2011.05315v2Nov 10, 2020cs.CRcs.CVcs.LG

TL;DR

The paper asks whether instance encoding can let ordinary learners train privately without sacrificing accuracy. It formalizes two attack models, proves impossibility results for stronger distinguishing privacy, and demonstrates high-fidelity reconstruction attacks against InstaHide in the weaker model.

Problem
The central question is whether encoded training inputs can hide sensitive data while allowing a non-private learner to retain useful accuracy.
Method
The paper formalizes instance encoding and two privacy attack models, then develops theoretical distinguishing attacks and practical reconstruction attacks against InstaHide.
Results
Useful instance encodings cannot guarantee strong distinguishing privacy, and InstaHide permits nearly identical reconstruction of its private images.
Takeaways & Limitations
Instance encoding does not provide meaningful privacy guarantees for InstaHide and cannot generally combine utility with strong distinguishing privacy.
Takeaways & Limitations
The impossibility result assumes the encoder receives information about the concept function only through the dataset, whereas direct knowledge of the concept could let it hide the input data.

Abstract

from arXiv · show

A private machine learning algorithm hides as much as possible about its training data while still preserving accuracy. In this work, we study whether a non-private learning algorithm can be made private by relying on an instance-encoding mechanism that modifies the training inputs before feeding them to a normal learner. We formalize both the notion of instance encoding and its privacy by providing two attack models. We first prove impossibility results for achieving a (stronger) model. Next, we demonstrate practical attacks in the second (weaker) attack model on InstaHide, a recent proposal by Huang, Song, Li and Arora [ICML'20] that aims to use instance encoding for privacy.

1 Introduction

The paper formalizes privacy risks in instance encoding and proves that useful encodings cannot guarantee strong distinguishing privacy. It then shows that InstaHide, despite encoding images before ordinary learning, can be practically reconstructed with high fidelity.

The Instance Encoding Problem: Instance encoding aims to preserve learning accuracy while hiding sensitive training data before a non-private learner processes it.The encoded dataset is released to the adversary and then used for model training.
Practical Attacks on InstaHide: The paper attacks InstaHide by clustering encodings from repeated training epochs, merging them through a noisy linear system, and neutralizing sign flips with absolute values.The attack exploits distinguishability predicted by the theoretical analysis.
Practical Attacks on InstaHide: More InstaHide mixing strengthens the reconstruction attack, while precise knowledge of public parameters enables near-perfect recovery even from a single encoding.The paper also reports a linear-time attack and concludes that InstaHide is not private.
Theoretical Impossibility Results: The impossibility results rule out encoding schemes that simultaneously preserve utility and even weak distinguishing privacy.The results apply broadly, including settings where classifiers achieve accuracy bounded away from 1.
Theoretical Impossibility Results: Theoretical results show that useful encodings cannot resist distinguishing attacks: an adversary can distinguish datasets differing in one example with probability 1/2 + Ω(1/n).A second result gives stronger instance-level distinguishing attacks under additional assumptions about concept richness or encoding utility.
Practical Attacks on InstaHide: In the InstaHide challenge, 5,000 encoded images derived from 100 originals enabled nearly identical reconstruction of all 100 private images.Figure 1 shows ten examples, while the complete recovered set appears in the appendix.

2 Privacy with Instance Encoding: Definitions

The paper formalizes dataset and instance encodings, their accuracy properties, and attack-based privacy notions. It emphasizes that privacy must be analyzed through the information each encoding message leaks, rather than assumed from the protocol’s final output.

Definitions: A dataset encoding mechanism E maps a labeled dataset S to an encoded dataset S̃, potentially using randomness.
Definitions: Encodings may be decomposable into separate instance and label algorithms, and r-local when each encoded example depends on at most r training examples.
Scope: The framework covers local and central encodings, randomized mechanisms, public datasets, and InstaHide as a decomposable, local instance-encoding special case.
Accuracy: Accuracy is defined both on original examples and on encoded instances, including balanced accuracy across possible labels.
Threat model: Efficient attacks are modeled as polynomial-time adversaries, while physical privacy alone does not account for leakage from the protocol’s final outcome.
Threat model: Strong physical privacy comparable to MPC cannot generally be achieved by one-message dataset encodings unless the task is trivial or a trusted party runs the learner.

3 Barriers for Privacy with Instance Encoding

The paper proves that useful accuracy and strong privacy are fundamentally difficult to combine with instance encoding. The barriers apply both to rich concept classes and to single concepts, under different assumptions about the encoding and learning task.

Dataset encoding: The formal dataset attack distinguishes neighboring, label-consistent datasets, and its running time is essentially that of the learning algorithm.
Scope and limitations: The impossibility results do not cover encoders given the concept function directly, which could output a description of that concept instead of the input data.
Rich concept classes: For rich concept classes, encoded accuracy implies an instance-distinguishing attack, so useful encoding accuracy cannot coexist with cryptography-strength privacy.
Single concept: The single-concept barrier allows the encoding to depend on the concept, but assumes balanced accuracy and decomposability; otherwise the rich-class proof does not directly apply.
Single concept: For a single balanced concept, either the encoding is distinguishable or an efficient learner can extract an almost-perfect classifier from it.

4 An Attack on InstaHide

The authors attack InstaHide by removing sign hiding, clustering encodings generated from shared source images, and reconstructing the originals. The attack remains effective across datasets and defense settings, including a single-encoding case.

4.2 Attack Overview: The pipeline takes absolute values to neutralize sign flipping, clusters encodings sharing source images, and solves for approximate originals.A neural network supplies pairwise similarity, cliques recover source-image groups, and gradient descent solves the resulting under-determined nonlinear system.
4.2 Attack Overview: The reconstruction step cannot recover originals pixel-perfectly because the underlying nonlinear system is under-determined, but high qualitative and quantitative similarity remains possible.
4.3 Clustering: 91% to 96%: using four examples of a source image improves the similarity network’s prediction accuracy and reduces its error rate.Additional examples produce diminishing returns beyond four.
4.7 Results: The attack works across CIFAR-10 and CIFAR-100, and its released configuration breaks InstaHide on both datasets and the challenge.The authors report that Figure 3 shows reconstructed examples from both datasets.
4.7 Results: The attack is computationally efficient, requiring 2 GPU hours and 2 CPU hours in total.The initial all-pairs distance computation dominates the runtime at two hours on one GPU.
4.8.1 Attacking InstaHide With a Single Encoding: With one encoding per private image, a GAN re-colors the absolute-value mixture before subtracting the most similar public images to extract the private image.The attack recovers all three public mixing images in 69% of cases and at least two of three in 85%.
4.8 Attacking Security Parameters: Increasing k does not improve security: reconstruction becomes better as k grows, while even k > 100 remains vulnerable.A separate attack also breaks the scheme when only N = 1 epoch of data is released.

5 Conclusion

The conclusion formalizes privacy goals for instance encoding, proves barriers to cryptographic-level indistinguishability, and demonstrates reconstruction attacks against InstaHide.

The authors formalize natural cryptographic privacy notions for instance encoding and prove strong barriers against achieving them.
Instance-encoding schemes that support accurate model training cannot provide indistinguishability guarantees comparable to MPC.
Reconstruction attacks fully break InstaHide’s challenge and contradict the heuristic privacy arguments underlying its construction.
Similar heuristic constructions for private training and inference may be vulnerable to related attacks.
Meaningful private learning without sacrificing performance remains an open goal, motivating precise and falsifiable privacy claims instead of ad-hoc security arguments.

A.1 Proof of Theorem 3

Theorem 3 constructs a dataset-distinguishing adversary by converting a model trained on encoded data into a test procedure and extending the distinction through hybrid arguments.

The proof trains a model on an encoded dataset and distinguishes source distributions by testing its predictions on samples from one concept.
Hybrid arguments transform distinguishability between differently labeled distributions into distinguishability for distributions consistent with a common concept function.
The constructed distributions Da and Db are label-consistent with selected pairs among c1, c2, and 1 − c1.
Averaging over the adversaries shows that at least one distinguishing advantage is at least (0.99 − 2δ(n))/3.
The challenge samples are jointly generated so their labels agree under c1, enabling the resulting adversary to operate within the theorem’s required labeling condition.

A.2 Proof of Theorem 4

Theorem 4 builds a distinguishing adversary from classifiers learned under multiple concept functions, using their encoded accuracy and richness to identify a useful challenge.

The adversary learns classifiers for multiple concept functions, each with encoded accuracy at least 1 − ϵ(n), by repeating training as needed.
The expected time to obtain these classifiers is O(m · n/(1 − δ(n))).
The attack samples two same-label points and distinguishes their encodings using the difference between classifier outputs on the points and the encoded challenge.
The proof concludes that the attack finishes once its constructed adversary achieves the required advantage or accuracy condition.

A.3 Proof of Theorem 5

Theorem 5 turns an encoded classifier into a majority-vote inference procedure and uses carefully sampled same-label pairs to obtain a reconstruction-style distinguishing attack.

The attack trains an encoded-data classifier, constructs a majority-vote classifier from fresh encodings, and tests a fresh encoding of one challenge point.
The majority-vote classifier uses k = −20 ln(τ)/τ^2 fresh encodings for each input.
If the derived classifier has error exceeding τ, the proof finds a same-label pair satisfying the attack’s conditions with probability at least τ^2/8.
The adversary can find such a pair using 8/τ^2 samples in expectation.
The attack’s first and third stages require O(m/δ(m)) time and O(m/τ^2) time, while evaluating the derandomized majority-vote classifier takes O(m/τ^3).

B Pixel-Perfect Break InstaHide due to Implementation Flaws

Implementation flaws in InstaHide enable attacks that break its algorithmic foundation and can achieve pixel-perfect reconstruction of the original dataset.

Implementation-independent attacks break the algorithmic foundation of InstaHide, making any implementation vulnerable.
The implementation-specific weaknesses are not fundamental to InstaHide and could be corrected, although they still permit pixel-perfect dataset recovery.
Two implementation weaknesses enable an additional reconstruction attack: insecure randomness and excessive precision in released encoded pixels.

B.1 PRNG State Extraction

The InstaHide implementation uses a deterministic Mersenne Twister for security-sensitive encoding randomness, allowing attackers to recover its state by brute force and undo masking.

A PRNG initialized with the same state reproduces the same output sequence, providing the basis for state recovery.
Mersenne Twister randomness controls image selection, λ values, public-image mixing, and random masks, despite not being intended for security-sensitive use.
Brute-forcing 2^32 initial seeds takes about 0.1 milliseconds per candidate and 120 CPU hours, reduced to just over an hour using 100 cores.
Recovering the seed reveals φ and λ and permits undoing multiplication by the random mask σ; releasing only abs(e) would prevent this attack.
Using a random {−1, 1}^d mask preserves sign information that can be used to decrypt encoded images, giving mathematically identical techniques different practical failure modes.

B.1.1 High-Fidelity Image Reconstruction

After recovering the PRNG-derived encoding information and removing sign flipping, the prior reconstruction attack recovers images from the InstaHide challenge.

Figure 1 compares the reconstruction attack’s results on the InstaHide challenge with images extracted by the prior attack, while Figure 8 presents all 100 reconstructions.
The recovered φ, λ, and sign-corrected E provide the inputs needed to apply the reconstruction attack from Section 4.5.3.
The attack therefore produces high-fidelity reconstructed images from the challenge data.

B.1.2 Pixel-Perfect Refinement

Recovering which public images were mixed into each encoding creates an over-determined system that can yield pixel-perfect reconstruction, though the challenge’s unreleased public dataset prevents direct application there.

Knowing the PRNG seed reveals both φ and the public images used in each encoded image, creating an over-determined reconstruction system.
A footnote notes that stronger mathematical analysis could recover the complete PRNG state if brute-force search were computationally intractable.
With M original images of dimension d, replacing σ-related variables leaves M · d variables, and more encoded than original images allows perfect solution.
The authors cannot mount this attack on the InstaHide Challenge because its public dataset is unreleased, but confirm it works on CIFAR-10.

C Additional Figures

The additional figures visualize reconstructions for CIFAR-10, CIFAR-100, and the 100-image InstaHide Challenge under two attack strategies.

CIFAR-10: Figure 5 pairs each of the first 50 CIFAR-10 images with its reconstruction.
CIFAR-100: Figure 6 pairs each of the first 50 CIFAR-100 images with its reconstruction.
InstaHide Challenge: Figure 7 shows reconstructions of all 100 InstaHide Challenge images produced by the fully general attack.
InstaHide Challenge: Figure 8 shows reconstructions of all 100 InstaHide Challenge images produced by an improved PRNG cryptanalytic attack exploiting InstaHide implementation weaknesses.