Mixing properties of modified additive generators

Abstract

We develop amatrix-graph approach to estimating themixing properties of bijective shift registers over a set of binary vectors. Such shift registers generalize, on the one hand, the class of ciphers based on the Feistel network and, on the other hand, the class of transformations of additive generators (the additive generators are the base for the Fish, Pike, andMush algorithms). It is worth noting that the original schemes of additive generators are found insecure due to their weak mixing properties. The article contains the results of investigations for the mixing properties of modified additive generators. For the mixing directed graph of a modified additive generator, we define the sets of arcs and cycles, obtain primitivity conditions, and give a bound for the exponent. We show that, the determination of parameters for the modified additive generator allows us to achieve a full mixing in a number of iterations that is substantially less than the number of vertices in the mixing digraph.