cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...

, differential equations of addition (DEA) are one of the most basic equations related to

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 information input can a ...

that mix additions over two different groups (e.g. addition modulo 2³² 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:

(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''

2^n

and ''bitwise exclusive-or'' respectively. The above equation is denoted by

(a, b, c)

. Let a set

S=\

for integer

i

denote a system of

k(n)

DEA where

k(n)

is a polynomial in

n

. It has been proved that the satisfiability of an arbitrary set of DEA is in the

complexity class P In computational complexity theory, P, also known as PTIME or DTIME(''n''O(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, ...

when a brute force search requires an

exponential time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

. In 2013, some properties of a special form of DEA were reported by Chengqing Li et al., where

a=0

and

y

is assumed known. Essentially, the special DEA can be represented as

(x \dotplus \alpha) \oplus (x\dotplus \beta)=c

. Based on the found properties, an algorithm for deriving

x

was proposed and analyzed.

Applications

Solution to an arbitrary set of DEA (either in batch and or in adaptive query model) was due to

Souradyuti Paul Souradyuti Paul (born 1976) is an Indian cryptologist. Formerly a member of COSIC, he is currently working as an associate professor at Indian Institute of Technology Bhilai and a Guest Researcher for the National Institute of Standards and Tec ...

and

Bart Preneel Bart Preneel (born 15 October 1963 in Leuven, Belgium) is a Belgium, Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group. He was the president of the International Association for Crypt ...

. The solution techniques have been used to attack the stream cipher

Helix A helix (; ) is a shape like a cylindrical coil spring or the thread of a machine screw. It is a type of smooth space curve with tangent lines at a constant angle to a fixed axis. Helices are important in biology, as the DNA molecule is for ...

References

{{Cryptography navbox , block Cryptographic attacks Theory of cryptography Ciphers

Examples

Applications

Further reading

References