[Resource Topic] 2015/122: Constructing Mixed-integer Programming Models whose Feasible Region is Exactly the Set of All Valid Differential Characteristics of SIMON

Welcome to the resource topic for 2015/122

Title:
Constructing Mixed-integer Programming Models whose Feasible Region is Exactly the Set of All Valid Differential Characteristics of SIMON

Authors: Siwei Sun, Lei Hu, Meiqin Wang, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Danping Shi, Ling Song, Kai Fu

Abstract:

In IACR ePrint 2014/747, a method for constructing mixed-integer linear programming (MILP) models whose feasible regions are exactly the sets of all possible differential (or linear) characteristics for a wide range of block ciphers is presented. These models can be used to search for or enumerate differential and linear characteristics of a block cipher automatically. However, for the case of SIMON (a lightweight block cipher designed by the U.S. National Security Agency), the method proposed in IACR ePrint 2014/747 is not {\it exact} anymore. That is, the feasible region of the MILP model constructed for SIMON contains invalid differential characteristics due to the dependent input bits of the AND operations, and these invalid characteristics must be filtered out by other methods. This is a very inconvenient process and reduces the level of automation of the framework of MILP-based automatic differential analysis. In this paper, by using quadratic constraints or constraints from the H-representation of a specific convex hull, we give a method for constructing mixed-integer (non)linear programming models whose feasible regions are exactly the sets of all valid differential characteristics for SIMON. The technique presented in this paper may be also useful for other ciphers. How to construct an MILP model whose feasible region is exactly the set of all linear characteristics of SIMON is still an open problem.

ePrint: https://eprint.iacr.org/2015/122

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .