On nonabelian key addition groups and markovian block ciphers

In this paper, (X, *) is an arbitrary key addition group, W = {W₀,..., W_r-1} is a partition of X, S(X) is the symmetric group on X. In 1991, X. Lai, J. L. Massey and S. Murphy introduced markovian block ciphers. We investigate a markovian block cipher Q(*,b) where l is the round number, b is a permutation on X, g : X² - X is the round function defined by g : (x, k) - b(x * k). In the previous paper, we introduced *_W-markovian block ciphers, which are a generalization of markovian ciphers, and *_W-markovian transformations. The block cipher Q(*,b) is *_W-markovian iff the permutation b is *_W-markovian. We have proved that if g preserves W, then G = (b, X*) is an imprimitive group and W is an imprimitivity system where X* is the right permutation representation of (X, *). Moreover, if G is imprimitive, then there exists a canonical homomorphism : G - S({0,..., r - 1}). We have proved that in the case (W₀, *) < (X, *), the cipher C(*, b) is *_W-markovian iff there exists a homomorphism . For cryptographic applications, we are interested in groups of order 2^m. In this paper, we consider all four nonabelian groups of order 2^m having a cyclic subgroup of index 2. These four groups include a dihedral group and a generalized quaternion group. For all four groups, we have described *_W-markovian permutations such that W is the right coset space (X : Wo = W), but (Wo, *) ^ (X, *).

Keywords

Authors

References