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

Category / Keywords: Finite automaton, ARX cipher, Modulo addition, Exclusive-or, Additive differential, Integer programming, Automatic cryptanalysis

Date: received 27 Mar 2016, last revised 27 Mar 2016

Contact author: sunsiwei at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20160330:105858 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]