AES Affine Transformation in $GF(2^4)$

Question

in $GF(2^8)$ the AES affine transformation is defined as \begin{equation*} b( x ) = ( x^7 + x^6 + x^2 + x ) + a ( x )( x^7 + x^6 + x^5 + x^4 + 1) mod (x^8 + 1) \end{equation*} where the polynom $( x^7 + x^6 + x^2 + x )$ represents the constant term and $( x^7 + x^6 + x^5 + x^4 + 1) mod (x^8 + 1)$ is the matrix, which is multiplied with the inverse a(x). This results in a function \begin{equation*} AT(a) = \begin{bmatrix} 1& 1& 1& 1& 1& 0& 0& 0 \\ 0& 1& 1& 1& 1& 1& 0& 0 \\ 0& 0& 1& 1& 1& 1& 1& 0 \\ 0& 0& 0& 1& 1& 1& 1& 1 \\ 1& 0& 0& 0& 1& 1& 1& 1 \\ 1& 1& 0& 0& 0& 1& 1& 1 \\ 1& 1& 1& 0& 0& 0& 1& 1 \\ 1& 1& 1& 1& 0& 0& 0& 1 \end{bmatrix} \begin{bmatrix} a_7\\a_6\\a_5\\a_4\\a_3\\a_2\\a_1\\a_0 \end{bmatrix} \oplus \begin{bmatrix} 0\\1\\1\\0\\0\\0\\1\\1 \end{bmatrix} \end{equation*} where $a_7$ is the most significant bit of the inverse. My Question is now, if I use an isomorphic mapping \begin{equation*} \delta = \begin{bmatrix} 1& 0& 1& 0& 0& 0& 0& 0 \\ 1& 1& 0& 1& 1& 1& 1& 0 \\ 1& 0& 1& 0& 1& 1& 0& 0 \\ 1& 0& 1& 0& 1& 1& 1& 0 \\ 1& 1& 0& 0& 0& 1& 1& 0 \\ 1& 0& 0& 1& 1& 1& 1& 0 \\ 0& 1& 0& 1& 0& 0& 1& 0 \\ 0& 1& 0& 0& 0& 0& 1& 1 \end{bmatrix} \end{equation*} for the input of the AES Subbyte to calculate the inverse in $GF(2^4)$, how would the affine transformation look like or how can I calculate this? After the affine Transformation in $GF(2^4)$ I want to use the inverse isomorphic mapping \begin{equation*} \delta^{-1} = \begin{bmatrix} 1& 1& 1& 0& 0& 0& 1& 0 \\ 0& 1& 0& 0& 0& 1& 0& 0 \\ 0& 1& 1& 0& 0& 0& 1& 0 \\ 0& 1& 1& 1& 0& 1& 1& 0 \\ 0& 0& 1& 1& 1& 1& 1& 0 \\ 1& 0& 0& 1& 1& 1& 1& 0 \\ 0& 0& 1& 1& 0& 0& 0& 0 \\ 0& 1& 1& 1& 0& 1& 0& 1 \\ \end{bmatrix} \end{equation*} to get the result of the S-Box back to $GF(2^8)$.

Answer 1

There are alternative representations of $GF(2^8)$ where the multiplicative inverse can be computed by computing the inverse in $GF(2^4)$, along with a handful of other operations (several $GF(2^4)$ multiplies, additions and a square). Does your $\delta$ convert from the standard AES representation into such an alternative representation of $GF(2^8)$?

(Background: a representation is how we translate members of the abstract object known as $GF(2^8)$ into bitpatterns. When we talk about, say, a prime field $GF(p)$, there's one obvious mapping between members of $GF(p)$ into the integers $[0, p)$, and it's hard to think of when another mapping would have any advantage. However, when we talk about $GF(2^8)$, there are lots of plausible ways; different representations make specific operations cheaper. The AES representation makes multiplying by the fixed element $2$ fairly cheap, at the expense of not giving an easy way of computing the multiplicative inverse). Other representations make computing the multiplicative inverse cheaper.

Assuming that is what your $\delta$ is doing, the obvious way to compute the sbox is to do:

$$SBox(x) = AT(\delta^{-1}(Inv(\delta(x))))$$

That is, we translate the value into our alternative represention, compute the inverse in that representation, translate the value back into the standard representation, and then continue with the standard sbox computation. You can compute the affine transform in the alternative represention; however it'll look like a random multiply by a fixed matrix, and be more expensive than the $AT$ in the standard representation).

If you feel like you have to compute the entire sbox in the alternative representation, then you can separate the affine transform into the linear multiplication $M$ and the constant vector $C$ (so $AT(x) = Mx + C$), and compute the values:

$$M' = \delta \times M \times \delta^{-1}$$

$$C' = \delta C$$

And so the operation $AT'(x) = M'x + C'$ is the affine operation entirely in the alternative representation. However, as above, multiplying by $M'$ won't likely be as cheap as multiplying by $M$ (whose regular structure allows for a lot of simplification).