Uma transformação afim é uma transformação entre dois espaços afins A e B. Essa transformação, ou mapeamento, consiste numa transformação lineal em A somado de um vetor b \in B. Ou seja:
S(x)=Tx + b.
No campo da criptografia post-quântica as transformações afins são usadas para ocultar a chave pública dos sistemas de cifração baseados em multivariados.
Para os envolvidos na área é de importância saber lidar com as diferentes representações de uma transformação afim. Neste post apresentarei essas representações e mostrarei como converter uma para a outra.
Seja \mathbb{F} um corpo finito com q elementos e \mathbb{E} uma extensão de grau n do corpo \mathbb{F}. Seja S:\mathbb{F}^n\rightarrow \mathbb{F}^n uma transformação afim.
Definição 1: Seja 0\leq i < n e A,B_i \in \mathbb{E}. Então nós chamamos o polinômio S(X)=\sum_{i=0}^{n-1}B_i X^{{q}^i}+A a representação de uma só variável da transformação afim S.
Definição 2: Seja M_S \in \mathbb{F}^{n\times n} uma matriz e v_s \in \mathbb{F}^n um vetor. Então nos chamamos S(x):=M_Sx+v_s, a representação matricial da transformação afim S .
Definição 3: Seja o espaço vetorial \mathbb{F}^n. Então nós chamamos \phi:\mathbb{E}\rightarrow \mathbb{F}^n com \phi(a):=b e b_i=a_{i-1} de bijeção canônica.
Teorema: Uma transformação afim, com v=0 na representação de uma só variável pode ser transformada eficientemente na sua representação matricial.
Prova: Definamos e_i \in \mathbb{F}^n com 1\leq i \leq n, com um 1 no seu i-th coeficiente e zero no restante. Vamos a mostrar que a coluna k dessa matriz é dada pela seguinte fórmula: M_k=\phi(S(\phi^{-1}(e_k))). Vamos a definir P(X):=\sum_{i=0}^{n-1}B_i X^{{q}^i}. Da álgebra conhecemos que o corpo \mathbb{F}^n é também um espaço vetorial sobre o corpo \mathbb{F}. Esse espaço vetorial tem a base V=\{t^0, t^1, t^2,\ldots,t^{{n-1}}\}. Vamos a representar os coeficiente de P(X) como B_i =\sum_{j=0}^{n-1}b_{ij} t^j e a variável X=\sum_{k=0}^{n-1}X_{k}t^k. Substituindo esses valores em P(X) temos P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} t^j(\sum_{k=0}^{n-1}X_{k}t^k)^{{q}^i},
Usando o teorema binomial e reduzindo temos
P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}t^{j+k{{q}^i}},
Escrevendo t^{j+k{{q}^i}} usando a base V temos t^{j+k{{q}^i}} = \sum_{m=0}^{n-1}c_{ijkm}t^m. Por tanto:
P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k} \sum_{m=0}^{n-1}c_{ijkm}t^m
P(X) = \sum_{m=0}^{n-1}\underline{\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}c_{ijkm}}_{E}t^m
Por outro lado, escrevendo \phi(S(\phi^{-1}(e_k))) usando a base V temos que esta é igual a: \phi(S(\phi^{-1}(e_k)))=(\sum_{i,j}^{n-1}b_{i,j}c_{ijk0}, \cdots, \sum_{i,j}^{n-1}b_{i,j}c_{ijk(n-1)}). Por fim, veja que E_m = (\phi(S(\phi^{-1}(e_1)))[m],\cdots,\phi(S(\phi^{-1}(e_{n-1})))[m])^{T}*(X_1,\cdots, X_{n-1}).
No caso de transformação afim com v \neq 0 então se tem que v:=M_k=\phi(S(\phi^{-1}(0))) e as colunas de M são M_k=\phi(S(\phi^{-1}(e_k)))-v.
