juaninf - notas de psudoprogramador

Tuesday, February 04, 2014

Transformação Afim na Criptografia

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.$



Lema: Seja $A$ um mapeamento linear de n-tuples para n-tuples de valores em $\mathbb{F}$. Então existem coeficientes $a_0, \dots, a_{n-1}$ em $\mathbb{E}$ tais que para qualquer dois n-tuples $(X_0,\cdots,X_{n-1})$ e $(y_0,\cdots,y_{n-1})$ de elementos em $\mathbb{F}$, $(Y_0,\cdots,Y_{n-1})= A(X_0,\cdots,x_{n-1})$ se e só se $Y=\sum_{i=0}^{n-1}a_iX^{q^i}$, onde $X=\sum_{i=0}^{n-1}X_it^i$ e $Y=\sum_{i=0}^{n-1}Y_it^i$ são elementos de $\mathbb{E}$ o qual corresponde à duas n-tuples sobre $\mathbb{F}$.

Prova: ($\Rightarrow$)Veja que o número de matrizes de dimensões $n \times n$ com suas entradas em  $\mathbb{F}$ é $q^{n^2}$ (usando permutações). O número de polinômios de grau $n-1$ com coeficientes em $\mathbb{K}$ é $(q^{n})^n$. Então é possível associar os mapeamentos lineares na representação de uma só variável com uma matriz. No teorema anterior tínhamos visto que é possível converter uma transformação afim na sua representação matricial para sua representação de uma só variável. Então faltaria demonstrar que não pode existir uma matriz $A$ com duas representações de uma só variável para que exista uma correspondência biunivoca. Vamos a supor que existam dois polinômios, $p(X)=\sum_{i=0}^{n-1}a_iX^{q^i}$ e $q(X)=\sum_{i=0}^{n-1}b_iX^{q^i}$ distintos que representam $A$. Pela hipóteses existem então $q^n$ equações da forma  $Y=\sum_{i=0}^{n-1}a_iX^{q^i}$ e a mesma quantidade da forma  $Y=\sum_{i=0}^{n-1}b_iX^{q^i}$. Restar as equações um a um, $p(X)$ do $q(X)$. Repare então que vamos a ter $q^n$ equações da forma $p(X)-q(X)=0$, ou seja o polinômio $r(X)=p(X)-q(X)$ com grau máximo de $q^{n-1}$ com $q^{n}$ o qual é impossível.
Post a Comment
Related Posts Plugin for WordPress, Blogger...