We introduce a steepest-descent-like search algorithm for the design of Boolean functions,
yielding multiple desirable cryptographic properties in their Walsh and autocorrelation spectra
together. The algorithm finds some Boolean functions on 9, 10, 11, 13 variables with very
good cryptographic properties unattained in the literature. More specifically, we have discovered
9-variable rotation symmetric Boolean functions (RSBFs) having nonlinearity of
241, which exceeds the bent concatenation bound and has remained as an open question in
the literature for almost three decades. We have then shown that there is no RSBF having
nonlinearity greater than 241, and that there are 8x189 many RSBFs having nonlinearity of
241, such that, among them there are only two that are different up to the affine equivalence.
We also propose a generalization to RSBFs and dihedral symmetric Boolean functions (DSBFs),
which improves the nonlinearity result of 9-variable Boolean functions to 242. Further,
we classify all possible permutations (362, 880) on the input variables of 9-variable
Boolean functions and find that there are only 30 classes, which are different with respect
to the linear equivalence of invariant Boolean functions under some permutations. Some of
these classes and their subsets yield new 9-variable Boolean functions having the nonlinearity
of 242 with different autocorrelation spectra from those of the Boolean functions found in generalized RSBF and DSBF classes. Moreover, we have attained 13-variable balanced
Boolean functions having nonlinearity of 4036 which is greater than the bent concatenation
bound of 4032, and improves the recent result of 4034.
Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/3/12609795/index.pdf |
Date | 01 August 2008 |
Creators | Kavut, Selcuk |
Contributors | Diker Yucel, Melek |
Publisher | METU |
Source Sets | Middle East Technical Univ. |
Language | English |
Detected Language | English |
Type | Ph.D. Thesis |
Format | text/pdf |
Rights | To liberate the content for public access |
Page generated in 0.002 seconds