PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Shi Tang, Zirui Chen, Yongjia Su, Zhengchao Gao, Lingyue Qin, Xiaoyang Dong

arXiv:2609.18751v1cs.CR

TL;DR

Future Toggle's weak sign predictions can leave deep-layer errors that require exponential enumeration. Normal Alignment infers signs from adjacent decision-facet normals, and combining it with hard-label SOE achieves exact polynomial-time full sign recovery in the reported experiments.

  • Problem

    Future Toggle's small advantage over random guessing can leave incorrectly recovered deep-layer signs at relatively high confidence, making full recovery require exponential enumeration.

    Source: Existing Sign Recovery Methods in S1… · p. 3

  • Method

    Normal Alignment compares projected normals of adjacent decision facets at dual points and aggregates valid votes to determine neuron signs.

    Source: §4.3 · p. 23, §7 · p. 27

  • Results

    eSOE+Alignment achieves exact polynomial-time full sign recovery, while eSOE+Toggle leaves incorrect signs that require exponential enumeration.

    Source: §2.1 · p. 6, §7 · p. 28

  • Takeaways & Limitations

    Normal Alignment's errors fall to low-confidence ranks, supporting its combination with hard-label SOE for complete sign recovery.

    Source: §2.1 · p. 6, §7 · p. 28

    Future Toggle's valid votes may be only slightly more likely than random guesses to be correct; the stated majority-vote bound assumes independent votes with a shared success probability.

    Source: Limitations of the Future Toggle · p. 13

Abstract

from arXiv · show

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.

1 Introduction

Hard-label extraction makes neuron-sign recovery central to polynomial-time model extraction, but Future Toggle can leave deep-layer errors that trigger exponential enumeration. Normal Alignment uses adjacent decision-facet normals, and its combination with hard-label SOE achieves exact polynomial-time recovery in the reported CIFAR-10 and MNIST experiments.

1 Introduction.

  • Cryptanalytic extraction recovers ReLU-network parameters layer by layer, first identifying unsigned neuron signatures and then determining their signs.The signature phase can be polynomial-time, while the earlier brute-force sign-recovery phase is exponential-time.Source: §1 · pp. 1–2

Hard-label extraction.

  • In S1, queries reveal only predicted class labels; Carlini et al. introduced polynomial-query, polynomial-time hard-label extraction using clustered dual points to recover signatures.Earlier hard-label sign recovery by Yi Chen et al. required exponential execution time; hard-label SOE typically recovers only the first hidden layer unless the network is sufficiently contractive.Source: Hard-label extraction · p. 2, Existing Sign Recovery Methods in S1… · p. 2

Existing Sign Recovery Methods in S1 and Their Limitations.

  • The passages report vote accuracies of 52%–57%; Future Toggle incorrectly recovered 9 of 64 layer-7 signs, including a 55.58%-confidence error ranked 20th among neurons by confidence.Source: Existing Sign Recovery Methods in S1… · p. 3

Our Contributions.

  • Normal Alignment compares the normals of the two decision facets adjacent to a dual point; the active-side normal is expected to be longer because it includes the target neuron's weight contribution.Votes are aggregated across dual points, and confidence is the fraction of valid votes supporting the majority sign.Source: Our Contributions · pp. 3–4
  • With 200 dual points, Normal Alignment reached 68.74% overall vote accuracy across hidden layers versus 60.89% for Future Toggle, with about 70% accuracy in deep layers versus around 53% in layers 3–7.Normal Alignment also used all dual points when adjacent decision-facet normals were successfully recovered; Future Toggle produced votes from only 2.26% of dual points in Layer 8.Source: Our Contributions · p. 4
  • On CIFAR-10, eSOE+Alignment recovered all 512/512 signs, and on MNIST all 320/320, achieving exact sign recovery in polynomial time; eSOE+Toggle recovered 469/512 and 296/320, respectively.Source: Our Contributions · p. 5

