Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
Measuring the number of rounds a full diffusion takes is common. –  CodesInChaos Feb 12 '13 at 17:45

1 Answer 1

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).

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.