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 LFSR’s 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.