# Measuring Shannon's diffusion

Shannon's idea of diffusion is fundamental to cryptography.

Besides being a descriptive idea, is there any work on measuring or expressing it? Saying something like "System A has more diffusion than B" or "The information in bit x is diffused 1/3 into bit y, 1/3 into bit z, and the remaining third among 11 more bits".

Is there a way to evaluate the diffusion of a transform? XOR does no diffusion, Add with carry does small diffusion, and a permutation may do a lot of diffusion.

In short: Diffusion is a great idea - how can we approach it mathematically?

UPDATE: For instance, we should be able to quantify the diffusion done by adding with carry. This breaks both of the suggested answers: Adding may update the value of every bit. Modifying one bit of the input may modify several bits of the output. But adding still doesn't diffuse very well.

-
Measuring the number of rounds a full diffusion takes is common. – CodesInChaos Feb 12 '13 at 17:45

## 1 Answer

One way is to look at how many bits of the outputs are modified if you modify, say $t$ bits in the input. Actually, a function from $\{0,1\}^n$ to $\{0,1\}^m$ such that modifying $t$ bits in input modifies $m-t+1$ bits of output is said to achieve perfect diffusion.

Examples of functions with good diffusion are those associated with MDS matrices. For instance, the permutation layer of the AES is made of one such function (it is the "mixcolumn" part of the algorithm).

-
It would be nice to disambiguate the definition or/and link to a reference. A small example could help. As is, we are left to guess if "modify $j$ bits" is to be taken as exactly $j$ bits, or has some statistical meaning as in other usages of diffusion; the range of $t$; and for which $(m,n)$ perfect diffusion can hold. – fgrieu Feb 13 '13 at 7:29