[home]   [research projects]   [research interests]   [coding projects]

Cryptographic Functions

Bent-function rigidity: a correct narrow result that was overtaken by stronger work.

Background

Bent functions over finite fields are extremal from the Fourier point of view: their Walsh spectrum has constant magnitude. That spectral flatness makes them rigid objects, so a natural question is how close two distinct bent functions can be in Hamming distance.

Tools

The project was almost entirely Fourier algebra over a finite field. The distance-one argument is short only after the Walsh transform, Parseval, Hamming distance, and the relevant root-of-unity rigidity are on the table.

Walsh Transform

Definition. Let \(p\) be an odd prime, \(\zeta_p=e^{2\pi i/p}\), and \(f:\mathbb F_p^d\to\mathbb F_p\). Define \[ W_f(a)=\sum_{x\in\mathbb F_p^d}\zeta_p^{\,f(x)-a\cdot x}. \]
Definition. The function \(f\) is bent if \[ |W_f(a)|=p^{d/2} \] for every \(a\in\mathbb F_p^d\).

Parseval

Proposition. For the unnormalized Walsh transform, \[ \sum_{a\in\mathbb F_p^d}|W_f(a)|^2=p^{2d}. \]

Hamming Distance

Definition. For \(f,g:\mathbb F_p^d\to\mathbb F_p\), \[ d_H(f,g)=|\{x:f(x)\neq g(x)\}|. \]

Roots of Unity

Proposition. For prime \(p\), \[ 1+\zeta_p+\cdots+\zeta_p^{p-1}=0, \] and this cyclotomic relation gives the basic rational linear dependence among the \(p\)-th roots of unity.

Finite Uncertainty

Theorem. For a nonzero function \(h\) on a finite abelian group \(G\), \[ |\operatorname{supp}h|\,|\operatorname{supp}\widehat h|\geq |G|. \]

The distance-one proof came from combining these rigidities for the difference of two bent functions. The next section explains why I did not get the broader separation theorem I originally wanted.

Attempt that worked

For odd prime \(p\), I proved that two bent functions on \(\mathbb F_p^d\) cannot differ at exactly one input. The one-point case is unusually rigid: changing a single input produces a very simple Fourier-side perturbation, and the bent condition forces incompatible spectral constraints.

Why the argument did not scale the way I wanted

The natural next step was a broader separation theorem. Once several inputs may change, however, the Fourier perturbation becomes a sum of contributions and cancellation creates substantially more freedom. The clean one-point contradiction no longer carries over in the same form.

Why I moved on

I later found stronger work that went substantially beyond the narrow distance-one statement I had proved. My theorem was still correct, but it was no longer the theorem I wanted to build a standalone paper around. Rather than manufacture a weaker paper after the mathematical point had been overtaken, I stopped the project.

What I kept

The useful part was the method: translating local disagreement into Walsh-spectral constraints and moving between Parseval, roots of unity, and uncertainty. Those tools mattered more to me than the distance-one statement itself.

Last updated: September 14, 2026.