IEEE International Symposium on Information Theory (ISIT)
An Efficient Algorithm to Sample Dual-Containing Low-Density Parity-Check Codes
Paolo Santini
Abstract
In this paper, we present an efficient algorithm to sample a random, sparse rectangular matrix H such that HH⊤= 0. Such matrices can be used, for instance, to define dual containing Low-Density Parity-Check (LDPC) codes, which are useful for building quantum codes according to the Calderbank-Shor-Steane (CSS) construction. Differently from existing works, we do not start from any strong algebraic structure but aim to obtain a matrix H as random as possible. We do this by sampling the matrix row by row, enforcing that each new row is orthogonal to all the rows we have already found. Technically, this is done by searching for a low weight codeword in the dual of the space generated by the already found rows. Interestingly, to efficiently find such a codeword, we rely on Information Set Decoding (ISD), which is a technique used for the cryptanalysis of code-based cryptosystems. We show that, when the desired row weight for H is low enough, our algorithm is likely to succeed and run efficiently; numerical simulations confirm the efficiency and effectiveness of our approach.