Correlation Analysis Of TRIVIUM

Trivium is one of the final winner algorithms in the project of E-STREAM which was designed by De Canniere and Bart Preneel. As the algorithm is designed to be simple and easy hardware implementation, Trivium has been widely concerned in cryptography. Excellent stream ciphers need a high pseudo-randomness, that is to say the key stream bits need to meet the Golomb pseudo-random theorem: balance, correlation and run-length distribution. In which correlation is a very important indicator because it is a basis to distinguish attack. The correlation of Trivium is mainly studied in this paper. Many results are as follows:(1)Trivium can be seen as a binary keystream generator with 288 bits of memory whose initial state is chosen uniformly at random, there exits a linear function L of at most 289 consecutive output bits which is an unbalanced function of the initial state variables. Such L function is only one currently, and nine new such functions have been obtained by Gauss elimination.(2)If the key length is k, distinguish attack is effective if and only if the correlation is greater than 2^k/2. Therefore, the relevant bias is the basis for a distinguish attack. In this paper, through analyzing nine related polynomials which are referred in (1), obtain the relevant bias.