Sum of two bent functions cannot represent all low degree Boolean functions
A counterexample to Tokareva's conjecture on sums of two bent functions
Information Theory
Summary
The paper studies a special kind of mathematical function called bent functions, which have important properties in cryptography and coding. For even dimensions of variables, it was believed any function with a certain complexity could be made by adding two bent functions together. The authors found a specific function that proves this belief wrong, showing that not all such simple functions come from two bent functions. They also extend their findings to larger cases and related theories.
What this means in practice
- •For cryptographic engineers: Avoid relying on sums of two bent functions to represent all low-degree Boolean functions when designing cryptographic primitives.
- •For error-correcting code designers: Reconsider certain function decompositions in code constructions that assume such Boolean functions are sums of two bent functions.
A theory result. No direct application yet.
Authors
Yansong Feng, Hao Jiang, Guancheng Li, Tianyi Li, Lili Tang
Abstract
It is well known that the sum of two bent functions on $\mathbb{F}^n$ has algebraic degree at most $n/2$ for even $n\ge 4$. Tokareva conjectured that the converse holds: every Boolean function with degree at most $n/2$ can be written as a sum of two bent functions. The conjecture has been verified for even $n\leq 6$ and for several special classes of Boolean functions. We disprove this conjecture by showing that $x_1x_2(x_3x_4+x_5x_6+x_7x_8)$ is not a sum of two bent functions on $\mathbb{F}^8$. We extend this construction to obtain counterexamples in every even dimension $n\ge 8$. Using Shaporenko's reduction, we also obtain explicit counterexamples to Tokareva's derivative conjecture in every even dimension $n\ge 10$.