Bivium as a Mixed Integer Programming Problem
Publication: Research - peer-review › Article in proceedings – Annual report year: 2009
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 | 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 |
| State | Published |
Conference
| Conference | 12th IMA International Conference on Cryptography and Coding |
|---|---|
| Period | 01-01-09 → … |
| Name | Lecture Notes of Computer Science |
|---|---|
| Number | 5921 |
| ISSN (Print) | 0302-9743 |
ID: 4032014