[Cryptography] If diffusion is perfect how much confusion do you really need?

[Jonathan Katz]

On Mon, Jun 1, 2015 at 4:05 PM, Ray Dillinger <bear at sonic.net> wrote:
> (warning: cipher design post)
>
> Let's say, in theory, that I have a "perfect" diffusion mechanism
> that can be defined for blocks of many different sizes.  I'm denoting
> it as a "D-box."  I think that I may ACTUALLY have one (defined
> using modular multiplication and some bit-slicing), but right now
> I'm not asking whether mine is actually a perfect D-box; I'm asking
> what the value of a perfect D-box would be.
>
> If I send a block of data through a D-box, the result is an output
> the same size as the block, in which every bit of input has an
> absolutely equal and nonlinear influence on every bit of the
> output.  Flip any nonempty subset of input bits, and roughly half
> of the output bits will change.
>
> But this mechanism which provides perfect diffusion, provides no
> confusion whatsoever.  Like P-boxes, it is trivially reversible,
> and anyone given the whole set of output bits can easily derive
> all the input bits. I'll denote the reversed D-box as a "Xob-d".
>
> Now, I believe, but could be wrong here, that if you have such a
> "perfect" diffusion mechanism, you need very little confusion to
> create a secure cipher.
>
> in catenative notation, using no S-boxes whatsoever and xor as
> a trivial, reversible method of combining message with key, I
> can't think of a single attack that applies to this utterly
> simple, fast, three-and-a-half round construction:
>
> M > ^key | D-box | ^key | D-box | ^key | D-box | ^key = C
>
> And the decryption is in fact the very same operation using the
> reversed D-boxes:
>
> C > ^key | Xob-d | ^key | Xob-d | ^key | Xob-d | ^key = M

One round of your construction is the Even-Mansour cipher, which can
indeed be proven secure. Multi-round versions have also been analyzed
more recently.