Modeling Bit Flipping Decoding Based on Nonorthogonal Check Sums With Application to Iterative Decoding Attack of McEliece Cryptosystem

In this correspondence, iteration-1 of bit flipping decoding based on a set of nonorthogonal check sums is analyzed for both regular and irregular models. In particular, the tradeoff between the Hamming weight (and overlapping) of the check sums and the number of redundant check sums required to start converging under iterative decoding is investigated. The model is then applied to an iterative attack of McEliece public-key cryptosystem since a successful attack of this system can be achieved by algebraic bounded distance decoding of a random code. Based on this model, the attack can be decomposed into two phases: a preprocessing phase which, for one particular key kappa, consists of finding a sufficiently large set S of check sums up to a certain Hamming weight, and a bit flipping decoding phase which uses the set S for each message encrypted with the key kappa