Explicit Nonlinear Functions beyond the Fourier bound

본문 미리보기

We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$. Concretely, we want an $F$ and an $A = A(m,n)>0$ as small as possible, so that for every affine map $L: \mathbb{F}_2^n \to \mathbb{F}_2^m$ (of the form $L(x) = Mx + b$) we have: $$ \operatorname{agree}(F,L) := |\{x \in \mathbb{F}_2^n \mid F(x) = L(x)\}| \leq A. $$ Such questions have been studied by Nyberg [1991, 1993], Carlet and Ding [2004, 2007], Liu, Mesnager and Chen [2017], Nag