Search for Boolean Functions With Excellent Profiles in the Rotation Symmetric Class
Authors:
- Subhamoy MaitraSMSubhamoy Maitra
- Melek D. YucelMYMelek D. Yucel
Top Cited Papers
- 30 April 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 53 (5) , 1743-1751
Abstract
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 >2n-1-2n-1/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 lceiln/2rceil. 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 functionsKeywords
This publication has 20 references indexed in Scilit:
- Patterson–Wiedemann construction revisitedDiscrete Mathematics, 2006
- Almost Boolean Functions: The Design of Boolean Functions by Spectral InversionComputational Intelligence, 2004
- Modifications of Patterson-Wiedemann functions for cryptographic applicationsIEEE Transactions on Information Theory, 2002
- Further constructions of resilient Boolean functions with very high nonlinearityIEEE Transactions on Information Theory, 2002
- On some cosets of the first-order Reed-Muller code with high minimum weightIEEE Transactions on Information Theory, 1999
- A spectral characterization of correlation-immune combining functionsIEEE Transactions on Information Theory, 1988
- Optimization by Simulated AnnealingScience, 1983
- The covering radius of the(2^{15}, 16)Reed-Muller code is at least 16276IEEE Transactions on Information Theory, 1983
- The covering radius of the (128,8) Reed-Muller code is 56 (Corresp.)IEEE Transactions on Information Theory, 1980
- Weight distributions of the cosets of the (32,6) Reed-Muller codeIEEE Transactions on Information Theory, 1972