Algebraic Cryptanalytic Extraction on Hard-Label Neural Networks

• URL: http://arxiv.org/abs/2608.05736v1
• Date: Thu, 06 Aug 2026 08:19:11 GMT
• Title: Algebraic Cryptanalytic Extraction on Hard-Label Neural Networks
• Abstract summary: This paper presents the first model extraction attack against hard-label max-pooling Convolutional Neural Networks (CNNs)<n> Experiments on a 64-64$times$4-10 FCNN and LeNet-5 (CNN) with max pooling demonstrate that our ASV method drastically cuts clustering time, and improves the overall efficiency in the model extraction.
• Score: 4.621555619872168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Although the state-of-the-art neural network model extraction attack in the hard-label setting by Carlini et al. at EUROCRYPT 2025 has polynomial-time complexity in theory, its dual-point clustering relies on singular value decomposition (SVD) with a time complexity of $\mathcal{O}(n^2 \cdot (d^{(k)})^3)$, resulting in huge runtime in practice. To address this computational bottleneck, this work transforms Carlini et al.'s geometric-view hard-label attack into an algebraic framework, and proposes a novel Approximate Signature Vector (ASV) method to achieve efficient parameter extraction on Fully Connected Neural Networks (FCNNs) by leveraging two key observations: high-dimensional random vectors are nearly orthogonal, and neurons in practical DNNs tend to learn disentangled features. The proposed ASV method replaces SVD-based rank checking with simple inner-product operations, reducing the clustering complexity to $\mathcal{O}(n \cdot (d^{(k)})^3)$ on average. Furthermore, this paper presents the first model extraction attack against hard-label max-pooling Convolutional Neural Networks (CNNs) by proposing an advanced ASV method with a kernel-centric clustering scheme instead of the neuron-centric clustering, which fully exploits the property of weight sharing in convolutions and fills the cryptanalysis gap. Experiments on a 64-64$\times$4-10 FCNN and LeNet-5 (CNN) with max pooling demonstrate that our ASV method drastically cuts clustering time, and improves the overall efficiency in the model extraction.

Related papers

• Efficient Encrypted Computation in Convolutional Spiking Neural Networks with TFHE [1.3047787405425166]
  Homomorphic Encryption (FHE) is a crucial technology for privacy-preserving computation.<n>FHE struggles with continuous non-polynomial functions, as it operates on discrete integers and supports only addition and multiplication.<n>We introduce FHE-DiCSNN, a framework built on the TFHE scheme, utilizing the discrete nature of SNNs for secure and efficient computations.
  arXiv  Detail & Related papers  (2026-03-25T03:15:59Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace.<n>We introduce the generative leap exponent $kstar$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting.
  arXiv  Detail & Related papers  (2025-06-05T18:34:56Z)
• Sliding down the stairs: how correlated latent variables accelerate learning with neural networks [8.107431208836426]
  We show that correlations between latent variables along directions encoded in different input cumulants speed up learning from higher-order correlations. Our results are confirmed in simulations of two-layer neural networks.
  arXiv  Detail & Related papers  (2024-04-12T17:01:25Z)
• The Convex Landscape of Neural Networks: Characterizing Global Optima and Stationary Points via Lasso Models [75.33431791218302]
  Deep Neural Network Network (DNN) models are used for programming purposes. In this paper we examine the use of convex neural recovery models. We show that all the stationary non-dimensional objective objective can be characterized as the standard a global subsampled convex solvers program. We also show that all the stationary non-dimensional objective objective can be characterized as the standard a global subsampled convex solvers program.
  arXiv  Detail & Related papers  (2023-12-19T23:04:56Z)
• Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification [22.361338848134025]
  We present a fully connected two-layer neural network for shifted ReLU activation to enable activated neuron identification in sublinear time via geometric search. We also prove that our algorithm can converge in $O(M2/epsilon2)$ time with network size quadratic in the coefficient norm upper bound $M$ and error term $epsilon$.
  arXiv  Detail & Related papers  (2023-07-13T05:33:44Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• On minimizers and convolutional filters: theoretical connections and applications to genome analysis [2.8282906214258805]
  CNNs start with a wide array of randomly convolutional filters, paired with a pooling operation, and then multiple additional neural layers to learn both the filters themselves and how they can be used to classify the sequence. In empirical experiments, we find that this property manifests as decreased density in repetitive regions, both in simulation and on real human telomeres. We train from scratch a CNN embedding of synthetic short-reads from the SARS-CoV-2 genome into 3D Euclidean space that locally recapitulates the linear sequence distance of the read origins.
  arXiv  Detail & Related papers  (2021-11-09T19:02:04Z)
• Partitioning sparse deep neural networks for scalable training and inference [8.282177703075453]
  State-of-the-art deep neural networks (DNNs) have significant computational and data management requirements. Sparsification and pruning methods are shown to be effective in removing a large fraction of connections in DNNs. The resulting sparse networks present unique challenges to further improve the computational efficiency of training and inference in deep learning.
  arXiv  Detail & Related papers  (2021-04-23T20:05:52Z)
• Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning [58.14930566993063]
  We present connections between three models used in different research fields: weighted finite automata(WFA) from formal languages and linguistics, recurrent neural networks used in machine learning, and tensor networks. We introduce the first provable learning algorithm for linear 2-RNN defined over sequences of continuous vectors input.
  arXiv  Detail & Related papers  (2020-10-19T15:28:00Z)
• Generalized Leverage Score Sampling for Neural Networks [82.95180314408205]
  Leverage score sampling is a powerful technique that originates from theoretical computer science. In this work, we generalize the results in [Avron, Kapralov, Musco, Musco, Velingker and Zandieh 17] to a broader class of kernels.
  arXiv  Detail & Related papers  (2020-09-21T14:46:01Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  We propose the linear approximation neural network (LANN) to approximate a given deep model with curve activation function. We experimentally explore the training process of neural networks and detect overfitting. We find that the $L1$ and $L2$ regularizations suppress the increase of model complexity.
  arXiv  Detail & Related papers  (2020-06-16T07:38:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.