Introducing the SEA S-Box: A High-Quality Substitution Box via Fractional Linear and Affine Transformations

Introducing the SEA S-Box: A High-Quality Substitution Box via Fractional Linear and Affine Transformations

In symmetric cryptography, the substitution box (S-box) is the primary source of nonlinear confusion in block ciphers. The security of ciphers like AES depends critically on the cryptographic quality of their S-box. After an extensive automated search evaluating many candidates across 24 cryptographic quality metrics, I’m presenting the SEA S-Box — the Seasoned Encryption Algorithm substitution box — a candidate 8×8 S-box that meets or exceeds AES-class performance on nearly every major metric.

Construction: Fractional Linear + Affine Transformation (FLAT)

The SEA S-Box is constructed in two stages:

Stage 1 — Fractional Linear Transformation over GF(2⁸):

The base permutation is generated using the fractional linear (Möbius) transformation:

S(x) = (ax + b) / (cx + d)

where a, b, c, d are elements of GF(2⁸) and all arithmetic is performed in the finite field defined by an irreducible polynomial. The transformation is bijective when the determinant ad − bc ≠ 0 (where subtraction is XOR in GF(2)). At the single pole point where cx + d = 0, the output is assigned the unique missing value to complete the permutation.

Fractional linear transformations over finite fields are an established approach to S-box construction. Farwa, Shah, and Idrees (2016) demonstrated that S-boxes constructed via fractional linear transformations over GF(2⁸) exhibit high nonlinearity, strong strict avalanche properties, and low differential approximation probability — confirming these mappings as a sound algebraic foundation for cryptographic permutations [Farwa et al., 2016].

Stage 2 — Affine Transformation over GF(2):

A raw fractional linear S-box has inherently low algebraic complexity (only 128 terms in its polynomial representation over GF(2⁸)) due to its simple rational structure. To break this algebraic regularity, an invertible affine transformation is applied to every output byte:

y = M · S(x)  ⊕  k

where M is an invertible 8×8 binary matrix over GF(2) and k is a constant XOR byte. Each output bit i is computed as:

bit_i = popcount(row_i AND input_byte) mod 2

This is the same class of affine transformation used in the AES S-box itself — the AES specification applies a fixed affine map over GF(2) after the multiplicative inverse in GF(2⁸) [FIPS 197, 2001]. The effectiveness of affine transformations for increasing algebraic complexity of S-boxes was demonstrated by Cui and Cao (2007), who introduced the Affine-Power-Affine (APA) structure. Their work showed that composing affine maps on both sides of the multiplicative inverse increases the forward algebraic complexity from 9 to 253 terms while preserving other cryptographic properties [Cui & Cao, 2007].

The SEA S-Box: Complete Specification

Irreducible Polynomial:

p(x) = x8 + x6 + x5 + x4 + x3 + x + 1    (0x17B)

Fractional Linear Parameters:

a = 4,  b = 151,  c = 230,  d = 19

Affine Transformation:

• Matrix M — 8×8 circulant binary matrix, first row = 0x58 (01011000). Each subsequent row is a 1-bit right rotation of the previous:

        Col:  7 6 5 4 3 2 1 0
Row 0:        0 1 0 1 1 0 0 0   (0x58)
Row 1:        0 0 1 0 1 1 0 0   (0x2C)
Row 2:        0 0 0 1 0 1 1 0   (0x16)
Row 3:        0 0 0 0 1 0 1 1   (0x0B)
Row 4:        1 0 0 0 0 1 0 1   (0x85)
Row 5:        1 1 0 0 0 0 1 0   (0xC2)
Row 6:        0 1 1 0 0 0 0 1   (0x61)
Row 7:        1 0 1 1 0 0 0 0   (0xB0)

• XOR constant k = 100 (0x64)

Resulting S-Box (256-byte lookup table):

