Mixed Integer Programming Models for Finite Automaton and Its Application to Additive Differential Patterns of Exclusive-Or

Siwei Sun; Lei Hu; Peng Wang; Meiqin Wang; Danping Shi; Xiaoshuang Ma; Qianqian Yang; Kai Fu

Paper 2016/338

Mixed Integer Programming Models for Finite Automaton and Its Application to Additive Differential Patterns of Exclusive-Or

Siwei Sun, Lei Hu, Peng Wang, Meiqin Wang, Danping Shi, Xiaoshuang Ma, Qianqian Yang, and Kai Fu

Abstract

Inspired by Fu et al. work on modeling the exclusive-or differential property of the modulo addition as an mixed-integer programming problem, we propose a method with which any finite automaton can be formulated as an mixed-integer programming model. Using this method, we show how to construct a mixed integer programming model whose feasible region is the set of all differential patterns $(\alpha, \beta, \gamma)$'s, such that ${\rm adp}^\oplus(\alpha, \beta \rightarrow \gamma) = {\rm Pr}_{x,y}[((x + \alpha) \oplus (y + \beta))-(x \oplus y) = \gamma] > 0$. We expect that this may be useful in automatic differential analysis with additive difference.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Finite automaton ARX cipher Modulo addition Exclusive-or Additive differential Integer programming Automatic cryptanalysis
Contact author(s): sunsiwei @ iie ac cn
History: 2016-03-30: received
Short URL: https://ia.cr/2016/338
License: CC BY

BibTeX

@misc{cryptoeprint:2016/338,
      author = {Siwei Sun and Lei Hu and Peng Wang and Meiqin Wang and Danping Shi and Xiaoshuang Ma and Qianqian Yang and Kai Fu},
      title = {Mixed Integer Programming Models for Finite Automaton and Its Application to Additive Differential Patterns of Exclusive-Or},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/338},
      year = {2016},
      url = {https://eprint.iacr.org/2016/338}
}