A new, vectorial approach to fast correlation attacks on binary memoryless combiners is proposed. Instead of individual input sequences or their linear combinations, the new attack is targeting subsets of input sequences as a whole thus exploiting the full correlation between the chosen subset and the output sequence. In particular, the set of all the input sequences can be chosen as the target. The attack is based on a novel iterative probabilistic algorithm which is also applicable to general memoryless combiners over finite fields or finite rings. To illustrate the effectiveness of the introduced approach, experimental results obtained for random balanced combining functions are presented
Keywords vectorial correlation attack - linear cryptanalysis - iterative probabilistic decoding - finite fields - nonlinear filter generator
Communicated by: H. Imai
Most of this work was done while he was with Rome CryptoDesign Center, Gemplus, Italy