Back to Search
Start Over
Construction of n -Variable ( n\equiv 2 \bmod 4 ) Balanced Boolean Functions With Maximum Absolute Value in Autocorrelation Spectra < 2^\frac n2.
- Source :
- IEEE Transactions on Information Theory; Jan2018, Vol. 64 Issue 1, p393-402, 10p
- Publication Year :
- 2018
-
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 an 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^{n/2} . 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^{n/2}-2^{(({n+6})/{4})} , nonlinearity strictly greater than \rho n = 2^{n-1} - 2^{n/2} + 2^{n/2-3} - 5\cdot 2^{(({n-2})/{4})} and algebraic degree n-1 , 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 nonlinearity > 2^n-1 - 2^n/2 for n = 18, 22 , and 26. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 64
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 126963969
- Full Text :
- https://doi.org/10.1109/TIT.2017.2769092