2 Preliminaries

The preliminaries define the ReLU-network setting and extraction target, then introduce the geometry and sign ambiguity used to formulate layer-wise sign recovery. They also distinguish hard-label from raw-output access and define complete-recovery complexity.

2.1 Notations and Definitions

  • eSOE+Alignment achieves complete sign recovery in polynomial time, whereas eSOE+Toggle requires exponential enumeration of unresolved signs.Complete recovery measures the time needed to recover all neuron signs correctly.Source: §2.1 · p. 6
  • A fixed activation pattern defines a linear neighborhood in which the ReLU network acts linearly, and the model is piecewise linear across such neighborhoods.The network alternates affine layer maps and componentwise ReLU operations.Source: §2.1 · pp. 5–6
  • S5 returns raw logits, while S1 returns only the predicted class label.The extraction problem focuses on S1 hard-label access.Source: §2.1 · p. 7, Assumptions · p. 9

Prefix and suffix maps of layer k.

  • Decision boundaries contain facets within linear neighborhoods; dual points lie on a target neuron's critical boundary and typically have adjacent facets.The network is decomposed into prefix and suffix maps around layer k.Source: Prefix and suffix maps of layer k · p. 7

2.2 Extraction Goal and Assumptions

  • After signature recovery, the remaining scalar's magnitude can be absorbed into outgoing weights, but its sign determines the neuron’s active side.Sign recovery identifies the true active side of each neuron.Source: §2.2 · p. 9

Extraction Goal.

  • The extraction goal is functional equivalence up to positive neuron rescaling and within-layer permutation, with sign recovery targeting layer k after signatures are known up to scalar.The assumptions include a known architecture, full-domain adaptive queries, and sufficiently precise computation.Source: Extraction Goal · p. 9, Assumptions · pp. 9–10

3 Existing Sign Recovery Methods in S1 Setting and their Limitations

The section reviews Future Toggle, which predicts a target neuron’s active side from distances to future toggles, and explains why tracing, discarded dual points, and weak votes limit it. It also describes raw-output and hard-label SOE methods, whose full-rank requirements constrain their use to sufficiently contractive networks.

3.1 Future Toggle in Hard-label Setting

  • Future Toggle predicts the target active side as the side that reaches a future-layer neuron toggle after the shorter distance from a dual point.A neuron toggle is an activation-state change that bends the visible decision boundary.Source: Motivation from Neuron Wiggle: Future… · p. 11

Motivation from Neuron Wiggle: Future Toggle

  • The distance heuristic uses toggle distance as a proxy for an unobserved rate of change: future-neuron preactivations tend to change faster on the active side.This statistical signal is motivated by the larger layer-(k+1) wiggle on the target active side for equal input perturbations.Source: Motivation from Neuron Wiggle: Future… · p. 11

Limitations of the Future Toggle.

  • As layer depth increases, recovered-layer bends rise from 0.87 to 12.45 while dual-point utilization falls from 99.74% to 3.21%.Bends from known layers require additional decision-facet normal recoveries, while repeated known-layer boundaries or failure to reach a future toggle can cause a dual point to be discarded.Source: Limitations of the Future Toggle · p. 13
  • Future Toggle’s mean vote accuracy ranges from 52.82% to 56.51%, and its last-hidden-layer searches produce only about 32 valid votes per 1,000 attempted points on average.The method’s two proxy relations are not guaranteed at every dual point, and last-layer searches instead terminate at class-boundary intersections whose measured distances can depend on different class boundaries and logit-change rates.Source: Limitations of the Future Toggle · pp. 13–14

