Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Highly nonlinear functions are used in combination generators and other stream ciphers.
We know that maximum nonlinearity (hamming distance to all affine functions) of $f$ is achieved when $f$ is bent function. This will be $$NL=2^{n-1}-2^{(n/2)-1}$$ when $n$ is even. Also when $n$ is odd, this bound is not satisfied. What will it be?
The question is: Can we find $f$ with largest nonlinearity for an arbitrary odd integer $n$ case?
This is a famous open problem in coding theory, the covering radius of the first order Reed-Muller code, when the number of variables is odd.
As far as I know the best general upper bound on nonlinearity which in this paper is denoted N (=covering radius R) for $n=2k+1$ is still the one below:
