Paper 2016/1078
Construction of $n$variable ($n\equiv 2 \bmod 4$) balanced Boolean functions with maximum absolute value in autocorrelation spectra $< 2^{\frac n2}$
Deng Tang and Subhamoy Maitra
Abstract
In this paper we consider the maximum absolute value $\Delta_f$ in the autocorrelation spectrum (not considering the zero point) of a function $f$. In even number of variables $n$, bent functions possess the highest nonlinearity with $\Delta_f = 0$. The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with $\Delta_f < 2^{\frac n2}$. So far there are only a few examples of such functions for $n = 10, 14$, but no general construction technique is known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on $n$ variables having absolute indicator strictly lesser than $\delta_n = 2^{\frac{n}{2}}2^{\frac{n+6}{4}}$, nonlinearity strictly greater than $\rho_n = 2^{n1}  2^{\frac{n}{2}} + 2^{\frac n23}  5\cdot2^{\frac{n2}{4}}$ and algebraic degree $n1$, where $n\equiv 2 \pmod 4$ and $n\geq 46$. While the bound $n \geq 46$ is required for proving the generic result, our construction starts from $n = 18$ and we could obtain balanced functions with $\Delta_f < 2^{\frac{n}{2}}$ and nonlinearity $> 2^{n1}  2^\frac{n}{2}$ for $n = 18, 22$ and $26$.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Absolute IndicatorAutocorrelation SpectrumBalancednessBoolean functionNonlinearity.
 Contact author(s)
 subho @ isical ac in
 History
 20161121: revised
 20161121: received
 See all versions
 Short URL
 https://ia.cr/2016/1078
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/1078, author = {Deng Tang and Subhamoy Maitra}, title = {Construction of $n$variable ($n\equiv 2 \bmod 4$) balanced Boolean functions with maximum absolute value in autocorrelation spectra $< 2^{\frac n2}$}, howpublished = {Cryptology ePrint Archive, Paper 2016/1078}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/1078}}, url = {https://eprint.iacr.org/2016/1078} }