[Resource Topic] 2000/005: On Resilient Boolean Functions with Maximal Possible Nonlinearity

Welcome to the resource topic for 2000/005

On Resilient Boolean Functions with Maximal Possible Nonlinearity

Authors: Yuriy Tarannikov


It is proved that the maximal possible nonlinearity of n-variable
m-resilient Boolean function is 2^{n-1}-2^{m+1} for
{2n-7\over 3}\le m\le n-2. This value can be achieved only for
optimized functions (i.~e. functions with an algebraic degree n-m-1).
For {2n-7\over 3}\le m\le n-\log_2{n-2\over 3}-2 it is suggested a method
to construct an n-variable m-resilient function with maximal possible
nonlinearity 2^{n-1}-2^{m+1} such that each variable presents in ANF of this
function in some term of maximal possible length n-m-1.
For n\equiv 2\pmod 3, m={2n-7\over 3},
it is given a scheme of hardware implementation for such function that
demands approximately 2n gates EXOR and (2/3)n gates AND.

ePrint: https://eprint.iacr.org/2000/005

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .