Re: Almost perfect nonlinear permutations



1.) I don't know what you mean by MKS-ing (although I suspect it to be
a reference to Mok Kong Shen).

2.) Let S be a 5x5 S-box mapping the first eight entries as follows:

INPUTS:     00000 00001 00010 00011 00100 00101 00110 00111 ...
OUTPUTS: 00000 00001 00010 00101 00100 00110 00111 00011 ...

If S does not map 01000 to 01000, we create a new S-box mapping 01000
to itself by applying a linear transform to the inputs, mapping 8 to
S^{-1}(8) but leaving invariant any input less than 8. The matrix
representing this linear transform will be identical to the identity
matrix in its third, fourth, and fifth columns, will have S^{-1}(8) as
its second column, and may have any value linearly independent of
these as its first column.

We obtain

INPUTS:     00000 00001 00010 00011 00100 00101 00110 00111 01000 ...
OUTPUTS: 00000 00001 00010 00101 00100 00110 00111 00011 01000 ...

(let this S-box be denoted T.)

If T maps 10000 to 10000, all well and good.

If T does not map 10000 to 10000, it may be the case that T^{-1}
(10000) is a value of the form 0abcd.

If this is the case, we will need to apply a linear transformation of
this form to the outputs:

1 0 0 0 0
u 1 0 0 0
v 0 1 0 0
w0 0 1 0 (If using a fixed-width font, put a space between w and
0)
x 0 0 0 1

Consider that the only values of the form 0abcd which could at this
point map to 10000 are the values 01001, 01010, ..., 01111. There are
seven such inputs, and sixteen outputs of the form 1****. Therefore,
at least nine values of the form 1**** are mapped to by inputs of the
form 1****. By choosing one of these nine output values, and choosing
the leftmost column of the matrix shown above to be equal to said
output value, applying the matrix will result in a situation where
T^{-1}(10000) >= 10000, without affecting any outputs of the form
0****

GIven a situartion where T^{-1}(10000) > 10000, we apply another
linear transformation of the form

1 0 0 0 0
u 1 0 0 0
v 0 1 0 0
w0 0 1 0 (Again, if using a fixed-width font, put a space
between the 0 and the w)
x 0 0 0 1

This time, we apply it to the inputs, and the leftmost column is T^{-1}
(10000)

We thus obtain a mapping of the form

INPUTS: 00000 00001 00010 00011 00100 00101 00110 00111 01000 ...
10000 ...
OUTPUTS: 00000 00001 00010 00101 00100 00110 00111 00011 01000 ...
10000 ...

My belief is that this mapping cannot be APN; and my inability to
prove this started this thread.

With regards to your statement that

"The upper n-m bits will be a linear combination of their input."

in this case, each of the upper two output bits y_i (0 <= i <= 1) will
have algebraic normal forms containing:

No constant term.
No linear terms except the corresponding x_i
An unknown number of degree 2 or higher monomials, each of which must
include at least one of x_0 and x_1.

I do not see anything implying that this "unknown number" is zero.

Finally, while I have never seen a 5x5 APN S-box such that the first
eight entries of the truth table comprised an APN bijection, this 5x5
APN S-box (CCZ-equivalent to the finite field inverse) is the closest
I've come:

INPUTS: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 30 31
OUTPUTS: 0 1 2 5 4 6 9 17 8 12 22 30 25 28 21 7 16 19 15 24
11 29 14 18 3 13 31 20 10 26 23 27

(spacing may be a bit off as browser is not using a fixed-width font.)
.