Explicit Nonlinear Functions beyond the Fourier bound
Cryptographers construct explicit highly nonlinear maps over finite fields that beat the classical Fourier agreement bound.
The paper studies vectorial maps from binary vector spaces that agree with every affine map on as few inputs as possible. Classical bent-function and Fourier constructions cannot push that agreement below about 2^{n/2}. For every gamma greater than 0 and an output dimension linear in n, the authors construct maps with agreement at most (1+gamma)^n, including against tuples of degree-d polynomials, improving on Ben-Sasson and Kopparty. The results extend to every finite field and use algebraic counts of solutions to polynomial systems.
- Constructs vectorial maps whose agreement with every affine map beats the Fourier bound.
- For every gamma>0 and m linear in n, agreement is at most (1+gamma)^n.
- The same quantitative bound holds against tuples of degree-d polynomials.
- All constructions extend from binary fields to arbitrary finite fields.
- Proofs count solutions of polynomial systems using algebraic and combinatorial methods.
From the original article
1 min read at arxiv.orgWe 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) = M x + b $) we have: $$\mathrm{agree}(F, L) := |\{ x \in \mathbb F_2^n \mid F(x) = L(x) \}| \leq A.
By Swastik Kopparty · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.