Construction of 8-Bit S-Boxes Based on Large Neighborhood Search

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.

Authors

Publication Details

Journal
Electronics
Published
2026-11-20
DOI
https://doi.org/10.3390/electronics15225425
Primary Topic
Cryptographic Implementations and Security
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Construction of 8-Bit S-Boxes Based on Large Neighborhood Search

Yingyin Pan, Fuzhong Zhang, Rong Cheng, Yu Han et al.
1 links
Electronics
Cryptographic Implementations and Security
article

Construction of 8-Bit S-Boxes Based on Large Neighborhood Search

Yingyin Pan, Fuzhong Zhang, Rong Cheng, Yu Han, Yu Zhou
article en

Abstract

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.

ElectronicsVol. 15(22)
Cryptographic Implementations and Security
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Construction of 8-Bit S-Boxes Based on Large Neighborhood Search — Yingyin Pan, Fuzhong Zhang, et al. · Electronics (2026) | TGRS Research Map | TGRS