The Raw-Output SOE Method

  • Raw-output SOE recovers unknowns from a linear system, but a single-input system’s rank is limited by its local prefix map and full recovery requires a sufficiently contractive architecture.Inactive neurons can be removed from the unknown vector; the remaining entries are uniquely determined when the coefficient matrix reaches full rank.Source: The SOE + Wiggle in Raw-Output Setting… · pp. 14–15, The Raw-Output SOE Method · p. 14
  • Raw-output SOE can combine systems from inputs with the same activation states in layers k onward but different earlier activation states, potentially increasing coefficient-matrix rank.When the combined rank reaches the number of remaining unknowns, those entries are uniquely determined.Source: The SOE + Wiggle in Raw-Output Setting… · p. 15

Hard-Label SOE

  • Hard-label SOE builds a linear system from perturbations at a class-transition point, but unique recovery requires full rank and therefore a strongly contractive architecture.The solution is unique up to a scalar multiple under the stated rank condition.Source: Hard-Label SOE · p. 16

4 Hard-Label Sign Recovery via Normal Alignment

The section recovers decision-facet normals from hard-label queries, then uses their projected lengths and alignments to infer neuron signs. Normal Alignment aggregates dual-point votes, with white-box validation reporting high overall accuracy across the evaluated models.

4.1 Recovering Decision-Facet Normals in S5/S1 Settings

  • Hard-label coordinate probes recover a decision-facet normal up to scale, and a small perturbation with a class-label check determines its sign.Coordinate ratios come from binary-searching back to the boundary after stepping along each basis direction.Source: §4.1 · pp. 16–17

Projected Decision-Facet Normal in the Input Space of Layer k.

  • When deeper-layer systems are rank deficient, the full facet normal may be nonunique, but its projection onto the control space is uniquely recoverable by least squares.The hard-label setting supplies the unit input-space normal, which is used to construct the system for the projected normal.Source: Projected Decision-Facet Normal in the… · pp. 17–18

4.2 Normal Lengths Comparison in Raw-Output Setting

  • Adjacent decision-facet normals differ by a component tied to the target neuron's weight, while deeper layers may expose only their control-space projections.If the compared directions form an angle above π/2, the length ordering depends on the relative magnitudes of positive and negative terms.Source: §4.2 · p. 18, Statistical Length Advantage · p. 19

Statistical Length Advantage.

  • Under the stated independent, zero-mean Gaussian-coordinate setup, the active-side projected normal has larger expected squared length and exceeds the comparison with probability strictly above 1/2; larger alignment generally reduces single-point success.Source: Statistical Length Advantage · pp. 19–22

4.3 Normal Alignment in Hard-Label Setting

  • At each dual point, Normal Alignment predicts the active side from which unit projected normal has the larger absolute alignment with the target weight, then aggregates confidence-thresholded votes.The alignment comparison has the same single-point success probability as the length comparison.Source: §4.3 · pp. 22–23

White-Box Validation of the Normal Alignment.

  • 1417 of 1440 neuron signs (98.40%) were recovered; all first-hidden-layer signs were correct, with 20 errors and 3 ties in the second and third layers.Across four CIFAR-10 models, the mean single-point success probabilities were 66.01% theoretically and 70.12% empirically; the active-side projected normal was longer in all twelve hidden layers.Source: White-Box Validation of the Normal… · pp. 23–24, Table 3 · p. 24

5 eSOE+Alignment: Combining Normal Alignment with Hard-Label SOE

eSOE+Alignment combines high-confidence Normal Alignment signs with an extended hard-label SOE system. In the evaluated settings, it recovered all signs without fallback exhaustive search.

5 eSOE+Alignment: Combining Normal Alignment with Hard-Label SOE

  • The method removes zero entries for neurons Normal Alignment identifies as inactive with high confidence, then extends the hard-label SOE system across compatible transition points.The points must share activation states in layer k and subsequent layers and remain on the same class-decision boundary.Source: §5 · pp. 24–25

