InstaHide’s Sample Complexity When Mixing Two Private Images

Abstract

Inspired by InstaHide challenge [Huang, Song, Li and Arora'20], [Chen, Song and Zhuo'20] recently provides one mathematical formulation of InstaHide attack problem under Gaussian images distribution. They show that it suffices to use O(n_priv^k_priv - 2/(k_priv + 1)) samples to recover one private image in n_priv^O(k_priv) + poly(n_pub) time for any integer k_priv, where n_priv and n_pub denote the number of images used in the private and the public dataset to generate a mixed image sample. Under the current setup for the InstaHide challenge of mixing two private images (k_priv = 2), this means n_priv^4/3 samples are sufficient to recover a private image. In this work, we show that n_priv ( n_priv ) samples are sufficient (information-theoretically) for recovering all the private images.

Tasks

Reproductions