0xD3, 0x28, 0xBC, 0x94, 0xA0, 0x2F, 0xAD, 0xCC, 0x54, 0x3E, 0x60, 0xFD, 0x16, 0xDA, 0x39, 0x2C,
0x31, 0x2A, 0x9D, 0x0A, 0x5F, 0xE9, 0xD6, 0x51, 0x1A, 0x0D, 0x34, 0x67, 0xCE, 0x99, 0x6A, 0xAF,
0x5E, 0x77, 0x41, 0x8F, 0x9B, 0xD8, 0x59, 0x06, 0x52, 0xF8, 0xA7, 0x10, 0x29, 0xB9, 0x79, 0xEF,
0xB7, 0x1B, 0x2E, 0xB5, 0x5A, 0xA5, 0x72, 0x3D, 0x7E, 0x24, 0xAA, 0xE0, 0xF9, 0x71, 0xC2, 0x3B,
0x4B, 0x0B, 0xB6, 0x8E, 0x7A, 0x8B, 0xE6, 0x42, 0x36, 0x5D, 0x6F, 0xBF, 0x69, 0xC7, 0x5C, 0x89,
0xE2, 0x43, 0xF1, 0x57, 0x74, 0xD1, 0x87, 0x56, 0x48, 0x5B, 0xFC, 0x81, 0xC3, 0x1C, 0x55, 0x0E,
0xB1, 0x6B, 0x37, 0x11, 0x0C, 0x27, 0xB2, 0x23, 0xEC, 0x00, 0xBE, 0x93, 0x1D, 0xF7, 0x82, 0xB0,
0x73, 0x76, 0x50, 0x35, 0xDD, 0x09, 0xF0, 0xCF, 0xF3, 0x3C, 0xA4, 0x64, 0x20, 0x53, 0x4D, 0xF5,
0xA1, 0xAB, 0xE8, 0x2B, 0xAC, 0xC0, 0x0F, 0x07, 0x84, 0x46, 0xC5, 0x21, 0xAE, 0xDE, 0xE3, 0xC4,
0x3A, 0x9A, 0x85, 0xE7, 0x1E, 0x32, 0xA8, 0xFA, 0xB4, 0x88, 0x92, 0x91, 0x01, 0xC8, 0xFB, 0x58,
0x15, 0x04, 0xF4, 0xA9, 0x86, 0xB3, 0xCD, 0xD7, 0x14, 0x4A, 0x96, 0x66, 0x1F, 0xFE, 0x6D, 0x17,
0x8D, 0xDB, 0xD2, 0x9E, 0x13, 0x70, 0xB8, 0x9C, 0xBA, 0xC6, 0x6C, 0x03, 0x7D, 0x08, 0xDC, 0xF6,
0x12, 0xDF, 0xBB, 0xA3, 0x9F, 0xCB, 0xE1, 0x19, 0xEE, 0xD0, 0xE4, 0x8C, 0x68, 0x47, 0xA2, 0xFF,
0xA6, 0x26, 0x40, 0xBD, 0xEB, 0x75, 0x98, 0x45, 0x78, 0x3F, 0xE5, 0x97, 0xCA, 0xC1, 0x49, 0x30,
0x4C, 0xF2, 0x18, 0x7C, 0x44, 0xC9, 0x65, 0x2D, 0xD4, 0x95, 0x61, 0x83, 0x22, 0x90, 0x6E, 0x62,
0xED, 0x4F, 0x38, 0x4E, 0x63, 0x80, 0x05, 0x7B, 0x02, 0xD5, 0xD9, 0xEA, 0x25, 0x33, 0x7F, 0x8A,

Metric-by-Metric Comparison with AES

The following table compares the SEA S-Box against the AES (Rijndael) S-Box on all evaluated metrics. For each metric, the theoretical optimal value is listed alongside its importance. Green indicates the better value between the two; red indicates the worse.

Key Advantages Over AES

The SEA S-Box matches AES on every differential, linear, and boomerang metric — these are the properties that most directly govern resistance to the dominant families of block cipher cryptanalysis. Where it surpasses AES is in four areas:

1. Algebraic Complexity: This is the most dramatic improvement. AES has a total algebraic complexity of just 260 (9 forward + 251 inverse), because the AES S-box is a pure multiplicative inverse — an elegant algebraic object with a minimal polynomial representation. The SEA S-Box achieves 505 (253 + 252), nearly doubling AES. This directly increases resistance to interpolation attacks [Jakobsen & Knudsen, 1997] and algebraic attacks using Gröbner bases [Courtois & Pieprzyk, 2002].
2. Permutation Structure: The SEA S-Box forms a single cycle of length 256 (iterative period = 256, number of cycles = 1), while AES decomposes into 5 cycles with a period of only 2 (the underlying multiplicative inverse is an involution). A single maximal-length cycle eliminates the potential for slide attacks or other techniques that exploit short permutation cycles.
3. Diffusion Quality (DSAC): The SEA S-Box achieves a DSAC of 232 — to my knowledge, the lowest reported for any published 8×8 S-box. For comparison, the AES S-box has a DSAC of 432, the COBLAH S-box (2024) achieved 332 [Jawed & Sajid, 2024], and the Mishra-Singh-Delhibabu genetic algorithm search (2023) reported a best of 352 [Mishra et al., 2023]. DSAC directly quantifies how closely an S-box satisfies the Strict Avalanche Criterion across all input-output bit pairs. A lower value means better diffusion: small changes in the plaintext propagate more uniformly through the cipher, making the S-box more resistant to known-plaintext and differential attacks.
4. Side-Channel Properties: The SEA S-Box has tighter SAC conformance (RMSE 0.0201 vs 0.0317), better BIC-SAC (RMSE 0.0284 vs 0.0312), and lower reVisited Transparency Order (7.25 vs 7.46), suggesting marginally better resistance to DPA side-channel attacks.

Comparison with Other Known S-Boxes

The following table compares the SEA S-Box against 57 published S-Boxes from the cryptographic literature across all evaluated metrics. S-Boxes are ranked by composite score across all metrics (lower is better). Green shading marks the best value in each column; red marks the worst.

Column key: NL = Nonlinearity, Vec. NL = Vectorial Nonlinearity, BIC-NL = Bit Independence Criterion Nonlinearity, DU = Differential Uniformity, BU = Boomerang Uniformity, FBU = Feistel Boomerang Uniformity, DBN = Differential Branch Number, LBN = Linear Branch Number, Deg = Algebraic Degree, AC = Algebraic Complexity, Inv AC = Inverse Algebraic Complexity, Total AC = Total Algebraic Complexity, AI = Algebraic Immunity, Auto = Autocorrelation, SAC RMSE = Strict Avalanche Criterion Root Mean Square Error, SAC Mean = Strict Avalanche Criterion Mean, SAC SD = Strict Avalanche Criterion Standard Deviation, DSAC = Distance to Strict Avalanche Criterion, BIC-SAC RMSE = Bit Independence Criterion for Strict Avalanche Criterion Root Mean Square Error, BIC-SAC Mean = Bit Independence Criterion for Strict Avalanche Criterion Mean, BIC-SAC SD = Bit Independence Criterion for Strict Avalanche Criterion Standard Deviation, VTO = reVisited Transparency Order, Period = Iterative Period.

The SEA S-Box achieves the best overall composite score of any S-Box in this comparison set. It is worth noting that the Duong-Pham S-Boxes achieve a higher nonlinearity of 116, but at the cost of weaker differential uniformity (6 vs 4), higher boomerang uniformity (14 vs 6), and much shorter iterative periods — illustrating the inherent trade-offs in S-Box design. The Picek Evolved S-Box stands out for having the best VTO (4.676), meaning the highest resistance to DPA side-channel attacks, but it pays heavily in nonlinearity (98), differential uniformity (12), and autocorrelation (96).

SKINNY-128 is intentionally designed for low-latency hardware implementation rather than maximal cryptographic strength per S-box, and so its inclusion here is for reference rather than direct comparison.

Conclusion

The SEA S-Box demonstrates that fractional linear transformations over GF(2⁸), when composed with a carefully chosen affine transformation, can produce S-Boxes that are competitive with — and in several important metrics superior to — the AES S-Box. The construction is fully specified by just 7 parameters (4 field elements, a polynomial, a matrix seed, and a XOR constant), making it compact, reproducible, and amenable to formal analysis.

