An Application of Algebraic Geometry to Encryption: Tame Transformation Method

Let K be a finite field of 2 elements. Let φ4, φ3, φ2, φ1 be tame mappings of the n+ r-dimensional affine space Kn+r. Let the composition φ4φ3φ2φ1 be π. The mapping π and the φi’s will be hidden. Let the component expression of π be (π1(x1, . . . , xn+r), . . . πn+r(x1, . . . , xn+r)). Let the restriction of π to a subspace be π as π = (π1(x1, ..., xn, 0, ..., 0), . . . , πn+r(x1, . . . , xn, 0, . . . , 0))= (f1, . . . , fn+r) : K → Kn+r. The field K and the polynomial map (f1, . . . , fn+r) will be announced as the public key. Given a plaintext (x′1, . . . , x′n) ∈ Kn, let y′ i = fi(x ′ 1, . . . , x ′ n), then the ciphertext will be (y′ 1, . . . , y′ n+r) ∈ Kn+r. Given φi and (y′ 1, . . . , y′ n+r), it is easy to find φ −1 i (y ′ 1, . . . , y ′ n+r). Therefore the plaintext can be recovered by (x′1, . . . , x′n, 0, . . . , 0) = φ−1 1 φ −1 2 φ −1 3 φ −1 4 π (x ′ 1, . . . , x ′ n) = φ −1 1 φ −1 2 φ −1 3 φ −1 4 (y ′ 1, . . . , y ′ n+r). The private key will be the set of maps {φ1, φ2, φ3, φ4}. The security of the system rests in part on the difficulty of finding the map π from the partial informations provided by the map π and the factorization of the map π into a product (i.e., composition) of tame transformations φi’s.