Is Private Learning Possible with Instance Encoding?

### Overview This presentation examines the viability of achieving privacy-preserving machine learning through instance encoding, focusing on the InstaHide scheme introduced at ICML. Instance encoding adds a pre-processing step where training data is converted into intermediate encodings intended to prevent information leakage while enabling models to train directly on the encoded data. The authors evaluate InstaHide's empirical security by completely breaking its official challenge dataset, present theoretical impossibility results bounding instance encoding privacy when combined with accuracy, and critically assess the role of security challenges in machine learning security research.

### Key Topics - **Instance Encoding in Machine Learning:** The concept of transforming raw training data into privacy-preserving intermediate encodings that allow downstream algorithms to train without direct access to private samples. - **InstaHide Architecture:** A mechanism combining linear combinations of private images with samples from an unlabeled public dataset, followed by random pixel sign flipping (masking). - **Attack on the InstaHide Challenge:** A practical reconstruction attack utilizing neural-network-based clustering followed by image recovery to reconstruct private training images. - **Theoretical Barriers:** Formal security definitions and impossibility theorems demonstrating fundamental trade-offs between instance encoding accuracy and cryptographic privacy. - **Evaluation of Security Challenges:** The limitations of relying on static empirical challenges without formal, falsifiable security models and threat definitions.

### Technical Details - **InstaHide Encoding Mechanism:** InstaHide draws images from both a private labeled dataset and an auxiliary public dataset, creates a linear combination of these images, and applies a masking layer that randomly flips the sign of each pixel with probability 1/2. - **Challenge Reconstruction Attack:** The InstaHide challenge provided 50 encodings for each of 100 private images using an undisclosed public dataset. The attack operates in two phases: first, a neural network clusters encodings based on the underlying private images they encode; second, an image recovery step reconstructs the original images from each cluster, achieving near-perfect recovery of all 100 challenge images. - **Alternative Threat Model Attack:** Assuming auxiliary knowledge where the attacker has access to the public dataset used during encoding, the authors developed an efficient attack that scales linearly with data size and reconstructs a private image from just a single encoding. - **Theoretical Impossibility Bounds:** The authors formulated a security game where an adversary distinguishes which of two identically labeled instances was encoded. They proved that if a protocol achieves accuracy 1/2 + ε on encoded data across two concept functions, a polynomial-time adversary achieves advantage 1/2 + Ω(ε) in breaking privacy. When accuracy is defined on original data, the adversary's advantage is bounded by 1/2 + 1/n (where n is sample complexity), ruling out cryptographic levels of privacy.

### Takeaways - **InstaHide is Insecure:** InstaHide fails to provide robust privacy, as demonstrated by the complete reconstruction of its official challenge dataset and efficient single-encoding recovery under public dataset knowledge. - **Fundamental Incompatibility:** Strong cryptographic privacy and high utility/accuracy cannot be achieved simultaneously via instance encoding alone. - **Challenges Cannot Replace Formal Models:** Security challenges should serve only as necessary conditions for security and cannot substitute for clear threat models and falsifiable claims. The broader machine learning security field must transition from informal evaluations toward rigorous, mathematically defined threat models.