@inproceedings{868e036d5a684a2492c8dc07d7096321,

title = "Bivium as a Mixed Integer Programming Problem",

abstract = "Trivium is a stream cipher proposed for the eSTREAM project. Raddum introduced some reduced versions of Trivium, named Bivium A and Bivium B. In this article we present a numerical attack on the Biviums. The main idea is to transform the problem of solving a sparse system of quadratic equations over $GF(2)$ into a combinatorial optimization problem. We convert the Boolean equation system into an equation system over $\mathbb{R}$ and formulate the problem of finding a $0$-$1$-valued solution for the system as a mixed-integer programming problem. This enables us to make use of several algorithms in the field of combinatorial optimization in order to find a solution for the problem and recover the initial state of Bivium. In particular this gives us an attack on Bivium B in estimated time complexity of $2^{63.7}$ seconds. But this kind of attack is also applicable to other cryptographic algorithms.",

author = "Julia Borghoff and Knudsen, {Lars Ramkilde} and Mathias Stolpe",

year = "2009",

language = "English",

isbn = "978-3-642-10867-9",

series = "Lecture Notes of Computer Science",

publisher = "Springer",

number = "5921",

pages = "133--152",

editor = "Parker, {Matthew G.}",

booktitle = "Cryptography and Coding",

note = "12th IMA International Conference on Cryptography and Coding ; Conference date: 01-01-2009",

}