Normal alignment improves sign recovery efficiency in hard-label neural networks
Normal Alignment: Improved Cryptanalytic Sign Recovery on Hard-Label Networks
Cryptography and Security
Summary
Extracting information from certain protected deep neural networks is very hard because existing methods often guess signs incorrectly, causing huge slowdowns. The authors introduce Normal Alignment, a new statistical method that matches patterns in the neural network to predict signs more accurately. This reduces mistakes and avoids expensive guessing steps, allowing full sign recovery in polynomial time, even on complex models. Their approach works particularly well on deeper layers where older methods struggled.
What this means in practice
- •For security analysts: Perform more efficient cryptanalysis on protected neural networks to recover internal sign information without exponential-time computation.
- •For machine learning engineers: Diagnose and debug behavior of deep neural networks by accurately recovering neuron sign patterns in challenging hard-label settings.
Authors
Shi Tang, Zirui Chen, Yongjia Su, Zhengchao Gao, Lingyue Qin, Xiaoyang Dong
Abstract
At EUROCRYPT 2025, Carlini et al. proposed a breakthrough in the cryptanalytic extraction on hard-label (S1) deep neural networks (DNNs), demonstrating polynomial-time signature and sign recovery. However, Carlini et al.'s sign-recovery method (which we call Future Toggle) suffers only a marginal advantage over random guessing, producing high-confidence wrong sign predictions in deeper layers. Such errors trigger expensive exponential-time enumeration. This work presents Normal Alignment, a novel statistical sign-recovery approach for S1 DNNs. Drawing on the expected length difference between projected normals of adjacent decision facets at dual points, our method infers neuron signs via normal-signature alignment. It delivers higher voting accuracy and pushes erroneous predictions to low-confidence ranks, which further enables a more efficient combined method, eSOE + Alignment, by combining Normal Alignment with the hard-label SOE extension. This combined strategy removes heavy enumeration overhead and realizes exact polynomial-time full sign recovery. Experiments demonstrate the effectiveness of our method, especially for deep layers. For example, with our method, the signs for CIFAR-10 (architecture 192-64$\times$8-10) and MNIST (architecture 64-96$\times$3-32-10) models can be fully recovered in polynomial time; in contrast, Carlini et al.'s sign-recovery method would require exponential-time enumerations involving $2^{52}$ or $2^{82}$ guesses of the signs, respectively.