Score:1

Diffusion of arithmetic and bit operations

tf flag
Tom

I want to estimate when and wether different types of functions provide full or partial diffusion.

I'm trying to understand diffusion of basic operations, like:

  • addtion,
  • multiplication,
  • xoring.

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a+b \mod n = c$

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a \oplus b \mod n = c$

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a \cdot b \mod n = c$

And what if we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$(a >> 1) \cdot b \mod n = c$

Is it fairly easy to deduce or do I have to write a program to check it?

In xor case only one bit would be changed if we compute it for $a$ differing by one bit. But what with other cases? I think in case of $a >> 1$ nearly half of the bits will be changed, because if we switch two bits that way, we have about 50% probability that they would be the same or not. So simple $a >> 1$ could provide good diffusion (if we combine it with other mixing operations, just repeating this operation over and over, of course, makes no sense).

EDIT:

Let's consider $n$ equal to power of $2$.

Maarten Bodewes avatar
in flag
What kind of $n$ would that be? I think you forgot to copy that part of the assignment.
Tom avatar
tf flag
Tom
@MaartenBodewes I think you are right. I thought about n equal to power of two.
Score:1
cn flag
Leo

You can visually inspect the diffusion of different operations using an avalanche diagram.

I've generated the avalanche diagrams of these operations, the sizes I used for $a$ and $b$ are 64 bits. The result is also a 64-bit variable.

The tool I use generates the diagrams for all bit changes instead of just $a$, but it should still be informative.

Diffusion of $a \oplus b$

As you guessed; with plain XOR, the output bit $c_n$ is only affected by input bits $a_n$ and $b_n$. Here's what that looks like.

Avalanche diagram of XOR

Diffusion of $a + b$

A slight improvement is addition. You can see that instead of each bit only affecting itself, there is now a very slight diffusion around the bits.

Avalanche diagram of addition

Diffusion of $a \cdot b$

Multiplication provides a massive improvement. But multiplication only diffuses changes in one direction. And depending on the processor you are targeting, multiplications might be expensive or not constant time.

Avalanche diagram of multiplication

Diffusion by repeating simple mixers

If you take a bunch of invertible operations that somewhat diffuse the changes, and repetitively perform them, you can get much better results.

Below is an example with just XOR-shifts and add-shifts.

Avalanche diagram of repetition

Here's the operations that are being performed. As you can see, individually none of those diffuse that much, but if you repeat them enough, the mixing is much better.

for (size_t i = 0; i < 4; i++) {
    // Mix a
    a ^= a >> 7;
    a += a << 13;
    a ^= a >> 9;

    // Mix b
    b ^= b >> 7;
    b += b << 13;
    b ^= b >> 9;

    // Shift a and b into each other
    u64 a_old = a;
    u64 b_old = b;
    a = (a_old << 8) | ((b_old >> 56) & 0xFF);
    b = (b_old << 8) | ((a_old >> 56) & 0xFF);

}

u64 c = a ^ b;
Tom avatar
tf flag
Tom
Ok, I have many questions. 1. Did you make this diagrams in some program or generate it in c++ with some graphic library? What is the name of it? 2. Authors of Skein wrote about full diffusion, is it possible to get 100% diffusion? I thought about (a >> 1) * b. It could achieve full diffusion after 64 iterations, istn't it?
Tom avatar
tf flag
Tom
3. It seems like this diffusions don't add to each other. I wanted to do thought experiment and calculate diffusion of n multiplications (e.g. by adding toegether n times diffusions of single multiplication), but of course some bits may remain unchanged, especially if low input bits would be all zeros. So to increase diffusion we have "move" green bits into black bits positions - somehow, by bit shifts or arithmetic operations. So it is hard to caclulate analytically final result. Can I use this method for scientific purposes, to estimate diffusion of some algorithm (is this accepted method)?
Tom avatar
tf flag
Tom
4. It looks like in last diagram all pixels are green, but some are lighter. How to interpret that? Does it shows some bits are mixed less often?
Tom avatar
tf flag
Tom
@kelalaka diagrams are wrong?
kelalaka avatar
in flag
Ok, the figures are confusing. X-or is fine, however, modular or not, addition can effect more than one bit and that is really depend on the size of modulus $n$ where it seems $2ˆ{64}$
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.