Differential equations of addition

From Wikipedia, the free encyclopedia

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 232 and addition over GF(2)) and where input and output differences are expressed as XORs.

Examples of Differential Equations of Addition

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

where and are -bit unknown variables and , and are known variables. The symbols and denote addition modulo and bitwise exclusive-or respectively. The above equation is denoted by .

Let a set is an integer less than denote a system of DEA where is a polynomial in . 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 and is assumed known. Essentially, the special DEA can be represented as . Based on the found properties, a algorithm for deriving was proposed and analyzed.[1]

Usage of Differential Equations of Addition

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 Helix.


  • Souradyuti Paul and Bart Preneel, Solving Systems of Differential Equations of Addition, ACISP 2005. Full version (PDF)
  • Souradyuti Paul and Bart Preneel, Near Optimal Algorithms for Solving Differential Equations of Addition With Batch Queries, Indocrypt 2005. Full version (PDF)
  • Helger Lipmaa, Johan Wallén, Philippe Dumas: On the Additive Differential Probability of Exclusive-Or. FSE 2004: 317-331.
    • ^ Li, Chengqing; Liu, Yuansheng; Zhang, Leo Yu; Chen, Michael Z. Q. (2013-04-01). "Breaking a chaotic image encryption algorithm based on modulo addition and xor operation". International Journal of Bifurcation and Chaos. 23 (04): 1350075. ISSN 0218-1274. doi:10.1142/S0218127413500752. 
    Retrieved from "https://en.wikipedia.org/w/index.php?title=Differential_equations_of_addition&oldid=742853197"
    This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Differential_equations_of_addition
    This page is based on the copyrighted Wikipedia article "Differential equations of addition"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA