turkmath.org

In this presentation, we propose new methods using a divide-and-conquer strategy to generate $n \times n$ binary matrices (for composite $n$) with a high/maximum branch number and the same Hamming weight in each row and column. We 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, we focus on generating $12 \times 12$, $16 \times 16$ and $32 \times 32$ binary matrices with a maximum or maximum achievable branch number and low implementation costs to be used in block ciphers. Then, we discuss the implementation properties of binary matrices generated and present experimental results for binary matrices in these sizes. Finally, we apply the proposed methods to larger sizes, i.e., $48 \times 48$, $64 \times 64$ and $80 \times 80$ binary matrices having some applications in secure multi-party computation and fully homomorphic encryption.