Vectorial Approach to Fast Correlation Attacks

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 presentedMost of this work was done while he was with Rome CryptoDesign Center, Gemplus, Italy