JournalsrmiVol. 19, No. 2pp. 667–685

An Application of Algebraic Geometry to Encryption: Tame Transformation Method

  • T.T. Moh

    Purdue University, West Lafayette, USA
An Application of Algebraic Geometry to Encryption: Tame Transformation Method cover
Download PDF

Abstract

Let KK be a finite field of 22^{\ell} elements. Let ϕ4,ϕ3,ϕ2,ϕ1\phi_4,\phi_3, \phi_2,\phi_1 be tame mappings of the n ⁣+rn\!+r-dimensional affine space Kn+rK^{n+r}. Let the composition ϕ4ϕ3ϕ2ϕ1\phi_4\phi_3\phi_2\phi_1 be π\pi. The mapping π\pi and the ϕi\phi_i's will be hidden. Let the component expression of π\pi be (π1(x1,,xn+r),πn+r(x1,,xn+r))(\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 π^=(π1(x1,,xn,0,,0),,πn+r(x1,,xn,0,,0))=(f1,,fn+r):Kn mapstoKn+r\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 KK and the polynomial map (f1,,fn+rf_1,\dots,f_{n+r}) will be announced as the public key. Given a plaintext (x1,,xn)Kn(x'_1,\dots,x'_n)\in K^n, let yi=fi(x1,,xn)y'_i=f_i(x'_1,\dots,x'_n), then the ciphertext will be (y1,,yn+r)Kn+r(y'_1,\dots,y'_{n+r})\in K^{n+r}. Given ϕi\phi_i and (y1,,yn+ry'_1,\dots,y'_{n+r}), it is easy to find ϕi1(y1,,yn+r)\phi_i^{-1}(y'_1,\dots,y'_{n+r}). Therefore the plaintext can be recovered by (x1,,xn,0,,0)=ϕ11ϕ21ϕ31ϕ41π^(x1,,xn)=ϕ11ϕ21ϕ31ϕ41(y1,,yn+r)(x'_1,\dots,x'_n,0,\dots,0) = \phi_1^{-1}\phi_2^{-1} \phi_3^{-1}\phi_4^{-1}\,\hat\pi\,(x'_1,\dots,x'_n)=\phi_1^{-1} \phi_2^{-1}\phi_3^{-1}\phi_4^{-1}(y'_1,\dots, y'_{n+r}). The private key will be the set of maps {ϕ1,ϕ2,ϕ3,ϕ4}\{\phi_1,\phi_2,\phi_3,\phi_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 ϕi\phi_i's.

Cite this article

T.T. Moh, An Application of Algebraic Geometry to Encryption: Tame Transformation Method. Rev. Mat. Iberoam. 19 (2003), no. 2, pp. 667–685

DOI 10.4171/RMI/364