LAUSR

We study the problem how to efficiently generate circulant binary matrices with a prescribed number of ones which are invertible over ℤ2$\mathbb {Z}_{2}$. A natural method to generate such matrices consists of two steps. Firstly, a circulant binary matrix with the prescribed number of ones is generated. Afterwards, it is tested for invertibility and if needed the process is repeated. To increase the efficiency of the process, we are interested in generating the matrices directly, without the need for the additional invertibility testing. We propose algorithms which fulfill this task for a wide range of parameters. Furthermore, we propose algorithms to construct matrices S and Q in the QC-LDPC McEliece cryptosystem. Matrices S and Q have to be composed of blocks of circulant matrices and they have to be invertible. In addition, S has to be dense and Q has to have a prescribed number of ones in a row. To avoid known attacks on the QC-LDPC McEliece cryptosystem, our algorithms generate S and Q with blocks of an odd size.