Critical noise for convergence of iterative probabilistic decoding with belief propagation in cryptographic applications

Abstract

In this paper, the critical noise beyond which no convergence can be expected is determined for iterative decoding with belief propagation of binary linear block codes over the binary symmetric channel. This value is derived developing the self composition channel model first introduced for iterative a-posteriori-probability decoding. These results are then applied to the cryptanalysis of a keystream generator based on linear feedback shift registers.