[Cryptography] Bent, crooked, and twisted functions

[Pierre Abbat]

On Wednesday, September 24, 2025 2:22:13 AM EDT Ferecides de Siros via 
cryptography wrote:
> **Your 4-bit results:** Interesting that the canonical twisted function
> shows different patterns than the 3-bit version. The [3,3,3,3,3,2,3]
> pattern suggests consistent but imperfect nonlinearity.

[3,3,3,3,3,2,3] turned out to be from the Rust code passing 3 as the order to 
the function regardless of how long the vector is. The actual derivative 
counts are [4, 4, 4, 4, 3, 4, 4, 4, 4, 3, 4, 4, 4, 4, 3].

I thought the derivative counts were going to alternate between two values 
according to the parity of the difference, that is, in a Thue-Morse sequence, 
but they don't. The result for order 5 is [16, 16, 8, 16, 9, 8, 13, 16, 9, 9, 
12, 8, 12, 13, 10, 16, 8, 9, 13, 9, 12, 12, 10, 8, 13, 12, 10, 13, 10, 10, 
11].

As far as I can tell, the maximum number of derivative values is attained when 
the order is odd; when it's even, the derivative takes at most half that many 
values. Since the derivative counts are irregular, I think I should take the 
harmonic mean of them as a measure of nonlinearity.

The algorithm is quadratic. Can you think of a faster way to count the 
derivatives for higher orders, such as 16, 32, or 16384, assuming that the 
function is a twisted function without bit permutation?

Twisted functions preserve or invert parity. They should therefore be combined 
with functions that mess up parity. In Daphne, the two multiplications mess up 
parity; in Wring and Twistree, where the rotbitcount step is a twisted 
function on the entire message or block, the S-boxes and mix3 mess up the 
parity.

Pierre
-- 
gau do li'i co'e kei do