Article detail · 2007
Search for Boolean Functions With Excellent Profiles in the Rotation Symmetric Class
- Year
- 2007
- Type
- article
Data source split
- YÖKSİS YÖKSİS article record
- YÖKSİS venue IEEE TRANSACTIONS ON INFORMATION THEORY
- Catalog match (ISSN) IEEE Transactions on Information Theory
- OpenAlex OpenAlex enrichment (abstract, citations, topics)
Abstract
OpenAlex · English
For the first time Boolean functions on 9 variables having nonlinearity$241$are discovered, that remained as an open question in literature for almost three decades. Such functions are found by heuristic search in the space of rotation symmetric Boolean functions (RSBFs). This shows that there exist Boolean functions on$n$(odd) variables having nonlinearity$> 2^{n-1} - 2^{{ n-1}\over { 2}}$if and only if$n > 7$. Using similar search technique, balanced Boolean functions on 9, 10, and 11 variables are attained having autocorrelation spectra with maximum absolute value$< 2^{\lceil {{ n}\over { 2}}\rceil }$. On odd number of variables, earlier such functions were known for 15, 21 variables; there was no evidence of such functions at all on even number of variables. In certain cases, our functions can be affinely transformed to obtain first-order resiliency or first-order propagation characteristics. Moreover, 10 variable functions having first-order resiliency and nonlinearity$492$are presented that had been posed as an open question at Crypto 2000. The functions reported in this paper are discovered using a suitably modified steepest descent based iterative heuristic search in the RSBF class along with proper affine transformations. It seems elusive to get a construction technique to match such functions.
Topics
Citations
OpenAlex cited_by_count. Not a WoS or Scopus citation count; those sources have no separate column here.
160 citations
OpenAlex cited_by_count (cache / database)
16 publications in the local catalog that cite this work (OpenAlex reference match; not the full global list).
- 9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class 2010
- Generalized Rotation Symmetric and Dihedral Symmetric Boolean Functions − 9 Variable Boolean Functions with Nonlinearity 242 2007
- Construction and search of balanced Boolean functions on even number of variables towards excellent autocorrelation profile 2019
- Patterson-Wiedemann Type Functions on 21 Variables With Nonlinearity Greater Than Bent Concatenation Bound 2016
- A Super-Set of Patterson--Wiedemann Functions: Upper Bounds and Possible Nonlinearities 2018
- New Patterson--Wiedemann type functions with 15 variables in the generalized rotation-symmetric class 2017
- Genetic Approach to Improve Cryptographic Properties of Balanced Boolean Functions Using Bent Functions 2023
- 9-variable Boolean Functions with Nonlinearity 242 in the Generalized Rotation Class 2008
- Boolean Functions Generated from (1057, 31)-Interleaved Sequences 2023
- HIGHLY NONLINEAR (VECTORIAL) BOOLEAN FUNCTIONS THAT ARE SYMMETRIC UNDER SOME PERMUTATIONS 2020