Mixed-integer Linear Programming in the Analysis of Trivium and Ktantan

Julia Borghoff

Paper 2012/676

Mixed-integer Linear Programming in the Analysis of Trivium and Ktantan

Julia Borghoff

Abstract

In this paper we present a rather new approach to apply mixed-integer optimization to the cryptanalysis of cryptographic primitives. We focus on the stream cipher Trivium, that has been recommended by the eSTREAM stream cipher project, and the lightweight block cipher Ktantan. Using these examples we explain how the problem of solving a non-linear multivariate Boolean equation system can be formulated as a mixed-integer linear programming problem. Our main focus is the formulation of the mixed-integer programming model (MIP model), which includes amongst others the choice of a conversion method to convert the Boolean equations into equations over the reals, different guessing strategies and the selection of binary variables. We apply the commercial solver Cplex to our problems. The results and further possible features of the approach are discussed.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: mixed-integer programming Trivium Ktantan
Contact author(s): j borghoff @ mat dtu dk
History: 2012-11-30: received
Short URL: https://ia.cr/2012/676
License: CC BY

BibTeX

@misc{cryptoeprint:2012/676,
      author = {Julia Borghoff},
      title = {Mixed-integer Linear Programming in the Analysis of Trivium and Ktantan},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/676},
      year = {2012},
      url = {https://eprint.iacr.org/2012/676}
}