Abstract:
A polynomial over a finite ring R is called a permutation polynomial of R if it induces a bijection from R to R. Permutation polynomials over finite rings have several applications in combinatorics, coding theory and cryptography. For example, the RC6 block cipher uses the permutation polynomial x + 2x2 over the finite ring Z2n, where 2n is the word size of machine. In 2001, Rivest found an exact characterization of permutation polynomials over finite rings Z2n. However, using Rivest's technique it was di±cult to characterize permutation polynomials over finite rings Zm, for m = 3n; 5n. In this thesis, we present some methods to characterize all permutation polynomials over finite rings Zm for m = 2n; 3n; 5n. In addition, we produce a new class of permutation binomials over the finite fields Zp. Moreover, we show that every polynomial over finite ring Zpn can be expressed as a triangular map over Zn p . Using this representation, we obtain su±cient conditions for a polynomial over Zpn to be a permutation polynomial, for any prime p. Next, we consider permutation polynomials over finite fields. Permutation polynomials over finite fields have been the subject of study for many years. There is a considerable interest in finding new classes of permutation polynomifials over finite fields. However, only a handful of specific classes of permutation polynomials are known so far and very few of the known classes have permutation polynomials commuting with one another. We find certain new classes of permutation polynomials over finite fields. Some of these classes are commutative. Multivariate public key cryptography is a branch of public key cryptography in which cryptosystems are based on the problem of solving nonlinear equations over finite fields. This problem is proven to be NP complete. MIC*, the first practical public key cryptosystem based on this problem, was proposed in 1988 by T. Matsumoto and H. Imai. This cryptosystem was more e±cient than RSA and ECC (Elliptic curve cryptosystems). Unfortunately, this cryptosystem was broken by Patarin. In 1996 Patarin gave a generalization of MIC* cryptosystem called HFE. However, in HFE the secret key computation was not as eficient as in the original MIC* cryptosystem. The basic instance of HFE was broken in 1999. In recent years, designing a public key cryptosystem based on the problem of solving system of nonlinear equations has been a challenging area of research. In this thesis, we have designed two eficient multivariate public key cryptosystems using permutation polynomials over finite fields. We have shown that these cryptosystems are secure against all the known attacks...