Paper 2025/1306
Rethinking Learning-based Symmetric Cryptanalysis: a Theoretical Perspective
, Institute of Software Chinese Academy of Sciences, University of Chinese Academy of SciencesAbstract
The success of deep learning in cryptanalysis has been largely demonstrated empirically, yet it lacks a foundational theoretical framework to explain its performance. We bridge this gap by establishing a formal learning-theoretic framework for symmetric cryptanalysis. Specifically, we introduce the Coin-Tossing (CoTo) model to abstract the process of constructing distinguishers and propose a unified algebraic representation, the Conjunctive Parity Form (CPF), to capture a broad class of traditional distinguishers without needing domain-specific details. Within this framework, we prove that any concept in the CPF class is learnable in sub-exponential time in the setting of symmetric cryptanalysis. Guided by insights from our complexity analysis, we demonstrate preprocessing the data with a flexible output generating function can simplify the learning task for neural networks. This approach leads to a state-of-the-art practical result: the first improvement on the deep learning-based distinguisher for $S{\scriptsize PECK}32/64$ since 2019, where we enhance accuracy and extend the attack from 8 to a record 9 rounds.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Contact author(s)
-
yufei2021 @ iscas ac cn
wenling @ iscas ac cn - History
- 2026-02-05: last of 2 revisions
- 2025-07-17: received
- See all versions
- Short URL
- https://ia.cr/2025/1306
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1306,
author = {Yufei Yuan and Haiyi Xu and Jiaye Teng and Lei Zhang and Wenling Wu},
title = {Rethinking Learning-based Symmetric Cryptanalysis: a Theoretical Perspective},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1306},
year = {2025},
url = {https://eprint.iacr.org/2025/1306}
}
