Cryptology ePrint Archive: Report 2004/247
Vectorial fast correlation attacks
Jovan Dj. Golic and Guglielmo Morgari
Abstract: 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, all the input sequences can be targeted simultaneously.
The attack is based on a novel iterative
probabilistic algorithm which is also applicable to general memoryless combiners over finite fields or finite
Experimental results obtained for randomly chosen binary combiners with balanced combining functions show
that the vectorial approach yields a considerable improvement in comparison with the classical, scalar approach.
Category / Keywords: secret-key cryptography / stream ciphers, sequential linear cryptanalysis, correlation attacks, iterative probabilistic decoding
Date: received 22 Sep 2004
Contact author: golic at inwind it
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Note: The first version of this paper with a different coauthor, and different contents with respect to algorithms and experimental results, will be published in Designs, Codes and Cryptography in 2005. This is explained in a footnote on the first page.
Version: 20040922:195707 (All versions of this report)
Short URL: ia.cr/2004/247
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]