# Is the Hard-Label Cryptanalytic Model Extraction Really Polynomial?

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 25 references that are in the map.
- First posted on arXiv 8 Oct 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [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)
- [MEGEX: Data-Free Model Extraction Attack against Gradient-Based Explainable AI](https://mlsanity.com/paper/2107.08909/) (2021)
- [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)
- [Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting](https://mlsanity.com/paper/2410.05750/) (2024)
- [Beyond Slow Signs in High-fidelity Model Extraction](https://mlsanity.com/paper/2406.10011/) (2024)
- [Navigating the Deep: End-to-End Extraction on Deep Neural Networks](https://mlsanity.com/paper/2506.17047/) (2025)
- [Delving into Cryptanalytic Extraction of PReLU Neural Networks](https://mlsanity.com/paper/2509.16620/) (2025)

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

- [Data Augmentation Techniques to Reverse-Engineer Neural Network Weights from Input-Output Queries](https://mlsanity.com/paper/2511.20312/) (2025)
- [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) have attracted significant attention, and their internal models are now considered valuable intellectual assets. Extracting such a model via oracle access to a DNN is conceptually similar to extracting a secret key from a block cipher. Consequently, cryptanalytic techniques, particularly differential-like attacks, have been actively explored. ReLU-based DNNs are the most common and widely deployed architectures. While early works (e.g., Crypto 2020, Eurocrypt 2024) assume access to exact output logits, which are typically not exposed, more recent works (e.g., Asiacrypt 2024, Eurocrypt 2025) focus on the hard-label setting, where only the final classification result (e.g., "dog" or "car") is available. Notably, Carlini et al. (Eurocrypt 2025) showed that model extraction is feasible in polynomial time even under this restricted setting. In this paper, we show that a key assumption underlying their attack becomes increasingly unrealistic as the target depth grows. While prior works noted neurons whose activation states rarely change, we analyze their concrete impact on hard-label extraction: even a single neuron that is (almost) always active can prevent the attack from proceeding unless its parameters are recovered, and ignoring it incurs a non-negligible error. A straightforward solution is to extract these parameters by observing a state switch of such a neuron, but observing such a switch becomes exponentially harder as depth increases, implying that hard-label extraction is not always polynomial time. To address this limitation, we propose a novel attack called cross-layer extraction. Rather than extracting secret parameters (e.g., weights and biases) directly, we exploit cross-layer interactions to recover them from deeper layers, reducing query complexity and addressing limitations of existing approaches.