2020

Is Private Learning Possible with Instance Encoding?

Carlini, Nicholas, Deng, Samuel, Garg, Sanjam et al.

Understand

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.

Built on

J. Edmonds and R. M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems,” Journal of the ACM (JACM) , vol. 19, no. 2, pp. 248–264, 1972
1972
Earlier work this paper cites.
J. Kelsey, B. Schneier, D. Wagner, and C. Hall, “Cryptanalytic attacks on pseudorandom number generators,” in International workshop on fast software encryption . Springer, 1998, pp. 168–188
1998
Earlier work this paper cites.
M. Matsumoto and T. Nishimura, “Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator,” ACM Transactions on Modeling and Computer Simulation (TOMACS) , vol. 8, no. 1, pp. 3–30, 1998
1998
Earlier work this paper cites.
I. Dinur and K. Nissim, “Revealing information while preserving privacy,” in Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , 2003, pp. 202–210
2003
Earlier work this paper cites.
Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE transactions on image processing , vol. 13, no. 4, pp. 600–612, 2004
2004
Earlier work this paper cites.
C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of cryptography conference . Springer, 2006, pp. 265–284
2006
Earlier work this paper cites.
N. Homer, S. Szelinger, M. Redman, D. Duggan, W. Tembe, J. Muehling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig, “Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays,” PLoS Genet , vol. 4, no. 8, p. e1000167, 2008
2008
Earlier work this paper cites.
S. Sankararaman, G. Obozinski, M. I. Jordan, and E. Halperin, “Genomic privacy and limits of individual detection in a pool,” Nature genetics , vol. 41, no. 9, pp. 965–967, 2009
2009
Earlier work this paper cites.
C. Gentry, A fully homomorphic encryption scheme . Stanford university Stanford, 2009, vol. 20, no. 9
2009
Earlier work this paper cites.
M. N. Wernick, Y. Yang, J. G. Brankov, G. Yourganov, and S. C. Strother, “Machine learning in medical imaging,” IEEE signal processing magazine , vol. 27, no. 4, pp. 25–38, 2010
2010
Earlier work this paper cites.
M. Hardt and K. Talwar, “On the geometry of differential privacy,” in Proceedings of the forty-second ACM symposium on Theory of computing , 2010, pp. 705–714
2010
Earlier work this paper cites.
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization.” Journal of Machine Learning Research , vol. 12, no. 3, 2011
2011
Earlier work this paper cites.
S. Halevi, Y. Lindell, and B. Pinkas, “Secure computation on the web: Computing without simultaneous interaction,” in Advances in Cryptology – CRYPTO 2011 , P. Rogaway, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 132–150
2011
Earlier work this paper cites.
J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy, data processing inequalities, and statistical minimax rates,” 2014
2014
Earlier work this paper cites.
R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization: Efficient algorithms and tight error bounds,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science . IEEE, 2014, pp. 464–473
2014
Earlier work this paper cites.
A. Beimel, H. Brenner, S. P. Kasiviswanathan, and K. Nissim, “Bounds on the sample complexity for private learning and private data release,” Machine learning , vol. 94, no. 3, pp. 401–437, 2014
2014
Earlier work this paper cites.
M. Fredrikson, E. Lantz, S. Jha, S. Lin, D. Page, and T. Ristenpart, “Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing,” in 23rd { \{ USENIX } \} Security Symposium ( { \{ USENIX } \} Security 14) , 2014, pp. 17–32
2014
Earlier work this paper cites.

Similar

I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in Advances in neural information processing systems , 2014, pp. 2672–2680
2014
Cited alongside, same era.
C. Dwork, A. Roth et al. , “The algorithmic foundations of differential privacy.” Foundations and Trends in Theoretical Computer Science , vol. 9, no. 3-4, pp. 211–407, 2014
2014
Cited alongside, same era.
M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security , 2015, pp. 1322–1333
2015
Cited alongside, same era.
C. Dwork, A. Smith, T. Steinke, J. Ullman, and S. Vadhan, “Robust traceability from trace amounts,” in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science . IEEE, 2015, pp. 650–669
2015
Cited alongside, same era.
R. Shokri and V. Shmatikov, “Privacy-preserving deep learning,” in Proceedings of the 22nd ACM SIGSAC conference on computer and communications security , 2015, pp. 1310–1321
2015
Cited alongside, same era.
K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for federated learning on user-held data,” arXiv preprint arXiv:1611.04482 , 2016
Original
2016
Cited alongside, same era.
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security , 2016, pp. 308–318
2016
Cited alongside, same era.
M. Bun and M. Zhandry, “Order-revealing encryption and the hardness of private learning,” in Theory of Cryptography Conference . Springer, 2016, pp. 176–206
2016
Cited alongside, same era.
X. Wu, M. Fredrikson, S. Jha, and J. F. Naughton, “A methodology for formalizing model-inversion attacks,” in 2016 IEEE 29th Computer Security Foundations Symposium (CSF) . IEEE, 2016, pp. 355–370
2016
Cited alongside, same era.
M. Backes, P. Berrang, M. Humbert, and P. Manoharan, “Membership privacy in microrna-based studies,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security , 2016, pp. 319–330
2016
Cited alongside, same era.
R. Zhang, P. Isola, and A. A. Efros, “Colorful image colorization,” in European conference on computer vision . Springer, 2016, pp. 649–666
2016
Cited alongside, same era.
P. Mohassel and Y. Zhang, “Secureml: A system for scalable privacy-preserving machine learning,” in 2017 IEEE Symposium on Security and Privacy (SP) . IEEE, 2017, pp. 19–38
2017
Cited alongside, same era.

