### 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.

Original language | English |
---|---|

Title of host publication | Cryptography and Coding : 12th IMA International Conference, Cryptography and Coding 2009 Cirencester, UK, DEcenber 2009 |

Editors | Matthew G. Parker |

Publisher | Springer |

Publication date | 2009 |

Pages | 133-152 |

ISBN (Print) | 978-3-642-10867-9 |

Publication status | Published - 2009 |

Event | 12th IMA International Conference on Cryptography and Coding - Duration: 1 Jan 2009 → … |

### Conference

Conference | 12th IMA International Conference on Cryptography and Coding |
---|---|

Period | 01/01/2009 → … |

Series | Lecture Notes of Computer Science |
---|---|

Number | 5921 |

ISSN | 0302-9743 |

## Cite this

Borghoff, J., Knudsen, L. R., & Stolpe, M. (2009). Bivium as a Mixed Integer Programming Problem. In M. G. Parker (Ed.),

*Cryptography and Coding: 12th IMA International Conference, Cryptography and Coding 2009 Cirencester, UK, DEcenber 2009*(pp. 133-152). Springer. Lecture Notes of Computer Science, No. 5921