An Application of Algebraic Geometry to Encryption: Tame Transformation Method

Abstract

Let $K$ be a finite field of $2^{\ell }$ elements. Let ${\varphi }_4,{\varphi }_3,{\varphi }_2,{\varphi }_1$ be tame mappings of the $n+r$-dimensional affine space $K^{n+r}$. Let the composition ${\varphi }_4{\varphi }_3{\varphi }_2{\varphi }_1$ be $\pi$. The mapping $\pi$ and the ${\varphi }_i$'s will be hidden. Let the component expression of $\pi$ be $({\pi }_1(x_1,\dots ,x_{n+r}),\dots {\pi }_{n+r}(x_1,\dots ,x_{n+r}))$. Let the restriction of $\pi$ to a subspace be $\hat{\pi }$ as $\hat{\pi }=({\pi }_1(x_1,\dots ,x_n,0,\dots ,0),\dots ,{\pi }_{n+r}(x_1,\dots ,x_n,0,\dots ,0))=(f_1,\dots ,f_{n+r}):K^{n}mapsto{K}^{n+r}$. The field $K$ and the polynomial map ($f_1,\dots ,f_{n+r}$) will be announced as the public key. Given a plaintext $(x_1^{\prime },\dots ,x_n^{\prime })\in K^n$, let $y_i^{\prime }=f_i(x_1^{\prime },\dots ,x_n^{\prime })$, then the ciphertext will be $(y_1^{\prime },\dots ,y_{n+r}^{\prime })\in K^{n+r}$. Given ${\varphi }_i$ and ($y_1^{\prime },\dots ,y_{n+r}^{\prime }$), it is easy to find ${\varphi }_i^{-1}(y_1^{\prime },\dots ,y_{n+r}^{\prime })$. Therefore the plaintext can be recovered by $(x_1^{\prime },\dots ,x_n^{\prime },0,\dots ,0)={\varphi }_1^{-1}{\varphi }_2^{-1}{\varphi }_3^{-1}{\varphi }_4^{-1}\hat{\pi }(x_1^{\prime },\dots ,x_n^{\prime })={\varphi }_1^{-1}{\varphi }_2^{-1}{\varphi }_3^{-1}{\varphi }_4^{-1}(y_1^{\prime },\dots ,y_{n+r}^{\prime })$. The private key will be the set of maps $\{{\varphi }_1,{\varphi }_2,{\varphi }_3,{\varphi }_4\}$. The security of the system rests in part on the difficulty of finding the map $\pi$ from the partial informations provided by the map $\hat{\pi }$ and the factorization of the map $\pi$ into a product (i.e., composition) of tame transformations ${\varphi }_i$'s.