Then

M. Chase, R. Gilad-Bachrach, K. Laine, K. E. Lauter, and P. Rindal, “Private collaborative neural network learning.” IACR Cryptol. ePrint Arch. , vol. 2017, p. 762, 2017
2017
Later among the works it cites.
E. Hesamifard, H. Takabi, and M. Ghasemi, “Cryptodl: Deep neural networks over encrypted data,” arXiv preprint arXiv:1711.05189 , 2017
Original
2017
Later among the works it cites.
A. Hosny, C. Parmar, J. Quackenbush, L. H. Schwartz, and H. J. Aerts, “Artificial intelligence in radiology,” Nature Reviews Cancer , vol. 18, no. 8, pp. 500–510, 2018
2018
Later among the works it cites.
P. Mohassel and P. Rindal, “Aby3: A mixed protocol framework for machine learning,” in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security , 2018, pp. 35–52
2018
Later among the works it cites.
M. Bun, J. Ullman, and S. Vadhan, “Fingerprinting codes and the price of approximate differential privacy,” SIAM Journal on Computing , vol. 47, no. 5, pp. 1888–1938, 2018
2018
Later among the works it cites.
Y. Long, V. Bindschaedler, L. Wang, D. Bu, X. Wang, H. Tang, C. A. Gunter, and K. Chen, “Understanding membership inferences on well-generalized learning models,” arXiv preprint arXiv:1802.04889 , 2018
Original
2018
Later among the works it cites.
J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, and S. Wanderman-Milne, “JAX: composable transformations of Python+NumPy programs,” 2018. [Online]. Available: http://github.com/google/jax
2018
Later among the works it cites.
M. X. Chen, B. N. Lee, G. Bansal, Y. Cao, S. Zhang, J. Lu, J. Tsay, Y. Wang, A. M. Dai, Z. Chen et al. , “Gmail smart compose: Real-time assisted writing,” in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining . ACM, 2019, pp. 2287–2295
2019
Later among the works it cites.
A. Salem, Y. Zhang, M. Humbert, M. Fritz, and M. Backes, “Ml-leaks: Model and data independent membership inference attacks and defenses on machine learning models,” in Network and Distributed Systems Security Symposium 2019 . Internet Society, 2019
2019
Later among the works it cites.
L. Melis, C. Song, E. De Cristofaro, and V. Shmatikov, “Exploiting unintended feature leakage in collaborative learning,” in 2019 IEEE Symposium on Security and Privacy (SP) . IEEE, 2019, pp. 691–706
2019
Later among the works it cites.
S. Wagh, D. Gupta, and N. Chandran, “Securenn: 3-party secure computation for neural network training,” Proceedings on Privacy Enhancing Technologies , vol. 2019, no. 3, pp. 26–49, 2019
2019
Later among the works it cites.
Y. Huang, Z. Song, K. Li, and S. Arora, “Instahide: Instance-hiding schemes for private distributed learning,” ICML , 2020
2020
Closest in time.
M. Raynal, R. Achanta, and M. Humbert, “Image obfuscation for privacy-preserving machine learning,” arXiv preprint arXiv:2010.10139 , 2020
Original
2020
Closest in time.
Nokia, “Nokia announces 2020 Bell Labs Prize winners,” 2020. [Online]. Available: https://www.nokia.com/about-us/news/releases/2020/12/03/nokia-announces-2020-bell-labs-prize-winners
2020
Closest in time.
Y. Huang, Z. Song, K. Li, and S. Arora, “A challenge for instahide,” 2020. [Online]. Available: https://github.com/Hazelsuko07/InstaHide_Challenge
2020
Closest in time.
Z. Liu, Z. Wu, C. Gan, L. Zhu, and S. Han, “Datamix: Efficient privacy-preserving edge-cloud inference,” in European Conference on Computer Vision (ECCV) , 2020
2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…