With optimal diffusion the change of a single input bit should change every single output bit equally likely with a chance of 50% each (in mean).
But this does not necessarily mean it makes it unpredictable. For example it could underlie a mathematical formula similar to the S-Box in AES.
Given this a formula could be computed which summarize the $n$ times appliance of a certain (block-cipher) encryption scheme and with this makes the computation much faster.

Does a 'good diffusion' also includes the unavailability of such a summarizing function?
If not has this property another name?
Can the unavailability be proofed or tested in some way?

Bonus questions:
Is there some $n$-bit diffusion algorithm which can not be simplified among $n$ times appliance?

Here some self-made algorithm based on AES allowing appliance for even $n$ bits.
How likely such summarizing function does not exits?

  • I) SubBytes(): Same as in AES but as we might end up with 2,4,6 bits at the very end it starts over with the first 6,4,2 bits. After 4 passed we are guaranteed to end at the last bit. To add some variability for the complete byte case we XOR the current byte with the next byte before applying it. One byte further away for each pass (1-4).
  • II) ShiftRows() (Part1): No matrix possible. Therefore we split the $n$-bytes in half placing the 1st part below the 2nd part. In each cycle we bit-shift the lower part one bit more. (or better 0,1,2,4,8,.. or Fibonacci numbers? )
  • III) MixColumns(): No matrix multiplication possible (or can it?). Instead we use the $2 \times (\frac{n}{2})$ from II) and apply some operation on each 2-bit collum. Alternating $+1$, $\cdot 3$ both $\bmod 4$
  • IV) ShiftRows() (Part2): merge the two rows with first bit from top, 2nd from bottom, top, bottom, t,b,t, and so on
  • V) AddRoundKey(): No key added here. It's just about diffusion and making summarizing $n$-times appliance impossible.

Cycle gets repeated $\lceil \frac{n}{8} \rceil$ times.
Not tested yet but it should make each input bit have an impact on each output bit. Let's assume that's the case.

Has the missing matrix multiplication, and round key negative impact on diffusion or summarizing?
How likely it can't be summarizing across multiple steps (as a much quicker computation)?

(hints about what can be changed, added or removed are also welcome. Here only as bonus question, maybe some new thread is needed)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.