Paper 2026/2061

Normal Alignment: Improved Cryptanalytic Sign Recovery on Hard-Label Networks

Abstract

At EUROCRYPT 2025, Carlini {\em 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 {\em et al.}'s sign‑recovery method ({which we call \em 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 {\em 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, {\em eSOE + Alignment}, by combining {\em 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 {\em et al.}'s sign‑recovery method would require exponential‑time enumerations involving $2^{52}$ or $2^{82}$ guesses of the signs, respectively.