💻 computer science

Algebraic Cryptanalytic Extraction on Hard-Label Neural Networks

This paper proposes an algebraic framework using an Approximate Signature Vector (ASV) method to overcome the computational bottlenecks of existing hard-label model extraction attacks, achieving efficient parameter recovery for both Fully Connected and max-pooling Convolutional Neural Networks by replacing complex SVD-based clustering with simple inner-product operations.

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

Published 2026-08-07

📖 7 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to steal the secret recipe for a world-famous cake, but the baker refuses to let you taste the batter or see the ingredients list. All you can do is hand the baker a random ingredient, ask "Is this a cake?", and get a simple "Yes" or "No" back. This is the challenge of "hard-label" attacks in the world of Artificial Intelligence. In this corner of computer science, researchers try to reverse-engineer the hidden math (the weights and biases) inside a "black box" neural network just by watching its final yes-or-no decisions. For years, this was like trying to solve a giant jigsaw puzzle in the dark; while some clever tricks existed to find the pieces, sorting them into the right picture was so slow and computationally heavy that it felt impossible to do in real life. The problem wasn't that the math was wrong, but that the method to organize the clues was stuck in a traffic jam of calculations.

This paper introduces a clever new way to cut through that traffic jam. The authors, Zirui Chen and their team, realized that the old method was like trying to compare every single puzzle piece to every other piece one by one using a super-complex calculator. Instead, they proposed a shortcut called the "Approximate Signature Vector" (ASV). Think of it as realizing that if two puzzle pieces belong to the same section of the sky, they will both be blue. You don't need a super-computer to check; you just need a quick glance to see if they are the same shade. By using this "glance" (a simple math operation called an inner product) instead of the heavy calculator, they turned a task that took thousands of hours into one that takes minutes. They also figured out how to apply this trick to a specific type of AI architecture called a Convolutional Neural Network (CNN) that uses "max pooling," a feature that had previously been a dead end for these kinds of attacks.

The Big Idea: From Heavy Lifting to a Quick Glance

The story starts with a famous attack developed by Carlini and colleagues in 2025. They showed that even if you only get "Yes/No" answers from a neural network, you can still figure out its secret weights. They did this by finding special points in the data called "dual points." Imagine these dual points as the exact spots where the AI's decision flips from "Cat" to "Dog." By collecting thousands of these flip-points, the attackers could mathematically reconstruct the AI's brain.

However, there was a massive bottleneck. Once you have a pile of thousands of these flip-points, you have to sort them. You need to figure out which points belong to the same "neuron" (the same tiny decision-maker inside the AI) and which belong to different ones. The old method, used by Carlini's team, was like trying to sort a million socks by comparing every single sock to every other sock using a high-tech scanner. It worked in theory, but in practice, it was agonizingly slow. If you had 2,000 points, the computer had to do billions of heavy calculations, taking weeks or even months to finish the job. The authors of this paper noted that while the theory was sound, the practical implementation was stuck in a "computational bottleneck" that made it useless for real-world attacks.

The Magic Shortcut: The Approximate Signature Vector

The authors' breakthrough was to change the perspective from a geometric puzzle to an algebraic one. They noticed two cool things about how these AI brains are built:

High-dimensional randomness: In the vast, multi-dimensional space where these AIs live, random directions tend to be almost perfectly perpendicular to each other (like the x, y, and z axes).
Disentangled features: Real-world AIs are trained to learn different things with different neurons. One neuron might learn to spot ears, another tails. Because they learn different things, their internal "weights" (the math that defines them) are naturally uncorrelated, almost like they are pointing in different, unique directions.

Using these observations, the team invented the Approximate Signature Vector (ASV). Instead of doing the heavy, slow comparison for every pair of points, they calculate a quick "signature" for each point. If two points have signatures that point in nearly the same direction (or exactly opposite), they almost certainly belong to the same neuron.

It's like having a bag of marbles where you need to sort them by color. The old way was to weigh every marble against every other marble to see if they were the same density. The new way is to just look at the color. If two marbles are both bright red, you put them in the same pile. You don't need a scale; you just need your eyes. In math terms, this "look" is a simple multiplication of vectors (an inner product), which is lightning fast compared to the old "scale" (Singular Value Decomposition).

The Results: Speeding Up the Heist

The difference in speed is staggering. The authors tested their method on a standard AI model with 2,000 dual points.

