Is the Hard-Label Cryptanalytic Model Extraction Really Polynomial?

Deep Neural Networks (DNNs) have attracted significant attention, and their internal models are regarded as valuable intellectual assets. Extracting a model via oracle access to a DNN is conceptually similar to extracting a secret key via oracle access to a block cipher. Consequently, cryptanalytic techniques, particularly differential-like attacks, have been actively explored recently. ReLU-based DNNs are the most common architectures. While early works (e.g., Crypto 2020, Eurocrypt 2024) assume access to exact output logits, more recent works (e.g., Asiacrypt 2024, Eurocrypt 2025) focus on the hard-label setting, where the attacker observes only the final classification result (e.g., "dog" or "car"). Notably, Carlini et al. (Eurocrypt 2025) demonstrated that model extraction is feasible in polynomial time even under this restricted setting. In this paper, we show that a key assumption of their attack becomes increasingly unrealistic as the target depth grows. While prior works have 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 inevitably incurs a non-negligible error. A straightforward solution is to recover these parameters from a state switch, but observing such a switch becomes exponentially harder as the depth increases, implying that hard-label extraction is not always polynomial time. To address this limitation, we propose cross-layer extraction. Rather than extracting the 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 model extraction approaches. The source code is available at https://github.com/ECSIS-lab/hard-label-cross-layer-extraction.