For each integer n≥ 1, determine M_bal(n)=maxoperatornameNL(f): f:F_2^n→F_2, |f^-1(1)|=2^n-1, where operatornameNL(f)=min_a∈F_2^n, b∈F_2|x∈F_2^n:f(x)≠ a· x+b|. In particular, determine the exact value of M_bal(8); the supplied report claims M_bal(8)=116, excluding 118.

Balanced Boolean-function nonlinearity problem

For each integer $n\geq 1$ , determine

M_{\mathrm{bal}}(n)=\max\left\{\operatorname{NL}(f): f:\mathbb{F}_2^n\to\mathbb{F}_2,\ \left|f^{-1}(1)\right|=2^{n-1}\right\},

where

\operatorname{NL}(f)=\min_{a\in\mathbb{F}_2^n,\ b\in\mathbb{F}_2}\left|\left\{x\in\mathbb{F}_2^n:f(x)\ne a\cdot x+b\right\}\right|.

In particular, determine the exact value of $M_{\mathrm{bal}}(8)$ ; the supplied report claims $M_{\mathrm{bal}}(8)=116$ , excluding $118$ .

Sources & referencesView supporting material

Primary source

IACR Cryptology ePrint Archive

Additional references

Theoretical Open Problems in Symmetric Cryptography: Verifiable LLM-Guided Analysis — IACR Cryptology ePrint Archive

boolean-functions computational-mathematics

1 day ago

Progress summary

Refreshed 1 day ago

Claimed solved

A new report claims the eight-variable case has been settled at nonlinearity $116$ , but the broader problem remains open.

The problem asks for the maximum nonlinearity of balanced Boolean functions, especially in the finite case of $8$ variables. Earlier literature treated $118$ as a possible maximum and reported $116$ as the best-known value.

Known results

A $2022$ construction achieved nonlinearity $116$ for $8$ variables, without proving optimality.
A $2023$ experimental study reported $116$ for $8$ variables using local search, not exhaustive classification.
Other $2022$ and $2023$ computational papers described the maximum as unknown for dimensions beyond the previously settled range.

August 2026 exact-classification claim

An IACR e-print reports that the $8$ -variable maximum is exactly $116$ , thereby excluding $118$ . The supplied evidence does not include an independently checked computational certificate, so this is a claim rather than a verified resolution.

Current status (as of August 2026): The $8$ -variable value is claimed to be exactly $116$ , but verification of the certificate and the general balanced Boolean-function problem remain open.

Sources

No solutions have been posted yet.