A Public Key Cryptosystem Using a Group of Permutation Polynomials

In this paper we propose an efficient multivariate encryption scheme based on permutation polynomials over finite fields. We single out a commutative group ℒ(q, m) of permutation polynomials over the finite field F_qm. We construct a trapdoor function for the cryptosystem using polynomials in ℒ(2, m), where m =2^k for some k ≥ 0. The complexity of encryption in our public key cryptosystem is O(m³) multiplications which is equivalent to other multivariate public key cryptosystems. For decryption only left cyclic shifts, permutation of bits and xor operations are used. It uses at most 5m²+3m – 4 left cyclic shifts, 5m² +3m + 4 xor operations and 7 permutations on bits for decryption.