On 3-to-1 and Power APN S-Boxes - Sequences and Their Applications-SETA 2008 - page 385

=1+ x 1+ x 2 a 0 − 1
1+ x

+(1+ x ) k 0 x 2 s 0 1+( x 2 s 0 ) 2 a 1 − 1
1+ x 2 s 0

+ ···

+(1 + x ) k q − 2 x 2 s q − 2 1+( x 2 s q − 2 ) 2 a q − 1 − 1
1+ x 2 s q − 2

+(1+ x ) k q − 1 x 2 s q − 1 1+( x 2 s q − 1 ) 2 a q − 2
1+ x 2 s q − 1

+(1 + x ) k q − 1 x 2 s q − 1 (2 a q − 1) .

(1)

Opening (1 + x ) k q − 1 in the last term of Equation 1 to separate out x d

we have

2 a q − 1 − 2

(1 + x ) k q − 1 x 2 s q − 1 (2 a q − 1) = x d + x 2 s q − 1 (2 a q − 1) (1 + x ) k q − 2 x i 2 s q − 2

i =0

+ x 2 s q − 1 (2 a q − 1)+2 s q − 2 (2 a q − 1 − 1) (1 + x ) k q − 3 2 a q − 2 − 2 x i 2 s q − 3 +

···

i =0

2 a 0 − 2

+ x 2 s q − 1 (2 a q − 1)+ ··· +2 s 0 (2 a 1 − 1) x i

i =0

= x d + x l q 2 s q − 2 (1 + x ) k q − 2 1+( x 2 s q − 2 ) 2 a q − 1 − 1
1+ x 2 s q − 2

+ x l q − 1 2 s q − 3 (1 + x ) k q − 3 1+( x 2 s q − 3 ) 2 a q − 2 − 1
1+ x 2 s q − 3

+ x l 1 1+ x 2 a 0 − 1
1+ x

+ ··· . (2)

Now from Equations 1 and 2 we have
1+ x d +(1+ x ) d = x 1+ x 2 a 0 − 1
1+ x

+(1+ x ) k 0 x 2 s 0 1+( x 2 s 0 ) 2 a 1 − 1
1+ x 2 s 0

+ ···

+(1 + x ) k q − 2 x 2 s q − 2 1+( x 2 s q − 2 ) 2 a q − 1 − 1
1+ x 2 s q − 2

+(1+ x ) k q − 1 x 2 s q − 1 1+( x 2 s q − 1 ) 2 a q − 2
1+ x 2 s q − 1

+ x l q 2 s q − 2 (1 + x ) k q − 2 1+( x 2 s q − 2 ) 2 a q − 1 − 1
1+ x 2 s q − 2
+ x l q − 1 2 s q − 3 (1 + x ) k q − 3 1+( x 2 s q − 3 ) 2 a q − 2 − 1
1+ x 2 s q − 3

+ x l 1 1+ x 2 a 0 − 1
1+ x

+ ···

=( x + x l 1 ) 1+ x 2 a 0 − 1
1+ x

+(1+ x ) k 0 ( x 2 s 0 + x l 2 2 s 0 ) 1+( x 2 s 0 ) 2 a 1 − 1
1+ x 2 s 0

+ ···

+(1 + x ) k q − 2 ( x 2 s q − 2 + x l q 2 s q − 2 ) 1+( x 2 s q − 2 ) 2 a q − 1 − 1
1+ x 2 s q − 2

+(1 + x ) k q − 1 x 2 s q − 1 1+( x 2 s q − 1 ) 2 a q − 2
1+ x 2 s q − 1

. (3)

If each term in Equation 3 is 0 then 1 + x d +(1+ x ) d =0.Thatis, x d

is not

APN if there is a x ∈ V m \{ 0 , 1 } such that

( x + x l 1 ) 1+ x 2 a 0 − 1
1+ x

=(1+ x ) k 0 ( x 2 s 0 + x l 2 2 s 0 ) 1+( x 2 s 0 ) 2 a 1 − 1
1+ x 2 s 0

= ···

=(1+ x ) k q − 2 ( x 2 s q − 2 + x l q 2 s q − 2 ) 1+( x 2 s q − 2 ) 2 a q − 1 − 1
1+ x 2 s q − 2