The Old Way: Using the heavy SVD method, the sorting process would take about 4,348 hours (nearly half a year of non-stop computing).
The New Way: Using their ASV method, the same job took only 211.9 seconds (about 3.5 minutes).

That is a speedup of roughly 212 times. In a real experiment extracting the first layer of a model, the old method took 5.03 hours, while their method did it in just 0.04 hours (about 2.4 minutes). For the second layer, the old method couldn't even finish in a week, while the new method finished in 0.74 hours.

Cracking the CNN Code

The paper didn't just speed up the old trick; it also solved a new problem. The researchers applied their method to Convolutional Neural Networks (CNNs) that use "max pooling." Max pooling is a technique where the AI looks at a small group of numbers and only keeps the biggest one, discarding the rest. This creates a unique challenge because many different neurons in the network actually share the same "kernel" (the same set of weights).

Previous attempts to attack these networks were "neuron-centric," meaning they tried to sort points by which specific neuron they belonged to. But because of the way max pooling works, you'd need to find two points that hit the exact same neuron to make progress, which is incredibly hard to do by chance.

The authors introduced an "Advanced ASV" method that is "kernel-centric." Instead of asking, "Do these two points belong to the same neuron?" they asked, "Do these two points belong to the same kernel?" Since all neurons in a specific layer share the same kernel, they can mix and match points from different neurons as long as they are working on the same underlying pattern. This allowed them to successfully extract the weights of a LeNet-5 model (a classic image-recognition AI) using only hard-label inputs, a feat that had been an "open problem" until now.

What This Means

The paper demonstrates that by changing the mathematical lens through which we view these attacks, we can turn a task that was practically impossible into a routine calculation. The authors show that the "clustering" step, which was the main bottleneck, can be solved efficiently without sacrificing accuracy. They verified their results through simulations and experiments on standard models, showing that the "Approximate Signature Vector" is a reliable proxy for the true weights.

While the paper doesn't claim to have broken all AI security, it proves that the "hard-label" setting is far more vulnerable than previously thought, provided you have the right algebraic tools. The authors suggest that their method could be used by third parties to optimize these attacks, effectively closing the gap between theoretical possibility and practical reality. In the world of AI security, knowing that a "Yes/No" interface can be reverse-engineered in minutes rather than weeks is a significant warning that the defenses of black-box models need to be much stronger.

Technical Summary: Algebraic Cryptanalytic Extraction on Hard-Label Neural Networks

Problem Statement
The paper addresses the challenge of extracting model parameters (weights and biases) from Deep Neural Networks (DNNs) operating in a "hard-label" setting. In this scenario, an attacker has access only to the final classification labels (e.g., "cat" or "dog") rather than the raw logit outputs. While Carlini et al. (EUROCRYPT 2025) demonstrated a polynomial-time attack for hard-label Fully Connected Neural Networks (FCNNs) by analyzing decision boundary geometries, their approach suffers from a severe computational bottleneck. Specifically, the "signature recovery" phase requires clustering dual points to identify consistent groups corresponding to the same neuron. Carlini et al.'s method relies on Singular Value Decomposition (SVD) to check the rank consistency of point pairs, resulting in a time complexity of $O(n^2 \cdot (d(k))^3)$ , where $n$ is the number of dual points and $d(k)$ is the layer width. This complexity renders the attack impractical for deep networks or large datasets, as noted by the authors of the original work as a barrier to a fully optimized black-box implementation. Furthermore, prior to this work, no polynomial-time hard-label extraction method existed for Convolutional Neural Networks (CNNs) utilizing max-pooling, as existing attacks required raw output queries or were limited to average-pooling architectures.

Methodology
The authors propose transforming the geometric view of Carlini et al.'s attack into an algebraic framework, introducing a novel Approximate Signature Vector (ASV) method. The core of their approach relies on two key observations:

High-Dimensional Orthogonality: In high-dimensional spaces, independent random vectors tend to be nearly orthogonal.
Feature Disentanglement: In practical DNNs, distinct neurons learn to extract divergent features, making their weight vectors effectively uncorrelated or independent.

Based on these observations, the authors define the ASV ( $\vec{v}$ ) for a dual point. The ASV is constructed from the unit normal vectors of the adjacent decision boundary patches ( $\vec{n}_l$ and $\vec{n}_r$ ) surrounding a critical hyperplane. Theoretically, the ASV aligns closely with the true weight vector ( $\vec{w}$ ) of the target neuron (or the difference between weights for pooling switching points), with a cosine distance approaching zero.

