Polynomial Time Cryptanalytic Extraction of Neural Network Models
Adi Shamir
Abstract:
Billions of dollars and countless GPU hours are currently spent on training Deep Neural Networks (DNNs) for a variety of tasks. Thus, it is essential to determine the difficulty of extracting all the parameters of such neural networks when given access to their black-box implementations. Many versions of this problem have been studied over the last 30 years, and the best current attack on ReLU-based deep neural networks was presented at Crypto’20 by Carlini, Jagielski, and Mironov. It resembles a differential chosen plaintext attack on a cryptosystem, which has a secret key embedded in its black-box implementation and requires a polynomial number of queries but an exponential amount of time (as a function of the number of neurons).
In this talk, I will improve this attack by developing several new techniques that make it possible to extract with arbitrarily high precision all the real-valued parameters of a ReLU-based DNN using a polynomial number of queries AND a polynomial amount of time. We demonstrate its practical efficiency by applying it to a full-sized neural network for classifying the CIFAR10 dataset, which has 3072 inputs, 8 hidden layers with 256 neurons each, and about 1.2 million neuronal parameters. An attack following the approach by Carlini et al. requires an exhaustive search over 2^256 possibilities. Our attack replaces this with our new techniques, which require only 30 minutes on a 256-core computer.
Bio:
Adi Shamir is the Borman Professor of Computer Science at the Weizmann Institute in Israel. Adi specializes in cryptographic schemes and protocols, with special emphasis on cryptanalysis. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identification scheme (along with Uriel Feige and Amos Fiat) and one of the inventors of differential cryptanalysis. He has made numerous other contributions to the fields of cryptography and computer science, including the Shamir secret sharing scheme, the first linear time algorithm for 2-satisfiability and showing the equivalence of the complexity classes PSPACE and IP.