Differential equations of addition

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^{32} 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 x and y are nbit unknown variables and a, b and c are known variables. The symbols + and denote addition modulo 2^{n} and bitwise exclusiveor respectively. The above equation is denoted by (a,b,c).
Let a set S = {(a_{i},b_{i},c_{i})  i is an integer less than k} denote a system of k DEA where k is a polynomial in n. 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.
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.
References
 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 ExclusiveOr. FSE 2004: 317331.
Categories: Cryptographic attacks
 Theory of cryptography
 Ciphers
 Algebra
Wikimedia Foundation. 2010.
Look at other dictionaries:
Numerical ordinary differential equations — Illustration of numerical integration for the differential equation y = y,y(0) = 1. Blue: the Euler method, green: the midpoint method, red: the exact solution, y = et. The step size is h = 1.0 … Wikipedia
Differential geometry of surfaces — Carl Friedrich Gauss in 1828 In mathematics, the differential geometry of surfaces deals with smooth surfaces with various additional structures, most often, a Riemannian metric. Surfaces have been extensively studied from various perspectives:… … Wikipedia
Differential geometry — A triangle immersed in a saddle shape plane (a hyperbolic paraboloid), as well as two diverging ultraparallel lines. Differential geometry is a mathematical discipline that uses the techniques of differential and integral calculus, as well as… … Wikipedia
Differential algebra — In mathematics, differential rings, differential fields, and differential algebras are rings, fields, and algebras equipped with a derivation, which is a unary function that is linear and satisfies the Leibniz product law. A natural example of a… … Wikipedia
Équations — Équation (mathématiques) Cet article concerne les équations mathématiques dans leur généralité. Pour une introduction au concept, voir Équation (mathématiques élémentaires). … Wikipédia en Français
Addition — is the mathematical process of putting things together. The plus sign + means that two numbers are added together. For example, in the picture on the right, there are 3 + 2 apples meaning three apples and two other apples which is the same as… … Wikipedia
Maxwell's equations — For thermodynamic relations, see Maxwell relations. Electromagnetism … Wikipedia
Matrix differential equation — A differential equation is a mathematical equation for an unknown function of one or several variables that relates the values of the function itself and of its derivatives of various orders. A matrix differential equation is one containing more… … Wikipedia
Digital differential analyzer — This article is about the digital implementation of a Differential Analyzer. For other uses of DDA, see DDA. For the graphics algorithm, see Digital Differential Analyzer (graphics algorithm). A digital differential analyzer (DDA), also sometimes … Wikipedia
Derivation of the Navier–Stokes equations — The intent of this article is to highlight the important points of the derivation of the Navier–Stokes equations as well as the application and formulation for different families of fluids. Contents 1 Basic assumptions 2 The material derivative 3 … Wikipedia