The complete S-Box specification is public domain.

References

1. NIST, “Advanced Encryption Standard (AES),” FIPS 197, 2001. doi:10.6028/NIST.FIPS.197-upd1
2. S. Farwa, T. Shah, and L. Idrees, “A highly nonlinear S-box based on a fractional linear transformation,” SpringerPlus 5, 1658, 2016. doi:10.1186/s40064-016-3298-7
3. L. Cui and Y. Cao, “A new S-box structure named Affine-Power-Affine,” Int. J. Innov. Comput. Inf. Control, 3(3), 751–759, 2007.
4. N. Courtois and J. Pieprzyk, “Cryptanalysis of Block Ciphers with Overdefined Systems of Equations,” ASIACRYPT 2002, LNCS 2501, pp. 267–287. doi:10.1007/3-540-36178-2_17
5. T. Jakobsen and L.R. Knudsen, “The Interpolation Attack on Block Ciphers,” FSE 1997, LNCS 1267, pp. 28–40. doi:10.1007/BFb0052332
6. A. Nitaj, W. Susilo, and J. Tonien, “A New Improved AES S-box with Enhanced Properties,” ACISP 2020, LNCS 12248, pp. 125–141. doi:10.1007/978-3-030-55304-3_7
7. H. Li, Y. Zhou, J. Ming, G. Yang, and C. Jin, “The notion of transparency order, revisited,” The Computer Journal 63(12), pp. 1915–1938, 2020. doi:10.1093/comjnl/bxaa069
8. J. Daemen and V. Rijmen, The Design of Rijndael: AES — The Advanced Encryption Standard, Springer, 2002. doi:10.1007/978-3-662-04722-4
9. P.-P. Duong and C.-K. Pham, “Constructing 8×8 S-Boxes with Optimal Boolean Function Nonlinearity,” Cryptography 9(4), 67, 2025. doi:10.3390/cryptography9040067
10. R. Mishra, B. Singh, and R. Delhibabu, “Searching for S-boxes with better Diffusion using Evolutionary Algorithm,” IACR Cryptology ePrint Archive, 2023/353, 2023. eprint.iacr.org/2023/353
11. M.S. Jawed and M. Sajid, “COBLAH: A chaotic OBL initialized hybrid algebraic-heuristic algorithm for optimal S-box construction,” Computer Standards & Interfaces, 2024. https://doi.org/10.1016/j.csi.2024.103890
12. R. Cheng, Y. Zhou, X. Miao, and J. Hu, “Analysis of a New Improved AES S-Box Structure,” in Security and Privacy in New Computing Environments (SPNCE 2022), LNICST vol 496, Springer, 2023. doi:10.1007/978-3-031-30623-5_8
13. H.A.M.A. Basha, A.S.S. Mohra, T.O.M. Diab, and W.I. El Sobky, “Efficient Image Encryption Based on New Substitution Box Using DNA Coding and Bent Function,” IEEE Access 10, pp. 66409–66429, 2022. doi:10.1109/ACCESS.2022.3183990
14. W.I. El Sobky, A.R. Mahmoud, A.S. Mohra, and T. El-Garf, “Enhancing Hierocrypt-3 Performance by Modifying Its S-Box and Modes of Operations,” Journal of Communications 15(12), pp. 905–912, 2020. doi:10.12720/jcm.15.12.905-912
15. S. Picek, K. Papagiannopoulos, B. Ege, L. Batina, and D. Jakobovic, “Confused by Confusion: Systematic Evaluation of DPA Resistance of Various S-boxes,” in Progress in Cryptology — INDOCRYPT 2014, LNCS vol 8885, Springer, 2014, pp. 374–390. doi:10.1007/978-3-319-13039-2_22
16. C. Beierle, J. Jean, S. Kölbl, G. Leander, A. Moradi, T. Peyrin, Y. Sasaki, P. Sasdrich, and S.M. Sim, “The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS,” in Advances in Cryptology — CRYPTO 2016, LNCS vol 9815, Springer, 2016, pp. 123–153. doi:10.1007/978-3-662-53008-5_5