Algebraic Cryptanalytic Extraction on Hard-Label Neural Networks

Computer Science > Cryptography and Security [Submitted on 6 Aug 2026] Algebraic Cryptanalytic Extraction on Hard-Label Neural Networks Zirui Chen, Shi Tang, Zhengchao Gao, Yongjia Su, Lingyue Qin, Xiaoyang Dong 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 O( n 2 ⋅( 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 O(n⋅( 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 × 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. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2608.05736 [cs.CR]   (or arXiv:2608.05736v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2608.05736 Focus to learn more Submission history From: Zirui Chen [view email] [v1] Thu, 6 Aug 2026 08:19:11 UTC (871 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-08 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)