On the distribution of characteristics in bijective mappings

✍ Scribed by Luke O'Connor

• Publisher: Springer
• Year: 2004
• Tongue: English
• Weight: 915 KB
• Volume: 8
• Category: Article
• ISSN: 0933-2790
• DOI: 10.1007/bf00190756

✦ Synopsis

Differential cryptanalysis is a method of attacking iterated mappings based on differences known as characteristics. The probability of a given characteristic is derived from the XOR tables associated with the iterated mapping. If ~-is a mapping ~r: Z~ --, Z~", then for each AX, AY ~ Z~ the XOR table for ~r gives the number of input pairs of difference AX = X + X' for which ~r(X) + Ir(X') = AY.

The complexity of a differential attack depends upon two properties of the XOR tables: the density of zero entries in the table, and the size of the largest entry in the table. In this paper we present the first results on the expected values of these properties for a general class of mappings ~r. We prove that if 7r: Z~' ~ Z~' is a bijective mapping, then the expected size of the largest entry in the XOR table for ~r is bounded by 2m, while the fraction of the XOR table that is zero approaches e-1/2 = 0.60653. We are then able to demonstrate that there are easily constructed classes of iterated mappings for which the probability of a differential-like attack succeeding is very small.