Introducing the SEAv2 S-Box: A Slightly Higher-Quality Substitution Box via Fractional Linear and Affine Transformations

In a previous post, I introduced the SEA S-Box – an 8×8 substitution box constructed via Fractional Linear and Affine Transformations (FLAT) that matched or exceeded AES on nearly every cryptographic metric. The SEA S-Box was discovered through random seed exploration. Since then, I ran an exhaustive search mode – dubbed FLATv2 – that deterministically evaluates every canonical parameter combination, and it has revealed a slightly better S-Box. I’m calling it SEAv2.

From Random Search to Exhaustive Sweep

The original SEA S-Box was found by sampling random seeds and evaluating the resulting S-Boxes against 24 cryptographic quality metrics plus NIST SP 800-90B entropy assessments. While effective, this approach could not guarantee that the best possible FLAT S-Box had been found – only that the search had not yet found anything better.

FLATv2 closes this gap. It exhaustively iterates over every canonical FLT parameter combination across all 30 irreducible polynomials of GF(2⁸): 30 polynomials × 256 b-values × 255 c-values × 255 d-values = ~499 million combinations, evaluated in a deterministic shuffled order. Each combination is pre-filtered with 6 invariant metrics (nonlinearity ≥ 112, differential uniformity ≤ 4, algebraic degree = 254, vectorial nonlinearity ≥ 112, algebraic immunity ≥ 2, boomerang uniformity ≤ 6) before the full affine sweep. Surviving candidates are then evaluated against all 128 invertible circulant affine transforms × 256 XOR constants.

This exhaustive sweep found SEAv2 – an S-Box that improves on SEA in algebraic complexity.

The SEAv2 S-Box: Complete Specification

SEAv2 uses the same two-stage FLAT construction as SEA: a fractional linear transformation over GF(2⁸) followed by an affine transformation over GF(2). Among the 255 equivalent parameterizations of SEAv2, the simplest sets c = 1, reducing the FLT to:

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

compared to SEA’s more general S(x) = (ax + b) / (cx + d). Both the numerator and denominator are simple translations – just x plus a constant.

Irreducible Polynomial:

p(x) = x⁸ + x⁶ + x⁵ + x⁴ + x³ + x + 1    (0x17B)

Fractional Linear Parameters:

a = 1,   b = 135,   c = 1,   d = 98

The bijection-completing parameter (pole position) is t = 98.

Affine Transformation:

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

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

• XOR constant k = 122 (0x7A)

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

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

Metric-by-Metric Comparison: SEAv2 vs SEA vs AES

The following table compares SEAv2 against the original SEA S-Box and the AES (Rijndael) S-Box. Green indicates the best value among the three.

Metric	Optimal	SEAv2	SEA	AES
Nonlinearity	120	112	112	112
Vectorial Nonlinearity	120	112	112	112
BIC-NL	128	112	112	112
Differential Uniformity	2	4	4	4
Boomerang Uniformity	2	6	6	6
Feistel Boomerang Uniformity	0	4	4	4
Differential Branch Number	6	2	2	2
Linear Branch Number	7	2	2	2
Algebraic Degree	254	254	254	254
Algebraic Complexity	255	253	253	9
Inverse Algebraic Complexity	255	253	252	251
Total Algebraic Complexity	510	506	505	260
Algebraic Immunity	4	2	2	2
Autocorrelation	0	32	32	32
SAC RMSE	0.0	0.020109	0.020109	0.031735
SAC Mean	128.0	130.50	130.50	129.25
SAC Std Dev	0.0	0.017578	0.017578	0.031357
DSAC	0.0	232.0	232.0	432.0
BIC-SAC RMSE	0.0	0.028419	0.028419	0.031180
BIC-SAC Mean	0.5	0.501744	0.501744	0.504604
BIC-SAC Std Dev	0.0	0.028365	0.028365	0.030838
VTO	0.0	7.2547	7.2547	7.4583
Iterative Period	256	256	256	2
Number of Cycles	1	1	1	5

What Changed

SEAv2 is a marginal improvement over SEA. The only difference is the Inverse Algebraic Complexity: 252 → 253. The inverse S-box now has 253 non-zero terms in its polynomial representation (up from 252), bringing the total algebraic complexity from 505 to 506. This is now symmetric: both the forward and inverse directions have 253 terms. For context, AES has a total of 260 (9 + 251).

