On a conjecture on the Kasami APN function: reductions, structure theorems, a proof for $k\mathrm{mod}n\in \{1,2,n-2,n-1\}$, and exhaustive verification for $n\le 13$

Abstract

We study a conjecture on the Kasami almost perfect nonlinear (APN) function $F(x)=x^{4^k-2^k+1}$ on $GF(2^n)$, $\gcd (k,n)=1$: for the $2^{n-1}$-element set $\Delta =\{F(b)+F(b+1)+1:b\in GF(2^n)\}$ and all distinct nonzero $v_1,v_2\in GF(2^n)$, \[ \bigl|\{(x,y,z)\inΔ^3 : v_1x+v_2y+(v_1+v_2)z=0\}\bigr| \;=\; 2^{2n-3}. \] The conjecture was proposed at the NSUCRYPTO~2019 cryptographic olympiad (the proposer of the problem was not publicly disclosed). We prove the conjecture for $k\mathrm{mod}n\in \{1,2,n-2,n-1\}$, in particular a complete proof for $k=2$ ($d=13$) via a quadratic-form theory and an exact root-count reduction, and we verify it exhaustively by computer for every admissible $(n,k)$ with $n\le 13$.