SFU Discrete Math Seminar: Alexander Pott

A function $f:\F_2^n\to \F_2^n$ is called almost perfect nonlinear (APN) if $f(x) + f(y) + f(z) + f(x + y + z)= 0$ all $x,y,z$ such that $|\{x,y,z,x+y+z\}|=4$.. The motivation to study these functions comes from cryptography, since the defining property is somehow opposite to linearity. The big open problem on APN functions is whether there are APN permutations if n is even. There is only one example known if n = 6 [1]. For such permutations, there is an interesting reformulation:

Theorem 1. A bijection $f:\F_2^n\to \F_2^n$ is APN if and only if all affine subspaces of dimension 2 in $\F_2^n$ are mapped to sets which are not subspaces.

If a permutation is not APN, the number of subspaces which are mapped to subspaces measures the distance to APN functions. In this talk, I will survey some recent results about the number of such "vanishing flats".

This approach of vanishing flats may also serve as an interesting and perhaps fruitful extension of APN functions to design theory, since the set of affine subspaces of dimension 2 form a certain design. In my talk I will give the following indication that the design theoretic approach might be useful: recently, a relaxation of APN functions has been introduced [2]: A function is called partially APN if $f(y)+f(z)+f(y+z)\ne 0$ for all $y,z\ne 0$, $y\ne z$. That means that the APN property is satisfied for x = 0 only.

The main result is the following:

Theorem 2. Partially APN permutations exist for all n. The proof is non-constructive and uses an interesting connection (rather an observation than a theorem) to Steiner triple systems as well as [3].

References:

[1] K.A. Browning, J.F. Dillon, M.T. McQuistan and A.J. Wolfe, An APN Permutation in Dimension Six. In: Finite Fields: Theory and Application, Contemporary Mathematics 518 (2010), pp 33-42. 

[2] L. Budaghyan, N.S. Kaleyski, S. Kwon, C. Riera and P. Stanica, Partially APN Boolean functions and classes of functions that are not APN infinitely often. To appear in Cryptograpy and Communications (2019). arXiv:1905.13025.

[3] L. Teirlinck, On Making Two Steiner Systems Disjoint, Journal of Combinatorial Theory A 23 (1977), pp 349-350.