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

Date

2007-05-01

Author

Kavut, Selcuk
Maitra, Subhamoy
Yucel, Melek D.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

78
views

0
downloads

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.

Subject Keywords

Library and Information Sciences, Information Systems, Computer Science Applications

URI

https://hdl.handle.net/11511/67303

Journal

IEEE TRANSACTIONS ON INFORMATION THEORY

DOI

https://doi.org/10.1109/tit.2007.894696

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

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.