Scale-Free Hard-label SOE Extension.

  • The scale-free extension combines equations from selected points after projecting out their differing normal-length factors, giving them a common unknown vector.It uses neurons not identified as inactive to form the restricted system.Source: Scale-Free Hard-label SOE Extension · pp. 25–26
  • If the stated inactivity and nonzero-entry assumptions hold and the coefficient matrix has rank |U| − 1, eSOE+Alignment recovers all neuron signs in layer k in polynomial time.If the resulting solution is unreliable, the procedure can instead use Normal Alignment signs and enumerate low-confidence assignments until next-layer signatures are recovered.Source: Scale-Free Hard-label SOE Extension · p. 26
  • eSOE+Alignment recovered all 832 signs in the CIFAR-10 3072-256×3-64-10 model and all 512 and 320 signs in two other evaluated settings, with no fallback exhaustive search.Complete recovery for the 3072-256×3-64-10 model took about 1h43m on an 8-core CPU without neuron-level parallelism; Future Toggle was reported at 8.5 hours on a 256-core server.Source: Scale-Free Hard-label SOE Extension · p. 27

6 Experiments

Experiments evaluate sign recovery on trained CIFAR-10 and MNIST ReLU networks under assumptions about previously recovered layers and known unsigned signatures. eSOE+Alignment recovered all reported signs in both models.

  • The evaluated trained networks were CIFAR-10 192-64×8-10 and MNIST 64-96×3-32-10, with 42,122 and 28,298 parameters, respectively.Both used ReLU activations and Kaiming normal initialization.Source: §6 · p. 27
  • eSOE+Alignment correctly recovered all 512 signs in the CIFAR-10 model and all 320 signs in the MNIST model.The evaluation used 200 attempted dual points per neuron for Normal Alignment and eSOE+Alignment.Source: §6 · p. 27
  • The evaluation assumed precomputed dual points; Future Toggle and eSOE+Toggle were tested with budgets of 200 and 1000, with dataset-specific normal recovery and boundary-walk procedures.For CIFAR-10, decision-facet normals came directly from model parameters; for MNIST, unit normals were recovered using the section 4.1 procedure.Source: §6 · p. 27

7 Conclusion

The paper proposes Normal Alignment as an improved statistical sign-recovery method for hard-label ReLU network extraction. It reports higher voting accuracy and exact polynomial-time full sign recovery when combined with extended hard-label SOE.

7 Conclusion

  • Normal Alignment is proposed as an improved statistical sign-recovery method for hard-label ReLU network extraction.The conclusion identifies CIFAR-10 and MNIST models as evaluation settings.Source: §7 · p. 27
  • The method achieves higher voting accuracy and pushes erroneous predictions to low-confidence ranks.Source: §7 · p. 28
  • Combined with extended hard-label SOE, eSOE+Alignment achieves exact polynomial-time full sign recovery without exponential enumeration.Source: §7 · p. 28

A Supporting Experimental Results

The supporting results describe Normal Alignment’s accuracy across hidden layers and compare recovery methods using layer-wise results, confidence, and error-rank measures.

A Supporting Experimental Results

  • Fig. 3 reports the percentage of correctly recovered signs across all three hidden layers after aggregating each neuron's nattempt votes.Source: Figure 3 · p. 31
  • Table 5 reports layer-wise confidence and ranks for the highest-confidence incorrect predictions from Normal Alignment and Future Toggle on CIFAR-10 and MNIST.Source: Table 5 · p. 32
  • I-Confidence is the highest confidence among incorrect sign predictions, and lower I-Confidence indicates a better method.Source: A Supporting Experimental Results · p. 32
  • I-Rank identifies the highest-confidence incorrect prediction's rank, with larger ranks placing that error lower in the confidence ordering.Confidence ranks are descending; a layer without incorrect predictions is marked ✓.Source: A Supporting Experimental Results · p. 32
  • Tables 6 and 7 provide layer-wise comparisons of Normal Alignment, eSOE+Alignment, Future Toggle, and eSOE+Toggle on CIFAR-10 and MNIST models.Source: Table 6 · p. 33, Table 7 · p. 34
Loading 2609.18751v1…