Search for Boolean functions with excellent profiles in the rotation symmetric class

2007-05-01
Kavut, Selcuk
Maitra, Subhamoy
Yucel, Melek D.
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 non, linearity > 2(n-1) - 2 (n-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 < 2 [n/2]. 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.
IEEE TRANSACTIONS ON INFORMATION THEORY

Suggestions

Constructing linear unequal error protection codes from algebraic curves
Özbudak, Ferruh (Institute of Electrical and Electronics Engineers (IEEE), 2003-06-01)
We show that the concept of "generalized algebraic geometry codes" which was recently introduced by Xing, Niederreiter, and Lam gives a natural framework for constructing linear unequal error protection codes.
An improvement on the bounds of Weil exponential sums over Gallois rings with some applications
Ling, S; Özbudak, Ferruh (Institute of Electrical and Electronics Engineers (IEEE), 2004-10-01)
We present an upper bound for Weil-type exponential sums over Galois rings of characteristic p(2) which improves on the analog of the Weil-Carlitz-Uchiyama bound for Galois rings obtained by Kumar, Helleseth, and Calderbank. A more refined bound, expressed in terms of genera of function fields, and an analog of McEliece's theorem on the divisibility of the homogeneous weights of codewords in trace codes over Z(p)2, are also derived. These results lead to an improvement on the estimation of the minimum dista...
Cyclic codes and reducible additive equations
Guneri, Cem; Özbudak, Ferruh (Institute of Electrical and Electronics Engineers (IEEE), 2007-02-01)
We prove a Weil-Serre type bound on the number of solutions of a class of reducible additive equations over finite fields. Using the trace representation of cyclic codes, this enables us to write a general estimate for the weights of cyclic codes. We extend Woffmann's weight bound to a larger classes of cyclic codes. In particular, our result is applicable to any cyclic code over F-p and F-p2, where p is an arbitrary prime. Examples indicate that our bound performs very well against the Bose-Chaudhuri-Hocqu...
A genetic algorithm approach for verification of the syllable-based text compression technique
Üçoluk, Göktürk; Toroslu, İsmail Hakkı (SAGE Publications, 1997-01-01)
Provided that an easy mechanism exists for it, it is possible to decompose a text into strings that have lengths greater than one and occur frequently. Having in one hand the set of such frequently occurring strings and in the other the set of letters and symbols, it is possible to compress the text using Huffman coding over an alphabet which is a subset of the union of these two sets. Observations reveal that, in most cases, the maximal inclusion of the strings leads to an optimal length of compressed text...
The Augustin Capacity and Center
Nakiboğlu, Barış (Pleiades Publishing Ltd, 2019-10-01)
For any channel, the existence of a unique Augustin mean is established for any positive order and probability mass function on the input set. The Augustin mean is shown to be the unique fixed point of an operator defined in terms of the order and the input distribution. The Augustin information is shown to be continuously differentiable in the order. For any channel and convex constraint set with finite Augustin capacity, the existence of a unique Augustin center and the associated van Erven-Harremoes boun...
Citation Formats
S. Kavut, S. Maitra, and M. D. Yucel, “Search for Boolean functions with excellent profiles in the rotation symmetric class,” IEEE TRANSACTIONS ON INFORMATION THEORY, pp. 1743–1751, 2007, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/67303.