Linear Cryptanalysis of 2-round Trivium with Multiple Approximations

Trivium has successfully been chosen as one of the final ciphers by eSTREAM. It has a simple and elegant structure. Although Trivium has attached a lot of interest, it remains unbroken. By finding more linear approximations, a linear cryptanalysis of 2-round Trivium is made by utilizing multiple approximations and a more efficient distinguishing attack is proposed. Compared with current single linear cryptanalysis, this method allows for a reduction in the amount of data required for a successful attack. That is to say, if n linear approximations can be found, this method can supply the success rate with 1/n of the data amount required by a simple linear cryptanalysis. This study shows that there are still some defects in the design of stream cipher Trivium, further safety analysis are needed before its going into the implementation.