Differential equations of addition
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.
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.
and Bart Preneel
. The solution techniques have been used to attack the stream cipher Helix
.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, differential equations of addition (DEA) are one of the most basic equations related to differential cryptanalysis
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
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.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 PaulSouradyuti Paul
Souradyuti Paul is an Indian cryptologist . Formerly a member of COSIC, he is currently working as a Guest Researcher for the National Institute of Standards and Technology in the United States...
and Bart Preneel
Bart Preneel
Bart Preneel is a Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group, president of the International Association for Cryptologic Research, and project manager of ECRYPT....
. The solution techniques have been used to attack the stream cipher Helix
Phelix
Phelix is a high-speed stream cipher with a built-in single-pass message authentication code functionality, submitted in 2004 to the eSTREAM contest by Doug Whiting, Bruce Schneier, Stefan Lucks, and Frédéric Muller. The cipher uses only the operations of addition modulo 232, exclusive or, and...
.