Construction of 8-Bit S-Boxes Based on Large Neighborhood Search
Electronics · 2026-11-20 · 15 (22) · 5425
DOI: 10.3390/electronics15225425 ↗At a glance
Journal article in Electronics, published online on 2026-11-20. Written by Rong Cheng and 4 co-authors. The full text is freely available (open access, CC BY 4.0). Funded by: National Key Laboratory of Security Communication.
Abstract (original language)
S-boxes are the nonlinear components of symmetric cryptographic algorithms, and their differential uniformity and nonlinearity characterize their resistance against differential cryptanalysis and linear cryptanalysis, respectively. To preserve the randomness of S-boxes, heuristic searches for S-boxes with strong cryptographic properties usually start from random permutations. This paper proposes an S-box construction method based on large neighborhood search. The method iteratively optimizes S-boxes with large neighborhood search: in each round, a destroy operator first removes the values at several positions, and a repair operator then re-determines the values of these positions. While assigning values step by step, the repair operator maintains the difference distribution table and the Walsh spectrum, giving priority at each step to values that do not cause the differential uniformity or Walsh spectrum amplitudes to exceed their bounds and selecting the value with the smallest violation only when every candidate value would exceed a bound, and its output is always a permutation. The complete procedure consists of three stages. The first stage performs large neighborhood search from random permutations; the second stage expands the set of near-optimal candidate S-boxes by a local search over the exchange neighborhood; the third stage performs large neighborhood search again to find a target S-box. Experimental results show that the method relies neither on cryptographic structures nor on prior data, and all S-boxes obtained from successful searches are bijective S-boxes with a differential uniformity of 6 and a nonlinearity of 104.
Funding
- National Key Laboratory of Security Communication
Cite
APA
Cheng, R., Zhou, Y., Pan, Y., Zhang, F., & Han, Y. (2026). Construction of 8-Bit S-Boxes Based on Large Neighborhood Search. Electronics, 15(22), 5425. https://doi.org/10.3390/electronics15225425
Vancouver
Cheng R, Zhou Y, Pan Y, Zhang F, Han Y. Construction of 8-Bit S-Boxes Based on Large Neighborhood Search. Electronics. 2026;15(22):5425. doi:10.3390/electronics15225425
BibTeX
@article{Cheng2026,
author = {Cheng, Rong and Zhou, Yu and Pan, Yingyin and Zhang, Fuzhong and Han, Yu},
title = {Construction of 8-Bit S-Boxes Based on Large Neighborhood Search},
journal = {Electronics},
year = {2026},
volume = {15},
number = {22},
pages = {5425},
doi = {10.3390/electronics15225425}
}
EUVIMED