[Cryptography] Bent, crooked, and twisted functions

[Pierre Abbat]

A bent function is a Boolean function whose Hadamard transform is flat. 
Wikipedia has an article about bent functions, including a construction for 
all even orders. Bent functions satisfy the SAC for any positive number of 
changed bits.

Bent functions have a couple of problems when used for S-boxes:
* Bent functions exist only in even orders. You can't make a bent function 
which takes three or seven bits as input.
* Bent functions aren't balanced. For some kinds of ciphers, you want S-boxes 
which are permutations (invertible functions), which are balanced (the output 
has as many one-bits as zero-bits).

A crooked function is a vectorial Boolean function whose derivative, for any 
nonzero difference, takes as many different values as possible. Crooked 
functions exist for both odd and even orders, and they can be permutations. I 
did some web searching, but did not find an example of a crooked function.

I define a twisted function as follows: A twisted function is a vectorial 
Boolean function whose input and output have the same size, consisting of 
these steps:
1. Exclusive-or the input with a constant.
2. Apply a constant permutation to the bits.
3. Rotate the bit vector by its population count.
4. Apply a constant permutation to the bits.
5. Exclusive-or the output with a constant.

Twisted functions of order at least 3 satisfy the SAC for single bit flips, but 
not double bit flips. (All 24 permutations of order 2 are linear.) They are 
permutations and either preserve or invert the parity. The simplest nonlinear 
twisted function is [0,2,4,5,1,6,3,7]. It is not a crooked function, as when 
the difference has two bits (3, 5, or 6), there are only two different values of 
the derivative.

I wrote this code to calculate what degrees have nonzero coefficients in the 
expansion of a vectorial Boolean function:

"""
    powerTransform(buf::OffsetVector{<:Integer})

Takes a vector Boolean function and transforms it so that the constant term
is in [0], the linear terms are in [1],[2],[4],[8],..., the quadratic terms
are in [3],[5],[6],[9],[10],[12],..., and so on. I don't know what this is
called. It seems to be a variant of the pseudo-Hadamard transform.
"""
function powerTransform(buf::OffsetVector{<:Integer})
  tmp0=copy(buf)
  tmp1=copy(buf)
  sz=length(buf)
  h=sz÷2
  if ispow2(sz) && Origin(buf)==Origin((0,))
    while h>0
      for i in 0:sz-1
	j=i⊻h
	if i>j
	  @inbounds tmp1[i]=tmp0[j]⊻tmp0[i]
	else
	  @inbounds tmp1[i]=tmp0[i]
	end
      end
      tmp0,tmp1=tmp1,tmp0
      h÷=2
    end
  end
  tmp0
end

function powerSpectrum(buf::OffsetVector{<:Integer})
  # "power" means exponentiation, not energy per time.
  spectrum=OffsetVector(fill(0,count_ones(length(buf)-1)+1),-1)
  pt=powerTransform(buf)
  for i in eachindex(pt)
    if pt[i]!=0
      spectrum[count_ones(i)]+=1
    end
  end
  spectrum
end

nonlinearity(buf)=sum(powerSpectrum(buf)[2:end])

Here's what it says for bent functions of orders 4 and 6:

julia> powerSpectrum(OffsetVector([0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0],-1))
5-element OffsetArray(::Vector{Int64}, 0:4) with eltype Int64 with indices 0:4:
 0
 0
 2
 0
 0

julia> 
powerSpectrum(OffsetVector([0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,1],-1))
7-element OffsetArray(::Vector{Int64}, 0:6) with eltype Int64 with indices 0:6:
 0
 0
 3
 0
 0
 0
 0

They are entirely quadratic. And for the simplest twisted function:

julia> powerSpectrum(OffsetVector([0,2,4,5,1,6,3,7],-1))
4-element OffsetArray(::Vector{Int64}, 0:3) with eltype Int64 with indices 0:3:
 0
 3
 3
 0

The Daphne S-box is an order-8 twisted function:

julia> powerSpectrum(DaphneCipher.sbox)
9-element OffsetArray(::Vector{Int64}, 0:8) with eltype Int64 with indices 0:8:
  1
  8
 27
 56
 67
 56
 23
  8
  0

The last term is always 0 for a permutation, because it's the count of all the 
only 1 exclusive-or of all the outputs of the function (except for order 1).

Pierre
-- 
lo ponse be lo mruli ku po'o cu ga'ezga roda lo ka dinko