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.

1 comment:

badarbabyak said...

Lucky Creek Casino - MapyRO
Information and Reviews about 경산 출장샵 Lucky Creek Casino, including 상주 출장마사지 Hotels, Rooms, Phone Number, 서울특별 출장안마 Address, 대구광역 출장안마 Games, 포항 출장샵 Games, Slots, Poker, Agenda, Parties,

Related Posts Plugin for WordPress, Blogger...