# Re: Almost perfect nonlinear permutations

*From*: jdm <james.d.mclaughlin@xxxxxxxxx>*Date*: Thu, 16 Jun 2011 12:12:51 -0700 (PDT)

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.)

.

**Follow-Ups**:**Re: Almost perfect nonlinear permutations***From:*Tom St Denis

**References**:**Almost perfect nonlinear permutations***From:*jdm

**Re: Almost perfect nonlinear permutations***From:*Tom St Denis

**Re: Almost perfect nonlinear permutations***From:*jdm

**Re: Almost perfect nonlinear permutations***From:*Tom St Denis

**Re: Almost perfect nonlinear permutations***From:*jdm

**Re: Almost perfect nonlinear permutations***From:*Tom St Denis

- Prev by Date:
**Re: Almost perfect nonlinear permutations** - Next by Date:
**Re: The FBI wants your help - really !** - Previous by thread:
**Re: Almost perfect nonlinear permutations** - Next by thread:
**Re: Almost perfect nonlinear permutations** - Index(es):