Improved Fast Correlation Attack on the Shrinking and Self-shrinking Generators

摘要

The fast correlation attack on the shrinking generator proposed by Zhang et al. in [8] has a room for improvement that the probability that the guessing bit is incorrect increases in certain case. In this paper, we propose a method to improve Zhang et al.'s attack. Reflecting our idea, the fast correlation attack on the shrinking and self-shrinking generator is more efficient than Zhang et al.'s attack in both data and computational complexities. For the shrinking generator, required keystream bits and computational complexity are reduced about 69% and 27%, respectively; For the self-shrinking generator, required keystream bits and computational complexity are reduced about 46% and 22%, respectively.