View source for Differential equations of addition

{{Short description|Equations in differential cryptanalysis}}
In [[cryptography]], '''differential equations of addition''' (DEA) are one of the most basic equations related to [[differential cryptanalysis]] that mix additions over two different groups (e.g. addition modulo 2<sup>32</sup> and addition over GF(2)) and  where input and output differences are expressed as XORs.

== Examples ==
'''Differential equations of addition''' (DEA) are of the following form:

<math>(x+y)\oplus((x\oplus a)+(y\oplus b))=c</math>

where <math>x</math> and <math>y</math> are <math>n</math>-bit '''unknown''' variables and <math>a</math>, <math>b</math> and <math>c</math> are '''known''' variables. The symbols <math>+</math> and <math>\oplus</math> denote ''addition modulo'' <math>2^n</math> and ''bitwise exclusive-or'' respectively. The above equation is denoted by <math>(a, b, c)</math>.

Let a set 

<math>S=\{(a_i, b_i, c_i)|i < k\}</math> 

for integer <math>i</math> denote a system of <math>k(n)</math> '''DEA''' where <math>k(n)</math> is a polynomial in <math>n</math>. It has been proved that the satisfiability of an arbitrary set of DEA is in the [[complexity class P]] when a brute force search requires an [[exponential time]]. 

In 2013, some properties of a special form of DEA were reported by Chengqing Li et al., where <math>a=0</math> and <math>y</math> is assumed known. Essentially, the special DEA can be represented as <math>(x \dotplus \alpha) \oplus (x\dotplus \beta)=c</math>. Based on the found properties, an algorithm for deriving <math>x</math> was proposed and analyzed.<ref>{{Cite journal|last1=Li|first1=Chengqing|last2=Liu|first2=Yuansheng|last3=Zhang|first3=Leo Yu|last4=Chen|first4=Michael Z. Q.|date=2013-04-01|title=Breaking a chaotic image encryption algorithm based on modulo addition and xor operation|journal=International Journal of Bifurcation and Chaos|volume=23|issue=4|pages=1350075|doi=10.1142/S0218127413500752|issn=0218-1274|arxiv=1207.6536|bibcode=2013IJBC...2350075L|s2cid=15990771 }}</ref>

== Applications ==
Solution to an arbitrary set of DEA (either in batch and or in adaptive query model) was due to [[Souradyuti Paul]] and [[Bart Preneel]]. The solution techniques have been used to attack the stream cipher [[Phelix|Helix]].

== Further reading ==
* [[Souradyuti Paul]] and [[Bart Preneel]], Solving Systems of Differential Equations of Addition, ACISP 2005.  [http://www.cosic.esat.kuleuven.be/publications/article-566.pdf Full version] ([[PDF]])
* [[Souradyuti Paul]] and [[Bart Preneel]], Near Optimal Algorithms for Solving Differential Equations of Addition With Batch Queries, [[Indocrypt]] 2005.  [http://www.cosic.esat.kuleuven.be/publications/article-587.pdf Full version] ([[PDF]])
* Helger Lipmaa, Johan Wallén, Philippe Dumas: On the Additive Differential Probability of Exclusive-Or. [[Fast Software Encryption|FSE]] 2004: 317-331.

== References ==
<references />

{{Cryptography navbox | block}}

[[Category:Cryptographic attacks]]
[[Category:Theory of cryptography]]
[[Category:Ciphers]]