Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / mixed-integer programming, Trivium, Ktantan

Date: received 29 Nov 2012

Contact author: j borghoff at mat dtu dk

Available format(s): PDF | BibTeX Citation

Version: 20121130:150732 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]