The use of S-boxes (substitution boxes) to provide nonlinear properties is known to be a common way to design a block cipher. These nonlinear properties are necessary to ensure the security of a block cipher. This manuscript proposes a design construction of a new S-box using affine transformation via cellular automata as a permutation matrix. We incorporate this cellular-automaton permutation matrix into the AES S box structure and test various irreducible polynomials. Nonlinearity, bijection, bit independence criterion, strict avalanche effect, linear approximation probability, and differential uniformity are the standard performance requirements used to evaluate the S-boxes that arise. Using this method, we are able to determine an irreducible polynomial that enables the construction of a new S-box design that can achieve an ideal strict avalanche criterion (SAC), which will subsequently provide efficiency in the design of block ciphers.