The methodology proceeds in three main stages:

ASV Extraction: For each collected dual point, the attacker computes the ASV using simple inner-product operations rather than SVD.
Clustering: Instead of performing rank checks via SVD, the algorithm clusters dual points by comparing the cosine similarity (or directional distance) of their ASVs. If two points belong to the same neuron, their ASVs will be nearly collinear (identical or opposite directions). This reduces the pairwise comparison complexity from $O((d(k))^3)$ to $O(d(k))$ .
Kernel-Centric Recovery for CNNs: For max-pooling CNNs, the authors introduce an "Advanced ASV" method. Unlike previous "neuron-centric" approaches that require multiple dual points for the exact same neuron to solve linear systems, this method exploits the weight sharing property of convolutions. It clusters dual points based on the convolutional kernel they correspond to (kernel-centric), allowing the recovery of the unique kernel weight from a diverse set of dual points (including different neurons within the same layer) that share the same kernel.

Key Contributions

Algebraic Reformulation of Hard-Label Attacks: The paper converts the geometric decision boundary analysis into an algebraic framework, replacing computationally expensive SVD-based rank checking with efficient inner-product operations.
Approximate Signature Vector (ASV) Method: A new clustering technique that leverages the near-orthonality of high-dimensional weight vectors. This reduces the average-case time complexity of clustering from $O(n^2 \cdot (d(k))^3)$ to $O(n \cdot (d(k))^2)$ , with the dominant cost shifting to the initial ASV extraction rather than the pairwise comparisons.
First Hard-Label Attack on Max-Pooling CNNs: The paper presents the first model extraction attack against hard-label CNNs with max-pooling. It introduces a "kernel-centric" clustering scheme that overcomes the inefficiency of neuron-centric methods in CNNs, significantly reducing the number of required dual points to recover convolutional kernels.
Practical Efficiency: The proposed methods drastically reduce runtime. In experiments, the ASV method reduced clustering time by a factor of approximately $2^{12}$ compared to the SVD-based approach.

Experimental Results
The authors evaluated their method on two architectures:

FCNN (64-64×4-10):
- Layer 1: Extraction time reduced from 5.03 hours (Carlini et al.'s SVD method) to 0.04 hours (ASV method), a 99.2% reduction.
- Layer 2: The ASV method completed extraction in 0.74 hours, whereas the SVD method failed to produce a result within one week (estimated to require ~4,375 hours).
- Accuracy: The extracted models achieved $(\epsilon, 0)$ -functional equivalence with errors comparable to or better than the baseline.
CNN (LeNet-5 with Max Pooling):
- The Advanced ASV method successfully recovered the convolutional blocks of a LeNet-5 model in the hard-label setting.
- Compared to the "Simple ASV" (neuron-centric) method, the Advanced ASV (kernel-centric) method significantly improved the utilization of collected dual points. For the second layer, the Simple ASV required 6,000 dual points to find valid pairs, while the Advanced ASV achieved the same with only 1,000 points.
- The attack outperformed previous works that required raw output queries (Chen et al.) or were limited to average pooling (Sun et al.).

Significance and Claims
The paper claims to solve a critical computational bottleneck in algebraic cryptanalysis of neural networks, making hard-label model extraction feasible for deeper and more complex architectures. By transforming the problem into an algebraic framework and leveraging the statistical properties of high-dimensional vectors, the authors provide a scalable solution that was previously considered impractical due to runtime constraints. Crucially, the attack operates entirely within a black-box setting: the attacker possesses full knowledge of the network architecture but has no access to internal weights, biases, or gradients. To improve efficiency during the dual point discovery and weight recovery phases, the authors employ symbolic computation to derive gradients at decision boundaries based on the known architecture, rather than querying the model for internal gradient values or accessing its parameters. This approach adheres strictly to the hard-label adversarial model, where only classification labels are observable. The work fills a specific gap in the literature by enabling the first hard-label extraction of max-pooling CNNs, extending the scope of algebraic attacks beyond FCNNs and average-pooling CNNs. The authors emphasize that while their method is highly efficient, it relies on the assumption that neurons in practical DNNs learn disentangled features, a property they verify empirically.

The Big Idea: From Heavy Lifting to a Quick Glance

The Magic Shortcut: The Approximate Signature Vector

The Results: Speeding Up the Heist

Cracking the CNN Code

What This Means

More like this