A Maiorana--McFarland type construction for resilient Boolean functions on n variables (n even) with nonlinearity >2ⁿ-1-2ⁿ/2+2ⁿ/2-2

DOI10.1016/J.DAM.2005.03.014MaRDI QIDQ2489931zbMATH OpenOpenAlexFDO

Authors Subhamoy Maitra, E. Pasalic

Publication date 28 April 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.03.014

zbMATH Keywords

autocorrelation Boolean function nonlinearity resiliency

Mathematics Subject Classification ID

Cryptography (94A60)

Review text

In this paper, we present a construction method of \(m\)-resilient Boolean functions with very high nonlinearity for low values of \(m\). The construction only considers functions in even number of variables \(n\). So far the maximum nonlinearity attainable by resilient functions was \(2^{n-1}-2^{n/2}+2^{n/2-2}\). Here, we show that given any \(m\), one can construct \(n\)-variable, \(m\)-resilient functions with nonlinearity \(2^{n-1}-11\cdot 2^{n/2-4}\) for all \(n\geq 8m+6\) which is strictly greater than \(2^{n-1}-2^{n/2}+2^{n/2-2}\). We also demonstrate that in some specific cases one may get such nonlinearity even for some values of \(n\), where \(n<8m+6\). Further, we show that for sufficiently large \(n\), it is possible to get such functions with nonlinearity reaching almost \(2^{n-1}-2^{n/2}+\frac43 2^{n/2-2}\). This is the upper bound on nonlinearity when one uses our basic construction recursively. Lastly, we discuss the autocorrelation property of the functions and show that the maximum absolute value in the autocorrelation spectra is \(\leq 2^{n-3}\).

Recommendations

Cites work

Cited in

(10)

This page was built for publication: A Maiorana--McFarland type construction for resilient Boolean functions on \(n\) variables (\(n\) even) with nonlinearity \(>2^{n-1}-2^{n/2}+2^{n/2-2}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489931)