Efficient methods to generate cryptographically significant binary diffusion layers

In this study, the authors propose new methods using a divide-and-conquer strategy to generate n x n binary matrices ( for composite n) with a high/maximum branch number and the same Hamming weight in each row and column. They introduce new types of binary matrices: namely, (BHwC)(t,m) and (BCwC)(q,m) types, which are a combination of Hadamard and circulant matrices, and the recursive use of circulant matrices, respectively. With the help of these hybrid structures, the search space to generate a binary matrix with a high/maximum branch number is drastically reduced. By using the proposed methods, they focus on generating 12 x 12, 16 x 16 and 32 x 32 binary matrices with a maximum or maximum achievable branch number and the lowest implementation costs (to the best of their knowledge) to be used in block ciphers. Then, they discuss the implementation properties of binary matrices generated and present experimental results for binary matrices in these sizes. Finally, they apply the proposed methods to larger sizes, i.e. 48 x 48, 64 x 64 and 80 x 80 binary matrices having some applications in secure multi-party computation and fully homomorphic encryption.