Nonlinear mapping of random graph properties for cryptographic S-boxes

Abstract

Secure communication in the digital era depends on cryptographic primitives whose nonlinearity withstands side-channel, algebraic, and emerging quantum cryptanalytic threats. Among these primitives, the substitution box (S-box) is the principal source of confusion in modern block ciphers, and constructing S-boxes that combine high nonlinearity with strong avalanche and diffusion behaviour remains an open design problem. The objective of the present study is to develop a reproducible framework for generating 8-bit S-boxes whose cryptographic profile is competitive with state-of-the-art algebraic, chaos-based, and metaheuristic constructions. The framework formalises the link between random-graph topology and S-box confusion by deriving substitution values from vertex-level graph parameters and subsequently refining them through metaheuristic optimisation. The methodology consists of two phases. In the first phase, the vertex degree, eccentricity, and clustering coefficient of a 16-vertex Erdős–Rényi random graph are combined through a nonlinear modular mapping to produce an initial bijective candidate; non-injective outputs are repaired through a deterministic greedy fill-in. In the second phase, a temperature-controlled simulated-annealing routine with an average-coordinate-nonlinearity-based acceptance criterion and a swap-based neighbourhood operator refines the candidate, preserving bijectivity while SAC, LAP, DAP, and BIC are evaluated after optimization. The evaluation is conducted by numerical simulation in MATLAB R2023a on a standard workstation, using edge probabilities \(p = 0.7\) and \(p = 0.4\) to represent dense and sparse graph regimes. The two representative S-boxes reported in detail attain average coordinate nonlinearities of 111.25 and 111.50 for \(p=0.7\) and \(p=0.4\) , both with minimum coordinate nonlinearity 110, SAC of 0.5056 and 0.5054, BIC-nonlinearity of 103.86 and 103.64, LAP of 0.1328 and 0.1406, DAP of 0.0391 and 0.0469, and maximum algebraic degree 7. To establish that these figures are typical rather than exceptional, the complete pipeline is replicated on 100 independent random graphs for each edge probability: the target \(\textrm{AvNL}\ge 110\) is reached in 100% of the runs, with final average coordinate nonlinearity \(111.13\pm 0.28\) ( \(p=0.7\) ) and \(111.14\pm 0.23\) ( \(p=0.4\) ) and a mean of about \(1.7\times 10^{4}\) annealing iterations within a budget of \(5\times 10^{4}\) . An edge-probability sweep over \(p\in [0.15,0.95]\) , a seven-way ablation of the mapping terms, and a matched-budget comparison against uniformly random permutation initialisation quantify the individual contribution of every component of the construction. These figures indicate that the proposed S-boxes are competitive with recent graph-based, chaos-based, and optimisation-based S-box designs under the reported evaluation metrics. In particular, the proposed designs show favourable average coordinate nonlinearity and SAC values, while some comparison methods remain stronger in specific criteria such as LAP, DAP, or BIC-NL.