Everything else is identical. SEAv2 matches SEA on every differential, linear, boomerang, SAC, BIC-SAC, and VTO metric – nonlinearity 112, differential uniformity 4, boomerang uniformity 6, DSAC 232, SAC RMSE 0.020109, iterative period 256, single cycle. It shares all of SEA’s advantages over AES: near-doubled algebraic complexity, maximal permutation period, superior diffusion quality, and tighter SAC conformance.

Equivalence Classes

An interesting property of the FLAT construction is that many different parameter sets (polynomial, a, b, c, d, affine matrix, XOR constant) can produce the same S-Box. SEAv2 has 255 distinct representations – different combinations of FLT parameters and affine transforms that all yield the identical 256-byte permutation.

The representation chosen above (c = 1) is the simplest: both the numerator and denominator reduce to x + constant. Other representations use larger c values but compensate with different b, d, and affine parameters to arrive at the same mapping.

SEA in the Same Form

The original SEA S-Box was specified with parameters a=4, b=151, c=230, d=19 and a circulant affine matrix (first row = 0x58). But the same algebraic trick that simplifies SEAv2 can be applied to SEA.

Factoring out the scalar a/c from the original FLT:

S(x) = (4x + 151) / (230x + 19) = (4/230) · (x + 151/4) / (x + 19/230)

In GF(2⁸)/0x17B, we have 4/230 = 91, 151/4 = 123, and 19/230 = 207, giving:

S(x) = 91 · (x + 123) / (x + 207)

The GF(2⁸) scalar multiplication by 91 is a linear operation over GF(2) and can be absorbed directly into the affine matrix. The result is that SEA can also be expressed with a=1 and c=1:

• Fractional Linear Parameters: a = 1, b = 123, c = 1, d = 207
• Base transformation: S_base(x) = (x + 123) / (x + 207)
• Affine Matrix M’ – general 8×8 invertible binary matrix (the original circulant 0x58 composed with GF(2⁸) multiplication by 91):

        Col:  7 6 5 4 3 2 1 0
Row 0:        1 1 0 1 1 1 1 1   (0xDF)
Row 1:        1 1 0 0 1 1 0 1   (0xCD)
Row 2:        1 1 1 0 0 1 1 0   (0xE6)
Row 3:        1 1 1 1 0 0 1 1   (0xF3)
Row 4:        1 1 1 1 1 0 0 1   (0xF9)
Row 5:        1 1 1 1 1 1 0 0   (0xFC)
Row 6:        0 1 1 1 1 1 1 0   (0x7E)
Row 7:        1 0 1 1 1 1 1 1   (0xBF)

• XOR constant k = 100 (0x64)

This reveals that SEA and SEAv2 both can be represented in the simplified FLT form – S(x) = (x + b) / (x + d) – differing only in the constants:

	SEA	SEAv2
b	123	135
d	207	98
Affine matrix	General 8×8 (absorbed scalar)	Circulant (first row 0x85)
XOR constant	100 (0x64)	122 (0x7A)

The only structural difference is that SEA’s affine matrix is a general invertible matrix (the scalar 91 was folded in, breaking the circulant structure), while SEAv2’s affine matrix remains a clean circulant which can be represented more compactly as just the first row (since all other rows are just a shift of the first). The underlying fractional linear transformation – the cryptographic core – is identical in form.

Implementation

SEAv2 can be implemented with the same efficiency as SEA. The core operations are:

1. One GF(2⁸) addition (x + 135)
2. One GF(2⁸) addition (x + 98)
3. One GF(2⁸) multiplicative inverse
4. One 8×8 binary matrix-vector multiply (or equivalently, a table lookup)
5. One byte XOR with constant 0x7A

In practice, the entire S-Box is precomputed as a 256-byte lookup table, so the construction details only matter for specification and verification purposes.

Conclusion

SEAv2 is not a breakthrough over SEA – it is a refinement. The exhaustive FLATv2 search confirmed that the FLAT construction is capable of producing S-Boxes at the upper boundary of achievable quality for this algebraic family, and SEAv2 sits at that boundary with the simplest possible parameterization: both numerator and denominator are just x + constant. For any application where the SEA S-Box would be suitable, SEAv2 is a marginally better choice with identical performance characteristics and a cleaner algebraic specification.