Paper 2023/1124

An Algebraic Approach to Circulant Column Parity Mixers

Abstract

Column Parity Mixers, or CPMs in short, are a particular type of linear maps, used as the mixing layer in permutation-based cryptographic primitives like Keccak-f (SHA3) and Xoodoo. Although being successfully applied, not much is known regarding their algebraic properties. They are limited to invertibility of CCPMs, and that the set of invertible CCPMs forms a group. A possible explanation is due to the complexity of describing CPMs in terms of linear algebra. In this paper, we introduce a new approach to studying CPMs using module theory from commutative algebra. We show that many interesting algebraic properties can be deduced using this approach, and that known results regarding CPMs turn out to be trivial consequences of module theoretic concepts. We also show how this approach can be used to study the linear layer of Xoodoo, and other linear maps with a similar structure which we call DCD-compositions. Using this approach, we prove that every DCD-composition where the underlying vector space with the same dimension as that of Xoodoo has a low order. This provides a solid mathematical explanation for the low order of the linear layer of Xoodoo, which equals 32. We design a DCD-composition using this module theoretic approach, but with a higher order using a different dimension.