# Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting

arXiv: https://arxiv.org/abs/2410.05750 · HTML: https://mlsanity.com/paper/2410.05750/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 8 Oct 2024.

## Builds on (most cited first, 12 of 12)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [High Accuracy and High Fidelity Extraction of Neural Networks](https://mlsanity.com/paper/1909.01838/) (2019)
- [Model Reconstruction from Model Explanations](https://mlsanity.com/paper/1807.05185/) (2018)
- [Reverse-Engineering Deep ReLU Networks](https://mlsanity.com/paper/1910.00744/) (2019)
- [Cryptanalytic Extraction of Neural Network Models](https://mlsanity.com/paper/2003.04884/) (2020)
- [How far can we go without convolution: Improving fully-connected networks](https://mlsanity.com/paper/1511.02580/) (2015)
- [Polynomial Time Cryptanalytic Extraction of Neural Network Models](https://mlsanity.com/paper/2310.08708/) (2023)
- [Expand-and-Cluster: Parameter Recovery of Neural Networks](https://mlsanity.com/paper/2304.12794/) (2023)
- [An Exact Poly-Time Membership-Queries Algorithm for Extraction a three-Layer ReLU Network](https://mlsanity.com/paper/2105.09673/) (2021)
- [Beyond Slow Signs in High-fidelity Model Extraction](https://mlsanity.com/paper/2406.10011/) (2024)
- [Hard-Label Cryptanalytic Extraction of Neural Network Models](https://mlsanity.com/paper/2409.11646/) (2024)

## Built on by (most cited first, 9 of 9)

- [Navigating the Deep: End-to-End Extraction on Deep Neural Networks](https://mlsanity.com/paper/2506.17047/) (2025)
- [Is the Hard-Label Cryptanalytic Model Extraction Really Polynomial?](https://mlsanity.com/paper/2510.06692/) (2025)
- [Provably Learning Multi-Head Attention with Queries](https://mlsanity.com/paper/2608.03294/) (2026)
- [A Divide-and-Conquer Strategy for Hard-Label Extraction of Deep Neural Networks via Side-Channel Attacks](https://mlsanity.com/paper/2411.10174/) (2024)
- [Securing Transfer-Learned Networks with Reverse Homomorphic Encryption](https://mlsanity.com/paper/2505.14323/) (2025)
- [Train to Defend: First Defense Against Cryptanalytic Neural Network Parameter Extraction Attacks](https://mlsanity.com/paper/2509.16546/) (2025)
- [Data Augmentation Techniques to Reverse-Engineer Neural Network Weights from Input-Output Queries](https://mlsanity.com/paper/2511.20312/) (2025)
- [Can Watermarking Techniques Help Prevent LLM Model Stealing?](https://mlsanity.com/paper/2607.10794/) (2026)
- [End-to-End Hard-Label Cryptanalytic Model Extraction Using Efficient Sign Recovery](https://mlsanity.com/paper/2609.21941/) (2026)

## Abstract (arXiv)

Deep neural networks (DNNs) are valuable assets, yet their public accessibility raises security concerns about parameter extraction by malicious actors. Recent work by Carlini et al. (crypto'20) and Canales-Mart'inez et al. (eurocrypt'24) has drawn parallels between this issue and block cipher key extraction via chosen plaintext attacks. Leveraging differential cryptanalysis, they demonstrated that all the weights and biases of black-box ReLU-based DNNs could be inferred using a polynomial number of queries and computational time. However, their attacks relied on the availability of the exact numeric value of output logits, which allowed the calculation of their derivatives. To overcome this limitation, Chen et al. (asiacrypt'24) tackled the more realistic hard-label scenario, where only the final classification label (e.g., "dog" or "car") is accessible to the attacker. They proposed an extraction method requiring a polynomial number of queries but an exponential execution time. In addition, their approach was applicable only to a restricted set of architectures, could deal only with binary classifiers, and was demonstrated only on tiny neural networks with up to four neurons split among up to two hidden layers. This paper introduces new techniques that, for the first time, achieve cryptanalytic extraction of DNN parameters in the most challenging hard-label setting, using both a polynomial number of queries and polynomial time. We validate our approach by extracting nearly one million parameters from a DNN trained on the CIFAR-10 dataset, comprising 832 neurons in four hidden layers. Our results reveal the surprising fact that all the weights of a ReLU-based DNN can be efficiently determined by analyzing only the geometric shape of its decision boundaries.