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?


1 Answer 1


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:

enter image description here

  • 1
    $\begingroup$ Since the question (quickly deleted) was relevant to crypto and not asked before, I resurrected it. $\endgroup$
    – kodlu
    May 23, 2021 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.