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 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:

(x+y)\oplus((x\oplus a)+(y\oplus b))=c

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

Let a set S = {(ai,bi,ci) | 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


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


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.