Upper bounds for a branch number of matrices over a ring of integers modulo power of two

Abstract

Branch number is a very important cryptographic parameter of linear mappings used in block ciphers. It significantly affects security against differential and linear cryptanalysis due to “wide trail strategy” of block cipher design. Many techniques are well known to generate linear mappings with maximal possible branch number in matrix form over finite fields (so-called MDS-matrices). In the same time operations over integers modulo power of two are important for cryptographic purposes. They are very efficient in modern computing architectures and increase security of cryptographic functions against algebraic attacks. But known techniques of MDS-matrix generating are not applicable to a ring of integers modulo composite number. In this work we proved that any square matrix over a ring of integers modulo even number cannot have a maximal branch number. We proved that the branch number of any square matrix over a ring of integers modulo power of two is invariant under reduction modulo 2. Thus, any analytic result known for binary matrices is valid for matrices modulo power of two, including upper bounds for the branch number. Consequently, the branch number of this type of matrix cannot exceed about two thirds of a matrix size. Also we formulated some requirements for binary matrices to obtain high value of the branch number; we show that such matrices cannot have both sparse (low weight) and dense (high weight) columns. At the end we shortly consider how the security of binary ciphers (e.g. ARIA or Midori) against linear and integral cryptanalysis can be increased by replacing binary matrix with matrix over a ring of integers modulo power of two in linear layer. The results of this work allow to create block ciphers with potentially improved security against algebraic and integral attacks and reasonable security against differential and linear cryptanalysis.