| The Matsumoto-Imai cryptosystem was eventually defeated by Patarin's linearization attack. This attack takes advantage of the special algebraic structure of MI to produce a set of linearization equations that can be used to find the plaintext associated with a given ciphertext. In this paper, we present a solution to the problem of finding the dimension of the space of linearization equations. In particular, we show that this space has dimension n in general, and has dimension 2n, 2n3 , 3n2 , 8 or 7 in some exceptional cases.;We show that for some small prime number, the group generated by invertible Dickson and linear polynomials over the finite field of p elements Zp is the whole symmetric group over Zp and consequently any permutation of can be described explicitly in terms of composition of these polynomials. For a general prime number p, we study the properties of this group and the properties of the cycles of the permutations generated by Dickson polynomials. We show that the answer to the question, if the group generated by invertible Dickson and linear polynomials over the finite field Zp is the whole symmetric group over Zp, is indeed a non-trivial problem, particularly in terms of computational point of view. |
