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 programmingTriviumKtantan
Contact author(s)
j borghoff @ mat dtu dk
History
2012-11-30: received
Short URL
https://ia.cr/2012/676
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2012/676}},
      url = {https://eprint.iacr.org/2012/676}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.