Maximal differential uniformity distribution conjecture for polynomials over finite fields

Let nn be a positive integer, set q=2nq=2^n, and let fF2n[x]f\in\mathbb{F}_{2^n}[x] be a polynomial of degree m>4m>4. Define its differential uniformity by

δ(f):=max(α,β)F2n×F2n{xF2nf(x+α)+f(x)=β}.\delta(f):=\max_{(\alpha,\beta)\in\mathbb{F}_{2^n}^{\ast}\times\mathbb{F}_{2^n}}\sharp\{x\in\mathbb{F}_{2^n}\mid f(x+\alpha)+f(x)=\beta\}.

Maximal differential uniformity distribution conjecture. There exists εm>0\varepsilon_m>0 such that, for all sufficiently large nn, at least εm22n\varepsilon_m2^{2n} pairs (α,β)F2n×F2n(\alpha,\beta)\in\mathbb{F}_{2^n}^{\ast}\times\mathbb{F}_{2^n} satisfy

{xF2nf(x+α)+f(x)=β}=δ(f).\sharp\{x\in\mathbb{F}_{2^n}\mid f(x+\alpha)+f(x)=\beta\}=\delta(f).

The conjecture asserts that a positive proportion, depending only on the degree, of differential inputs attain the polynomial's maximal differential uniformity. The supplied evidence marks this statement as resolved; the surrounding discussion relates it to earlier results showing that maximal differential uniformity is typical for suitable degrees.

Sources & referencesView supporting material

Primary source

Yves Aubry, Fabien Herbaut and Jose Felipe Voloch, “Maximal differential uniformity polynomials”, arXiv:1708.01940 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.