[Cryptography] Bent, crooked, and twisted functions

[Ray Dillinger]

On 10/5/25 10:10 PM, Pierre Abbat wrote:
> Here's the graph. The three averages cluster together and oscillate between
> 0.4 for even order and 0.6 for odd order. I think that, for an easily
> constructible nonlinear function, that's pretty good.
>
> Pierre


It really is. This is important.  It looks like you've found a very 
general tool.

I think it's of the same importance and generality as fundamentals like 
the Feistel construction for block ciphers. Releasing it to the public 
domain, instead of filing a patent, is a significant contribution 
and very generous.

What you've got here is a general construction tool for good nonlinear 
transformations. This is practically a self-contained method for 
spitting out optimal or near-optimal S-boxes for ciphers that repeatedly 
apply S-boxes.  And it outputs a nonlinear transformation that is in 
itself a nonlinear transformation of some input - such as a cipher key.  
So it can be applied in a lot of interesting ways while still enabling 
some guarantees about the result.

Probably even more important than that, it gives a good way to analyze 
and quantify the nonlinearity of transformations, which we've had fairly 
poor metrics for until now.

     Bear