Abstract
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):Kn mapstoKn+r. The field K and the polynomial map (f1,…,fn+r) will be announced as the public key. Given a plaintext (x1′,…,xn′)∈Kn, let yi′=fi(x1′,…,xn′), then the ciphertext will be (y1′,…,yn+r′)∈Kn+r. Given ϕi and (y1′,…,yn+r′), it is easy to find ϕi−1(y1′,…,yn+r′). Therefore the plaintext can be recovered by (x1′,…,xn′,0,…,0)=ϕ1−1ϕ2−1ϕ3−1ϕ4−1π^(x1′,…,xn′)=ϕ1−1ϕ2−1ϕ3−1ϕ4−1(y1′,…,yn+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.