Analysis of the Minimum Decimation Distance of Decimation Attack

Decimation attack is one attack method of stream ciphers. In this paper, the decimation attack to prime Linear Feedback Shift Register(LFSR) sequences is investigated. The connection of decimation distance and the linear complexity of the original sequence and the decimate sequence is presented. The minimum decimate distance that makes the linear complexity of the decimate sequence less than that of the original sequence is obtained. The minimum known plaintext amount for decimation attack is given, and the practical feasibility of the decimation attack to prime LFSRs is analyzed. It is proved that the decimation attack to prime LFSR is useful possibly only in the case that the degree of LFSR is very small.