(2026-08) AFS; A Family of ARX-Based Large-State S-boxes with Exceptional Properties
2026-08-13
Large-state ARX-based S-boxes have become a key component of modern lightweight cryptographic designs, yet deriving tight security bounds for their differential and linear properties remains challenging. In this paper, we study the security of Alzette, the 64-bit ARX-based S-box used in the SPARKLE permutation, and present a general framework for the analysis and design of large-state ARX S-boxes. We introduce SMCS, a hybrid search strategy that combines MILP-based optimization with SMT-based model checking, enabling the computation of tight bounds on maximum expected differential probabilities and linear correlations. Using SMCS, we refine existing bounds for Alzette and, for the first time, establish tight linear bounds (resp. differential bounds) for up to 15 rounds (resp. 14 rounds). Building on these results, we propose S-box configurational encoding, an automated design method for ARX-based S-boxes, and introduce a new family of S-boxes called AFS (ARX-Feistel Structure) with 32-bit and 64-bit instances. We show that selected AFS instances achieve strictly better resistance to single-trail differential and linear cryptanalysis than SPECKEY and Alzette, respectively, while preserving comparable hardware and software costs. Finally, we present the first bit-based SMT model for optimal long-trail decomposition and apply it to derive more accurate bounds for SPARX-128 and SPARKLE. Our results show that replacing the S-boxes with AFS instances yields substantial improvements in cryptanalytic security margins.