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

[edit] Examples of Differential Equations of Addition

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

where x and y are n-bit unknown variables and a, b and c are known variables. The symbols + and denote addition modulo 2ⁿ and bitwise exclusive-or 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.

[edit] 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.

[edit] 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 Exclusive-Or. FSE 2004: 317-331.

v • d • e   Block ciphers Common algorithms: AES | Blowfish | DES | Triple DES | Serpent | Twofish Other algorithms: 3-Way | ABC | Akelarre | Anubis | ARIA | BaseKing | BassOmatic | BATON | BEAR and LION | C2 | Camellia | CAST-128 | CAST-256 | CIKS-1 | CIPHERUNICORN-A | CIPHERUNICORN-E | CLEFIA | CMEA | Cobra | COCONUT98 | Crab | CRYPTON | CS-Cipher | DEAL | DES-X | DFC | E2 | FEAL | FEA-M | FROG | G-DES | GOST | Grand Cru | Hasty Pudding Cipher | Hierocrypt | ICE | IDEA | IDEA NXT | Intel Cascade Cipher | Iraqi | KASUMI | KeeLoq | KHAZAD | Khufu and Khafre | KN-Cipher | Ladder-DES | Libelle | LOKI97 | LOKI89/91 | Lucifer | M6 | M8 | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MULTI2 | MultiSwap | New Data Seal | NewDES | Nimbus | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SAVILLE | SC2000 | SEED | SHACAL | SHARK | Skipjack | SMS4 | Spectr-H64 | Square | SXAL/MBAL | TEA | Treyfer | UES | Xenon | xmx | XTEA | XXTEA | Zodiac Design: Feistel network | Key schedule | Product cipher | S-box | SPN Attacks: Brute force | Linear / Differential / Integral cryptanalysis | Mod n | Related-key | Slide | XSL Standardization: AES process | CRYPTREC | NESSIE Misc: Avalanche effect | Block size | IV | Key size | Modes of operation | Piling-up lemma | Weak key v • d • e   Cryptography History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers | Steganography