A New MILP Model for Matrix Multiplications with Applications to KLEIN and PRINCE

Date

2021-01-01

Author

İlter, Murat Burhan
Selçuk, Ali Aydın

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

302
views

0
downloads

Mixed integer linear programming (MILP) models are applied extensively in the field of cryptanalysis. Finding the minimum number of active S-boxes and the best differential characteristic in a differential attack are two main problems examined using the MILP approach. In this study, KLEIN and PRINCE block ciphers are modeled with MILP to search for an exact solution to these problems. Both ciphers contain matrix multiplication operations, which can be calculated using multiple xor operations. The standard MILP model for multiple xors increases the number of variables significantly, which extends the solution time. In this work, an alternative xor model is proposed using fewer variables than the standard xor model. The new model is much more efficient in terms of the number of variables involved and the execution time. Using the new model, we analyze the differential properties of KLEIN and PRINCE. We obtain the exact minimum number of active S-boxes of these ciphers with full rounds and also discover the best differential characteristics for various numbers of rounds. For KLEIN and PRINCE ciphers we achieve the best single differential characteristic of probability 2(-56). These results improve the best single-key differential attacks on these ciphers in the literature.

Subject Keywords

MILP, Cryptanalysis, Differential Cryptanalysis, Optimization, AUTOMATIC SECURITY EVALUATION

URI

https://hdl.handle.net/11511/94812

DOI

https://doi.org/10.5220/0010519504200427

Conference Name

18th International Conference on Security and Cryptography (SECRYPT)

Collections

Graduate School of Applied Mathematics, Conference / Seminar

Suggestions

OpenMETU
Core

An interactive algorithm for multiobjective ranking for underlying linear and quasiconcave value functions TEZCANER ÖZTÜRK, DİCLEHAN; Köksalan, Mustafa Murat (Wiley, 2019-07-29) We develop interactive algorithms to find a strict total order for a set of discrete alternatives for two different value functions: linear and quasiconcave. The algorithms first construct a preference matrix and then find a strict total order. Based on the ordering, they select a meaningful pair of alternatives to present the decision maker (DM) for comparison. We employ methods to find all implied preferences of the DM, after he or she makes a preference. Considering all the preferences of the DM, the pre...
A genetic algorithm for 2d shape optimization Chen, Wei Hang; Oral, Süha; Department of Mechanical Engineering (2008) In this study, an optimization code has been developed based on genetic algorithms associated with the finite element modeling for the shape optimization of plane stress problems. In genetic algorithms, constraints are mostly handled by using the concept of penalty functions, which penalize infeasible solutions by reducing their fitness values in proportion to the degrees of constraint violation. In this study, An Improved GA Penalty Scheme is used. The proposed method gives information about unfeasible ind...
A Meta-Heuristic Paradigm for solving the Forward Kinematics of 6-6 General Parallel Manipulator Chandra, Rohitash; Frean, Marcus; Rolland, Luc (2009-12-18) The forward kinematics of the general Gough platform, namely the 6-6 parallel manipulator is solved using hybrid meta-heuristic techniques in which the simulated annealing algorithm replaces the mutation operator in a genetic algorithm. The results are compared with the standard simulated annealing and genetic algorithm. It shows that the standard simulated annealing algorithm outperforms standard genetic algorithm in terms of computation time and overall accuracy of the solution on this problem. However, t...
A new multiobjective simulated annealing algorithm Tekinalp, Ozan (Springer Science and Business Media LLC, 2007-09-01) A new multiobjective simulated annealing algorithm for continuous optimization problems is presented. The algorithm has an adaptive cooling schedule and uses a population of fitness functions to accurately generate the Pareto front. Whenever an improvement with a fitness function is encountered, the trial point is accepted, and the temperature parameters associated with the improving fitness functions are cooled. Beside well known linear fitness functions, special elliptic and ellipsoidal fitness functions,...
An improved method for inference of piecewise linear systems by detecting jumps using derivative estimation Selcuk, A. M.; Öktem, Hüseyin Avni (Elsevier BV, 2009-08-01) Inference of dynamical systems using piecewise linear models is a promising active research area. Most of the investigations in this field have been stimulated by the research in functional genomics. In this article we study the inference problem in piecewise linear systems. We propose first identifying the state transitions by detecting the jumps of the derivative estimates, then finding the guard conditions of the state transitions (thresholds) from the values of the state variables at the state transitio...

Citation Formats

M. B. İlter and A. A. Selçuk, “A New MILP Model for Matrix Multiplications with Applications to KLEIN and PRINCE,” presented at the 18th International Conference on Security and Cryptography (SECRYPT), ELECTR NETWORK, 2021, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/94812.