The nonlinearity and Hamming weights of rotation symmetric Boolean functions of small degree

Abstract

Let $e$, $l$ and $n$ be integers such that $1\le e<n$ and $3\le l\le n$. Let $\left\langle {i} \right\rangle$ denote the least nonnegative residue of $i \mod n$. In this paper, we investigate the following Boolean function $$F_{l, e}^n(x^n)=\sum_{i=0}^{n-1}x_{i} x_{\left\langle {i + e} \right\rangle}x_{\left\langle {i + 2e} \right\rangle }...x_{\left\langle {i + \left( {l - 1} \right)e} \right\rangle },$$ which plays an important role in cryptography and coding theory. We introduce some new sub-functions and provide some recursive formulas for the Fourier transform. Using these recursive formulas, we show that the nonlinearity of $F_{l, e}^n(x^n)$ is the same as its weight for $5\leq l\leq 7$. Our result confirms partially a conjecture of Yang, Wu and Hong raised in 2013. It also gives a partial answer to a conjecture of Castro, Medina and Stănică proposed in 2018. Our result extends the result of Zhang, Guo, Feng and Li for the case $l=3$ and that of Yang, Wu and Hong for the case $l=4$.

Keywords

• boolean function
• rotation symmetric boolean function
• nonlinearity
• weight
• fourier transform