Upper bounds on Sidon sets limit binary code and function properties
A new upper bound for Sidon sets in $\mathbb{F}_2^{4k+3}$
Information Theory
Summary
This paper looks at special collections of points called Sidon sets in certain mathematical spaces and finds new limits on how big these sets can be. The authors prove that when the space has particular sizes, these sets can’t exceed a specific size. This result helps show that certain kinds of error-correcting binary codes can’t exist with given parameters. Also, the findings imply new minimum properties for a type of function used in cryptography, called almost perfect nonlinear functions.
What this means in practice
- •For coding theory engineers: Know that certain binary error-correcting codes with specific parameters cannot exist, guiding code design limits.
- •For cryptographic function designers: Use the new lower bound on nonlinearity of almost perfect nonlinear functions to assess or rule out function candidates in cryptosystems.
A theory result. No direct application yet.
Authors
Darrion Thornburgh
Abstract
A subset $S \subseteq \mathbb{F}_2^n$ is called a Sidon set if no four distinct points of $S$ have zero sum. It is shown that if $n \geq 7$ and $n \equiv 3 \mod 4$, then $|S|\leq 2^{\frac{n+1}{2}}-3$. As a consequence, for any even $t \geq 4$, there does not exist a binary linear $[2^t-3,2^t-2t-2,5]$-code, strengthening a nonexistence result of Brouwer and Tolhuizen from 1993. As a second consequence, we also show that for an even integer $n \geq 4$, every almost perfect nonlinear (APN) function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ has nonlinearity at least $3$.