Exact Probabilistic Analysis of Memoryless Combiners
Jovan Dj. Golić · IEEE Transactions on Information Theory · 2007
Exact analytical expressions for various probability distributions in a type of stream ciphers known as memoryless combiners are derived. They relate to arbitrary linear functions and subvectors of output bits as well as to arbitrary linear functions and subvectors of input bits when the output sequence is assumed to be given. Practical approximations to the exact expressions to be used in one-step and iterative fast correlation attacks and statistical distinguishers are proposed. More generally, the results also apply to arbitrary binary linear codes that are nonlinearly transformed by time-variant Boolean functions. For comparison, the corresponding probability distributions for linear block codes on a memoryless time-variant binary symmetric channel are also determined and some practical consequences pointed out.