Cryptographic properties of cyclic binary matrices

Many modern symmetric ciphers apply MDS or almost MDS matrices as diffusion layers. The performance of a diffusion layer depends on its diffusion property measured by branch number and implementation cost which is usually measured by the number of XORs required. As the implementation cost of MDS matrices of large dimensions is high, some symmetric ciphers use binary matrices as diffusion layers to trade-off efficiency versus diffusion property. In the current paper, we investigate cyclic binary matrices (CBMs for short), mathematically. Based upon this theorical study, we provide efficient matrices with provable lower bound on branch number and minimal number of fixed-points. We consider the product of sparse CBMs to construct efficiently implementable matrices with the desired cryptographic properties.