From Boolean Functions to Secure S-Boxes: Construction, Challenges, and a Chaos-Based Dynamic Solution

Abstract

Substitution boxes, commonly called S-boxes, are the primary source of nonlinearity in modern symmetric block ciphers, and their strength rests almost entirely on the cryptographic quality of the Boolean functions from which they are built. This paper traces that dependency from first principles. It reviews the algebraic foundations of cryptographic Boolean functions, including nonlinearity, algebraic degree, balancedness, bentness, and the avalanche and correlation immunity criteria that a coordinate function of a strong S-box must satisfy. It then surveys the main families of S-box construction, algebraic, heuristic, chaos-based, and hybrid, drawing on a paper bank of 43 verified sources retrieved through the Semantic Scholar API, and explains why static, fixed S-boxes remain structurally exposed to differential, linear, and algebraic cryptanalysis. Building on this review, the paper implements and evaluates a dynamic, key-dependent S-box generation framework that couples a compound tent-logistic chaotic map with an algebraic base layer, and reports the framework's actual measured performance, nonlinearity, strict avalanche criterion, bit independence criterion, differential uniformity, and linear probability, against the AES S-box baseline over twelve independently generated instances. The results are reported honestly, including a gap between the proposed construction's nonlinearity and the AES baseline that mirrors a limitation already documented in the literature, and the paper closes with a discussion of what a genuinely competitive dynamic S-box design would need to add to close that gap.